## 2 An \(O(n)\)-Round Strategy for [PERSON]
### When \(n\) is composite
#### 2.3.2 The second phase: Visiting leftover unvisited positions  
Here, [PERSON] strategy is the same as in Phase 2 from [1]. At the end of the first phase, there is one unvisited class, which we denote \([\gamma]_{p}\), and \(p-1\) explored classes, which we denote \([\delta_{1}]_{p},\ldots,[\delta_{p-1}]_{p}\). Inductively we assume that on a table of size \(\frac{n}{p}\) [PERSON] can visit \(f^{*}(\frac{n}{p})\) positions in at most \(3(\frac{n}{p}-1)\) rounds. (This will follow from the inductive hypothesis in our proof in Section 2.3.3.) It follows that at the end of the first phase at least \(f^{*}(\frac{n}{p})\) positions have been visited in each of the explored classes. Without loss of generality we assume the worst case, in which exactly \(f^{*}(\frac{n}{p})\) positions were visited. Let \(p^{\prime}\) be the second smallest odd prime factor of \(n\). By Theorem 1, \(f^{*}(\frac{n}{p})=\frac{p^{\prime}-1}{p^{\prime}}\cdot\frac{n}{p}\). Then in each explored class, \(\frac{n}{p}-f^{*}(\frac{n}{p})=\frac{n}{pp^{\prime}}\) positions remain unvisited. We consider two ways in which [PERSON] can bring the total number of visited positions up to \(f^{*}(n)\). If [PERSON] visits all \(\frac{n}{pp^{\prime}}\) leftover positions in each of the explored classes, then he will have visited every position in \(p-1\) classes for a total of \(f^{*}(n)=(p-1)\frac{n}{p}\) positions. If instead he visits \(f^{*}(\frac{n}{p})\) positions of \([\gamma]_{p}\), then he will have visited all but \(\frac{n}{pp^{\prime}}\) positions in every class, leaving \(\frac{n}{p^{\prime}}\leq\frac{n}{p}\) unvisited positions in total. But this means that he has visited \(f^{*}(n)\) positions. Therefore [PERSON] goal will be to either move the token to the class \([\gamma]_{p}\), at which point he can recursively explore that class, or to visit all unvisited positions in \([\delta_{1}]_{p},\ldots,[\delta_{p-1}]_{p}\). Notice that since \(\gamma,\delta_{1},\ldots,\delta_{p-1}\) are the \(p\) distinct elements of \(\mathbb{Z}_{p}\), we have that \(\gamma,2^{-1}(\delta_{1}+\gamma),\ldots,2^{-1}(\delta_{p-1}+\gamma)\) are also distinct in \(\mathbb{Z}_{p}\). Therefore, up to re-ordering, we may write the explored classes as \([2^{-1}(\delta_{1}+\gamma)]_{p},\ldots,[2^{-1}(\delta_{p-1}+\gamma)]_{p}\). Let \(J\in[\delta_{i}]_{p}\) be an unvisited position for some \(1\leq i\leq p-1\), and suppose for the moment that [PERSON] is able to move the token to a position \(K\in[2^{-1}(\delta_{i}+\gamma)]_{p}\). Consider what happens when [PERSON] chooses the magnitude \(J-K\). If [PERSON] chooses the positive (clockwise) direction, then the token moves to \(K+(J-K)=J\), and [PERSON] visits the unvisited position. Otherwise, the token moves to \(K-(J-K)\in[\gamma]_{p}\). Using the above idea, [PERSON] has the following strategy. As in the first phase, he uses the technique from Section 2.2 to play on an imaginary table of size \(p\), where each position on this table corresponds to a class. Then by Theorem 4 he will visit \(p-1\) classes. If at any time he visits the class \([\gamma]_{p}\), he recursively explores it and is done. Otherwise, he will visit each of the \(p-1\) explored classes, \([2^{-1}(\delta_{1}+\gamma)]_{p},\ldots,[2^{-1}(\delta_{p-1}+\gamma)]_{p}\). Each time he visits a class \([2^{-1}(\delta_{i}+\gamma)]_{p}\) he has the opportunity to visit an unvisited position in the class \([\delta_{i}]_{p}\). By repeating this process \(\frac{n}{pp^{\prime}}\) times (for the \(\frac{n}{pp^{\prime}}\) unvisited positions in each explored class) he will eventually visit all unvisited positions in every explored class. We give [PERSON] strategy in pseudo-code in algorithm 1, below. It remains to prove that this strategy visits at least \(f^{*}(n)\) positions in at most \(3(n-1)\) rounds. ```
1:\(p\) is the smallest prime factor of \(n\). 2: The table is partitioned into \(p\) congruence classes modulo \(p\), \(\{[i]_{p}:0\leq i\leq p-1\}\), each of size \(\frac{n}{p}\),-
3: //Phase 1: Visit \(p-1\) congruence classes, and recursively explore each one.