Prove that the given sequence contains all natural numbers A sequence $\{a_n\}$ is defined in the following manner. Let $a_1$ be any arbitrary natural number. Let $S_n=a_1+a_2+…a_n$. Define $a_{n+1}$ to be the smallest natural number $k$ such that $\gcd(S_n,k)=1$ and $a_i \neq k$ for $i=1,2,…,n$. Prove that every natural number appears in this sequence.
My work so far has just been some casework showing that $2$, $3$ and $4$ will always be in the sequence. Not sure how to extend this to all numbers- I tried induction, but that didn't work. Let the induction hypothesis be: at some point all numbers up to $n-1$ have appeared. Then if $n$ is prime then it's quite easy to show that at some point, $S$ will be divisible by $n$ and we are done. But it's not that simple when $n$ has more than one prime divisor.
 A: This is not a complete solution.

For $a_1 = 1$.
Hint: List out the first 20 terms.
Find a pattern. The pattern doesn't start immediately, which is why I asked for 20 terms.
That should be enough for you to guess what $a_i$ is, then prove it.

Here's my guess of how the general case will proceed:

*

*Show that for any $a_1$, there exists an $N=4k+1$ such that the first $N$ terms in the sequence are the first $N$ integers.

*Then, the result follows from $a_1 = 1$.

A: Define $b_n$ as the smallest $m \not\in \{a_j : j \le n\}$. If $\text{gcd}(S_n, b_n)$ equals 1, then $a_{n+1} = b_n$. Assume now that it does not equal 1, so that then $a_{n+1} > b_n$, and therefor $b_{n+1} = b_n$. We have
$$\text{gcd}(S_n, S_{n+1}) = \text{gcd}(S_n, S_n + a_{n+1}) = \text{gcd}(S_n, a_{n+1}) = 1$$
Therefore, $\text{gcd}(S_{n+1}, b_n) = 1$. Now $a_{n+2} = b_{n+1} = b_n$, so that $b_n + 1 \le b_{n+2}$. This last inequality becomes (by an induction argument) $b_{r(n)} + \lfloor(n+1)/2\rfloor \le b_{n+2}$, where $r(n)$ equals $1$ if $n$ is odd, and $2$ if it is even. We conclude then that if $k < b_{r(n)} + \lfloor{(n+1)/2}\rfloor$ then $k \in \{a_j : j \le n + 2\}$.
