Putnam 2009, Problem B-6

Prove that for every positive integer $n$, there is a sequence of integers $a_0, a_1, \ldots, a_{2009}$ with $a_0 = 0$ and $a_{2009} = n$ such that each term after $a_0$ is either an earlier term plus $2^k$ for some nonnegative integer $k$, or of the form $b \bmod c$ for some earlier positive terms $b$ and $c$. [Here $b \bmod c$ denotes the remainder when $b$ is divided by $c$, so $0 \leq (b \bmod c) < c$.]


Solution:
**First solution.** (based on work of Yufei Zhao) Since any sequence of the desired form remains of the desired form upon multiplying each term by 2, we may reduce to the case where \( n \) is odd. In this case, take \( x = 2^h \) for some positive integer \( h \) for which \( x \geq n \), and set
\[
\begin{aligned}
a_0 &= 0 \\
a_1 &= 1 \\
a_2 &= 2x + 1 = a_1 + 2x \\
a_3 &= (x + 1)^2 = a_2 + x^2 \\
a_4 &= x^n + 1 = a_1 + x^n \\
a_5 &= n(x + 1) = a_4 \mod a_3 \\
a_6 &= x \\
a_7 &= n = a_5 \mod a_6.
\end{aligned}
\]
We may pad the sequence to the desired length by taking \( a_8 = \cdots = a_{2009} = n \).

**Second solution.** (by James Merryfield) Suppose first that \( n \) is not divisible by 3. Recall that since 2 is a primitive root modulo \( 3^2 \), it is also a primitive root modulo \( 3^h \) for any positive integer \( h \). In particular, if we choose \( h \) so that \( 3^{2h} > n \), then there exists a positive integer \( c \) for which \( 2^c \mod 3^{2h} = n \). We now take \( b \) to be a positive integer for which \( 2^b > 3^{2h} \), and then put
\[
\begin{aligned}
a_0 &= 0 \\
a_1 &= 1 \\
a_2 &= 3 = a_1 + 2 \\
a_3 &= 3 + 2^b \\
a_4 &= 2^{hb} \\
a_5 &= 3^{2h} = a_4 \mod a_3 \\
a_6 &= 2^c \\
a_7 &= n = a_6 \mod a_5.
\end{aligned}
\]
If \( n \) is divisible by 3, we can force \( a_7 = n - 1 \) as in the above construction, then put \( a_8 = a_7 + 1 = n \). In both cases, we then pad the sequence as in the first solution.

**Remark.** Hendrik Lenstra, Ronald van Luijk, and Gabriele Della Torre suggest the following variant of the first solution requiring only 6 steps. For \( n \) odd and \( x \) as in the first solution, set
\[
\begin{aligned}
a_0 &= 0 \\
a_1 &= 1 \\
a_2 &= x + 1 = a_1 + x \\
a_3 &= x^n + x + 1 = a_2 + x^n \\
a_4 &= x^{(n-1)(\phi(a_3) - 1)} \\
a_5 &= \frac{x^n + 1}{x + 1} = a_4 \mod a_3 \\
a_6 &= n = a_5 \mod a_2.
\end{aligned}
\]
It seems unlikely that a shorter solution can be constructed without relying on any deep number-theoretic conjectures.