Let me denote a sequence of distinct natural numbers by $x_n$ whose terms are determined as follows:
$x_1$ is $1$ and $x_2$ is the smallest distinct natural number $n$ such that $x_1+x_2$ is divisible by $2$, which is $3$. Similarly $x_n$ is the smallest distinct natural number such that $x_1+…+x_n$ is divisible by $n$. Thus $x_1=1$, $x_2=3$, $x_3=2$.
Now the problem is to show that
(i) $x_n$ is surjective
(ii) $x_{(x_n)}$ is $n$, for example $x_2=3$ and $x_3=2$
Best Answer
As other posters have noticed, this is closely related to the golden ratio $\varphi = \frac{1+\sqrt{5}}{2}$.
@ Ross Millikan your answer is a great place to start.
$\frac{1}{\varphi}+\frac{1}{\varphi ^2}=1$, so we can partition the natural numbers greater than 1 into numbers of the forms $\lceil {n \varphi} \rceil, \lceil {n \varphi ^2} \rceil$. (Add 1 to the beatty sequences)
Define $a_1=1, a_{\lceil {n \varphi} \rceil}=\lceil {n \varphi ^2} \rceil, a_{\lceil {n \varphi ^2} \rceil}=\lceil {n \varphi} \rceil$. Clearly $a_{a_n}=n$.
That's where the next crucial observation that $\sum\limits_{i=1}^{n}{a_i}=n \lceil{\frac{n}{\varphi}} \rceil$ comes in.
We proceed by induction on $n$ to show that $\sum\limits_{i=1}^{n}{a_i}=n \lceil{\frac{n}{\varphi}} \rceil$ and that $a_n$ is the smallest integer satisfying the divisiblity relation $n \mid \sum\limits_{i=1}^{n}{a_i}$.
When $n=1$, we have $1=1 \lceil{\frac{1}{\varphi}} \rceil$, which is true. When $n=2$, we have $1+3=2 \lceil{\frac{2}{\varphi}} \rceil$, which is true.
Suppose it holds for $n=k \geq 2$. Then $\sum\limits_{i=1}^{k}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil$. Consider 2 cases:
Case 1: $k+1=\lceil{m \varphi} \rceil$ for some $m \in \mathbb{Z}^+$. Then $a_{k+1}=\lceil{m \varphi ^2} \rceil=m+\lceil{m \varphi} \rceil=m+k+1$.
Now $k+1=m \varphi +1- \{m \varphi \}$ so $m-1<m-\frac{\{m \varphi \}}{\varphi}=\frac{k}{\varphi}<m<m+\frac{1-\{m \varphi \}}{\varphi}=\frac{k+1}{\varphi}<m+1$. Thus $\lceil{\frac{k}{\varphi}} \rceil=m, \lceil{\frac{k+1}{\varphi}} \rceil=m+1$.
$\sum\limits_{i=1}^{k+1}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil+a_{k+1}=km+(m+k+1)=(k+1)(m+1)=(k+1) \lceil{\frac{k+1}{\varphi}} \rceil$.
Minimality: Note that $a_{k+1}=m+k+1<2(k+1)$, and because we have a partition, $a_{k+1} \not =a_i \, \forall i$, so it suffices to show that $a_i=m$ for some $i$ with $1 \leq i \leq k$, or equivalently, $a_m \leq k$. If $m=\lceil{b \varphi ^2 } \rceil$ for some $b \in \mathbb{Z}^+$, we are done since $a_m<m \leq k$. Otherwise $m=\lceil{b \varphi} \rceil$ for some $b \in \mathbb{Z}^+$, so $a_m=\lceil{b \varphi ^2 } \rceil \leq \lceil{\lceil b \varphi \rceil \varphi } \rceil=\lceil{m \varphi } \rceil=k+1$. Since $k+1=\lceil{m \varphi} \rceil \not =\lceil{b \varphi ^2 } \rceil = a_m$ (Partition), we now have the desired inequality $a_m \leq k$.
Case 2: $k+1=\lceil{m \varphi ^2} \rceil=m+\lceil{m \varphi} \rceil$ for some $m \in \mathbb{Z}^+$. Then $a_{k+1}=\lceil{m \varphi} \rceil=k+1-m$.
Now $k+1=m \varphi ^2 +1-\{m \varphi ^2 \}$.
As we have a partition, $k+1$ cannot be written in the form $\lceil{i \varphi} \rceil$. Thus $\exists c \in \mathbb{Z}^+$ such that $\lceil{c \varphi} \rceil<k+1<\lceil{(c+1) \varphi} \rceil$. (Since $k>1$.)
This gives $\lceil{c \varphi} \rceil=k, \lceil{(c+1) \varphi} \rceil=k+2$.
Thus: $k=c \varphi +1-\{c \varphi \}, k+2=(c+1) \varphi +1-\{(c+1) \varphi \}$, so \begin{align} c<c+\frac{1-\{c \varphi \}}{\varphi}=\frac{k}{\varphi}=m \varphi -\frac{\{m \varphi ^2 \}}{\varphi}<m \varphi & <m \varphi +\frac{1-\{m \varphi ^2 \}}{\varphi} \\ & =\frac{k+1}{\varphi} \\ & =c+1-\frac{\{(c+1) \varphi \}}{\varphi} \\ & <c+1 \end{align}
We get $\lceil \frac{k}{\varphi} \rceil =\lceil m \varphi \rceil =\lceil \frac{k+1}{\varphi} \rceil =c+1$, so $k+1=m+c+1, a_{k+1}=c+1$.
$\sum\limits_{i=1}^{k+1}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil +a_{k+1}=k(c+1)+(c+1)=(k+1)(c+1)=(k+1) \lceil{\frac{k+1}{\varphi}} \rceil$
Minimality: Also note that $a_{k+1}=k+1-m<k+1$, so $a_{k+1}$ is the smallest integer satisfying the divisibility relation, and because we have a partition, $a_{k+1} \not =a_i \, \forall i$.
We are thus done by induction. Now, since $x_n$ is unique and $a_n$ satisfies the given conditions, $x_n=a_n \, \forall n \in \mathbb{Z}^+$ and we are done. Both i) $x_n$ is surjective and ii) $x_{x_n}=n$ follow trivially.