Problem 1945

Let $x(n) = \sum_{v_p(n) \ge 2} 1$ and $y(n) = \sum_{v_p(n)=1} 1$. Let the maximum number of islands that can be visited be denoted as $k(n)$. Then we have:
$$k(n) = \begin{cases} 3x(n) + 2y(n) + 1, & v_2(n) \neq 1, \\ 3x(n) + 2y(n), & v_2(n) = 1. \end{cases}$$
For $x, y \in \mathbb{Z}$ and $m \in \mathbb{Z}_{>0}$, if $xy \equiv xa \pmod{m}$, we denote this as $x \to y \pmod{m}$. Let $p$ be a prime factor of $n$ and $p^\alpha \nmid n$. For a sequence $x_1 \to x_2 \to \dots \to x_k \pmod{n}$, the same relation holds modulo $p^\alpha$:
$$x_1 \to x_2 \to \dots \to x_k \pmod{p^\alpha}.$$
(1) If $x_i \neq 0 \pmod{p^\alpha}$, then $x_{i+1}$ is coprime to $p$. This is because $p^\alpha \mid x_i(x_{i+1} - a)$, and $p^\alpha \nmid x_i$. Therefore, $p \mid x_{i+1} - a$. Since $a$ is coprime to $n$, we have $p \nmid a$, which implies $p \nmid x_{i+1}$.
(2) If $x_i$ is coprime to $p$, then $x_{i+1} \equiv a \pmod{p^\alpha}$. This is because $p^\alpha \mid x_i(x_{i+1} - a)$, and since $p \nmid x_i$, we have $p^\alpha \mid x_{i+1} - a$.
(3) From (1) and (2), we can conclude that if $\alpha \ge 2$, the sequence $x_1, x_2, \dots, x_k \pmod{p^\alpha}$ undergoes at most three changes: it changes from being divisible by $p^\alpha$ to being nonzero, then becomes coprime to $p$, and finally becomes congruent to $a$ modulo $p^\alpha$.
If $\alpha = 1$ and $p \neq 2$, then $x_1, x_2, \dots, x_k \pmod{p^\alpha}$ undergo at most two changes: it changes from being congruent to 0 modulo $p$ to being coprime to $p$, and finally becomes congruent to $a$ modulo $p$.
If $\alpha = 1$ and $p = 2$, then $x_1, x_2, \dots, x_k \pmod{p^\alpha}$ undergo at most one change: it changes from being congruent to 0 modulo 2 to being congruent to $a$ modulo 2.
Assuming that $x_1, x_2, \dots, x_k \pmod{n}$ have distinct adjacent terms, then adjacent terms have changes in some modulo $p^\alpha$, implying that $k \le k(n)$.
(4) Construct examples for $k = k(n)$. First, consider the cases based on modulo $p^\alpha$.
(i) If $\alpha \ge 2$, we have $0 \to p \to a + p^{\alpha-1} \to a \pmod{p^\alpha}$.
(ii) If $\alpha = 1$ and $p \neq 2$, we have $0 \to b \to a \pmod{p}$, where $b$ is coprime to $p$ and $b \neq a \pmod{p}$.
(iii) If $\alpha = 1$ and $p = 2$, we have $0 \to a \pmod{2}$.
Let $n = p_1^{\alpha_1} \cdots p_w^{\alpha_w}$ be the prime factorization of $n$. For each $p_i^{\alpha_i}$, we choose a sequence corresponding to the three cases mentioned above. Note that $0 \to 0$ and $a \to a$. We can appropriately add some zeros at the beginning and some $a$'s at the end of the sequences to ensure that their lengths reach $k(n)$. Let's denote these modified sequences as $L_i$. It is required that for $p_i^{\alpha_i}$ and $p_j^{\alpha_j}$ ($i \neq j$), the positions where changes occur in $L_i$ and $L_j$ are different.

For example, suppose $\alpha_1 \ge 2$, we can take
$$L_1: 0 \to p_1 \to a + p_1^{\alpha_1-1} \to a \to a \to \dots \to a \pmod{p_1^{\alpha_1}}.$$
If $\alpha_2 = 1$ and $p_2 \ne 2$, we can also take
$$L_2: 0 \to 0 \to 0 \to 0 \to b \to a \to a \to \dots \to a \pmod{p_2},$$
and continue this way to construct $L_3, \dots, L_w$.
By using the $t$-th term of $L_1, L_2, \dots, L_w$ and the Chinese Remainder Theorem, we can determine $x_t$. Since $x_t \to x_{t+1} \pmod{p_i^{\alpha_i}}$ for $1 \le i \le w$, it follows that $x_t \to x_{t+1} \pmod{n}$. Moreover, the sequence $x_1, x_2, \dots, x_{k(n)}$ modulo $n$ has distinct terms. This confirms the conclusion of the original problem, and the maximum value $k(n)$ is given by the formula mentioned at the beginning of the solution. $\square$