, 2014

Solution:

Answer: $127$

It is clear that the sequence $\{a_{i}\}$ will be a concatenation of sequences of the form $\{v_{i}\}_{i=1}^{N_{0}},\{w_{i} \cdot p_{1}\}_{i=1}^{N_{1}},\{x_{i} \cdot p_{1} p_{2}\}_{i=1}^{N_{2}},\{y_{i} \cdot p_{1} p_{2} p_{3}\}_{i=1}^{N_{3}}$, and $\{z_{i} \cdot p_{1} p_{2} p_{3} p_{4}\}_{i=1}^{N_{4}}$, for some permutation $(p_{1}, p_{2}, p_{3}, p_{4})$ of $(2,3,5,7)$ and some sequences of integers $\{v_{i}\} \cdot \{w_{i}\} \cdot \{x_{i}\} \cdot \{y_{i}\} \cdot \{z_{i}\}$, each coprime with $210$.

In $\{v_{i}\}_{i=1}^{N_{0}}$, there are a maximum of $\phi(210)$ distinct terms $\bmod\ 210$. In $\{w_{i} \cdot p_{1}\}_{i=1}^{N_{1}}$, there are a maximum of $\phi\left(\frac{210}{p_{1}}\right)$ distinct terms mod $210$. In $\{x_{i} \cdot p_{1} p_{2}\}_{i=1}^{N_{2}}$, there are a maximum of $\phi\left(\frac{210}{p_{1} p_{2}}\right)$ distinct terms mod $210$. In $\{y_{i} \cdot p_{1} p_{2} p_{3}\}_{i=1}^{N_{3}}$, there are a maximum of $\phi\left(\frac{210}{p_{1} p_{2} p_{3}}\right)$ distinct terms mod $210$. In $\{z_{i} \cdot p_{1} p_{2} p_{3} p_{4}\}_{i=1}^{N_{4}}$, there can only be one distinct term $\bmod\ 210$.

Therefore we wish to maximize $\phi(210)+\phi\left(\frac{210}{p_{1}}\right)+\phi\left(\frac{210}{p_{1} p_{2}}\right)+\phi\left(\frac{210}{p_{1} p_{2} p_{3}}\right)+1$ over all permutations $(p_{1}, p_{2}, p_{3}, p_{4})$ of $(2,3,5,7)$. It's easy to see that the maximum occurs when we take $p_{1}=2$, $p_{2}=3$, $p_{3}=5$, $p_{4}=7$ for an answer of $\phi(210)+\phi(105)+\phi(35)+\phi(7)+1=127$. This upper bound is clearly attainable by having the $v_{i}$'s cycle through the $\phi(210)$ integers less than $210$ coprime to $210$, the $w_{i}$'s cycle through the $\phi\left(\frac{210}{p_{1}}\right)$ integers less than $\frac{210}{p_{1}}$ coprime to $\frac{210}{p_{1}}$, etc.