## 2 An \(O(n)\)-Round Strategy for [PERSON]
### When \(n\) is composite
#### 2.3.1 The first phase: Decomposition into classes, and recursive visitation  
**Lemma 4** (Decomposition). : _Let the table size be \(n=ab\), where \(a\) and \(b\) are integers greater than \(1\). Suppose that on a table of size \(a\) (resp. \(b\)), [PERSON] has a strategy \(\alpha\) (resp. \(\beta\)) to visit \(f^{*}(a)\) (resp.\(f^{*}(b)\))positions in \(r(a)\) (resp. \(r(b)\)) rounds. Then on the table of size \(n\), [PERSON] is able to visit \(f^{*}(a)f^{*}(b)\) positions in \(r(b)+r(a)f^{*}(b)\) rounds._  
Proof. : We partition the table positions (_i.e._, the elements of \(\mathbb{Z}_{n}\)) into the \(b\) congruence classes modulo \(b\), each of size \(a\):  
\[[i]_{b}=\{i+jb:0\leq j\leq a-1\}\qquad\text{for $0\leq i\leq b-1$}\]  
We first note that [PERSON] can restrict his play to positions in a particular class. Let \(K\) denote the current position of the token, and suppose that \(K\in[i]_{b}\) for some \(0\leq i\leq b-1\). [PERSON] can then play as follows on an imaginary table of size \(a\) whose positions are the elements of \([i]_{b}\). On each round, [PERSON] employs strategy \(\alpha\) to calculate a magnitude \(\ell\) as if the table size were \(a\), but then chooses \(b\ell\) as the actual magnitude to use. Then the new position of the token will be \(K\pm b\ell\in[i]_{b}\), and so the token will remain within the class. [PERSON] overall strategy will be to repeatedly move the token to an unvisited class, and then, by restricting his play to positions within that class, use strategy \(\alpha\) to visit \(f^{*}(a)\) positions within that class in \(r(a)\) rounds. Now suppose that \(K\in[i]_{b}\) for some \(i\), and notice that for any magnitude \(\ell\), \((K\pm\ell)\mod n\in[i\pm\ell\pmod{b})]_{b}\). [PERSON] can use this idea to play on an imaginary table of size \(b\) whose positions correspond to the \(b\) congruence classes. By employing strategy \(\beta\) on this imaginary table, [PERSON] will visit \(f^{*}(b)\) different classes in \(r(b)\) rounds. Each time the token lands in an unvisited class, [PERSON] temporarily restricts his play to that class, and employs strategy \(\alpha\) until he has visited \(f^{*}(a)\) positions within that class. He then continues with strategy \(\beta\) until he reaches another unvisited class. Since [PERSON] can visit \(f^{*}(b)\) classes in \(r(b)\) rounds, and can visit \(f^{*}(a)\) positions in \(r(a)\) rounds within each class, the total number of positions visited will be \(f^{*}(a)f^{*}(b)\) and the total number of rounds will be \(r(b)+r(a)f^{*}(b)\). [PERSON] applies the Decomposition Lemma (Lemma 4) by letting \(n=pm\), where \(p\) is the smallest odd prime factor of \(n\), and partitioning the table into \(p\) congruence classes modulo \(p\), each of size \(\frac{n}{p}\). He then proceeds as in the proof of the lemma, letting strategy \(\beta\) be the technique for playing on a table of prime size from Section 2.2. Theorem 4 then guarantees that he will visit \(p-1\) congruence classes. As he visits each class, he restricts his play to it and, depending on the size of the class, chooses one of the following strategies to be strategy \(\alpha\):  
1. If the size is a power of two, he uses the strategy from Section 2.1. Then by Theorem 2 he will visit all positions in the class. 2. If the size is a prime, he uses the strategy from Section 2.2. Then by Theorem 4 he will visit all but one position in the class. 3. Otherwise, if the size is composite, he uses the strategy being described here (Section 2.3), applied recursively. We will use the terminology _exploring a class_ to refer to the process of restricting play to a class and choosing an appropriate strategy \(\alpha\). We will also say that a class that has been visited in this fashion has been _explored_. See phase 1 of algorithm 1, below, for a pseudo-code description of this strategy. Recall that [PERSON] goal is to visit \(f^{*}(n)=\left(\frac{p-1}{p}\right)n\) positions (in as few rounds as possible).