Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$
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.
I think it is inevitable here to just pose an expression for the solution and then prove that it satisfies the requirements, rather than deduce the solution directly form the requirements. So I'll use the form of the solution that was suggested; on the other hand I will prove everything about it directly rather than refer to theory.
The question discriminates against $0$, denying it citizenship of the natural numbers, and this bias (for me) complicates both formulae and understanding. Therefore I'll adapt the question as follows by first proclaiming $\def\N{\mathbf N}0\in\N$ (naturalisation of $0$), and then shifting everything one step down: $a_i=x_{i+1}-1$ for all $i\in\N$. Then the following formulation is clearly equivalent to the question: the sequence $(a_i)_{i\in\N}$ is determined the requirement that each $a_i\in\N$ is minimal such that $a_i\neq a_j$ for $0\leq j<i$, and $a_0+a_1+\ldots+a_i$ is divisible by $i+1$ (in particular one has $a_0=0$). Show that the map $i\mapsto a_i$ is an involution of $\N$, in other words $a_{a_i}=i$ for all $i\in\N$ (this of course implies that the map is surjective).
I will use floor and ceiling functions extensively; also I'll denote the complementary fractional part $\def\dn#1{\lfloor#1\rfloor}\def\up#1{\lceil#1\rceil}\up x-x$ of a real number $x$ by $\def\cfr#1{\operatorname{cf}(#1)}\cfr x$, and the golden ratio by $\phi$. The latter satisfies $1+\phi=\phi^2$ and therefore also $1/\phi+1=\phi$ and $1/\phi^2+1/\phi=1$, which identities will often be used without mention.
For an integer $k>0$ two complementary conditions will be important. The condition denoted $\def\lo{\operatorname{low}}\lo(k)$ will be said to hold if $$ \cfr{k\phi}=\cfr{k/\phi}<1/\phi=1-1/\phi^2 \quad\text{or equivalently}\quad \cfr{k/\phi^2}>1/\phi^2=1-1/\phi $$ while the condition denoted $\def\hi{\operatorname{high}}\hi(k)$ will be said to hold if $$ \cfr{k\phi}=\cfr{k/\phi}>1/\phi=1-1/\phi^2 \quad\text{or equivalently}\quad \cfr{k/\phi^2}<1/\phi^2=1-1/\phi $$ (the equivalences hold because $\cfr{k\phi}+\cfr{k/\phi^2}=1$). The cases are mutually exclusive, and equality cannot happen since that would mean $(k+1)/\phi\in\mathbf N$, which is impossible because $\phi$ is irrational.
When $\lo(l)$, then putting $n=\up{l/\phi}$ one has $\cfr{l/\phi}=n-l/\phi<1/\phi$, and so $n\phi-l=\phi(n-l/\phi)<1$ whence $l=\dn{n\phi}$; conversely $\lo(\dn{n\phi})$ holds for every integer $n>0$. Similarly when $\hi(h)$, then putting $n=\up{h/\phi^2}$ one has $\cfr{h/\phi^2}=n-h/\phi^2<1/\phi^2$, so $n\phi^2-h=\phi^2(n-h/\phi^2)<1$ whence $h=\dn{n\phi^2}$; conversely $\hi(\dn{n\phi^2})$ holds for every integer $n>0$.
Now define $(a_i)_{i\in\N}$ explicitly by $$ a_i= \begin{cases} 0 & \text{if $i=0$,} \\ \up{i\phi}=i+\up{i/\phi} & \text{if $\lo(i)$,} \\ \dn{i/\phi}=i-\up{i/\phi^2} & \text{if $\hi(i)$.} \\ \end{cases} $$ Writing indices $l$ with $\lo(l)$ as $l=\dn{n\phi}$ we get $a_l=l+n=\dn{n\phi+n}=\dn{n\phi^2}$. Similarly writing indices $h$ with $\hi(h)$ as $h=\dn{n\phi^2}$, we get $a_h=h-n=\dn{n\phi^2-n}=\dn{n\phi}$. We see that $$ a_{\dn{n\phi}}=\dn{n\phi^2} \quad\text{and}\quad a_{\dn{n\phi^2}}=\dn{n\phi} \qquad\text{for all $n\in\N$,} $$ and since this covers all cases, clearly $i\mapsto A_i$ is an involution of $\N$.
On to the divisibility condition, which follows from the following stronger fact. Although straightforward by induction, it does not really give any deep understanding why this divisibility holds.
Lemma 1 For all $k\in\N$ one has $\sum_{i<k}a_i=k\dn{k/\phi}$.
Proof by induction on $k$. For $k=0$ the sum is empty and the right hand side is $0$. Now assume the lemma for $k$, deduce it for $k+1$. If $\hi(k)$, then $\phi\up{k/\phi}-k>1$ whence $\up{k/\phi}>(k+1)/\phi$ and $\dn{(k+1)/\phi}=\dn{k/\phi}$; also $a_k=\dn{k/\phi}$ in this case, and so $$ \sum_{i\leq k}a_i=k\dn{k/\phi}+\dn{k/\phi} =(k+1)\dn{k/\phi}=(k+1)\dn{(k+1)/\phi}. $$ If on the other hand $\lo(k)$, then $\phi\up{k/\phi}-k<1$ whence $\up{k/\phi}<(k+1)/\phi$ and $\dn{(k+1)/\phi}=\dn{k/\phi}+1$; also $a_k=\up{k\phi}$ in this case, and so $$ \sum_{i\leq k}a_i=k\dn{k/\phi}+\up{k\phi} =k\dn{k/\phi}+\dn{k/\phi}+1+k=(k+1)(\dn{k/\phi}+1)=(k+1)\dn{(k+1)/\phi}. $$
Finally, to show that each $a_i$ is the minimal number to satisfy the requirements of injectivity and divisibility, the following will be used.
Lemma 2 Whenever $0\leq i<\dn{k/\phi}$ one has $i\in\{a_0,a_1,\ldots,a_{k-1}\}$; moreover $\dn{k/\phi}\in\{a_0,a_1,\ldots,a_{k-1}\}$ holds if and only if $\lo(k)$.
Proof. From $i\leq\dn{k/\phi}-1$ and $a_i\in\{\up{i\phi},\dn{i/\phi}\}$ it follows (using $\phi>1$) that $a_i<k$, so $i=a_{a_i}\in\{a_0,a_1,\ldots,a_{k-1}\}$. Similarly for $i=\dn{k/\phi}$ one gets $a_i\leq k$, so we will have $\dn{k/\phi}\in\{a_0,a_1,\ldots,a_{k-1}\}$ unless $a_i=k$. But $a_i=k=a_{a_k}$ means that $i=a_k$ while we have $i<k$, so this can only occur if $a_k<k$, that is if $\hi(k)$; conversely if $\hi(k)$ then $i=\dn{k/\phi}=a_k$ and indeed $a_i=k$.
Now to wrap everything up, the sequence $(a_i)_{i\in\N}$ defines an involution of $\N$ that by lemma $1$ satisfies the divisibility condition. To show that each $a_k$ is minimal to satisfy the divisibility condition and distinctness from previous values $a_i$, note first that unless $\lo(k)$ holds, the value $a_k=\dn{k/\phi}<k+1$ is the first one in its congruence class modulo $k+1$, so divisibility alone shows it is minimal. When $\lo(k)$ does hold, lemma $2$ shows that all values $i\leq\dn{k/\phi}$ are already present among the previous values $a_0,a_1,\ldots,a_{k-1}$. But in this case $a_k=\up{k\phi}=\dn{k/\phi}+k+1$ is the second one in its congruence class modulo $k+1$, after the forbidden value $\dn{k/\phi}$, so one has minimality here as well.
Addendum Lemma 2 was only used for a small part above (just the case $i=\dn{k/\phi}$). However its full strength is useful to prove that the pairs $(k,a_k)$ also form the set of cold positions (safe pairs, losing positions) in the game of Wijthoff's Nim, where players take turns modifying a pair of natural numbers, decreasing either one of them, or both by the same amount, and a player incapable of moving (in position $(0,0)$) loses. Positions are classified inductively as cold/hot by: $(0,0)$ is cold; any position from which one can move to a cold position is hot; any position where one can move only to hot positions is cold. The fact that $\{\,(k,a_k)\mid k\in\N\,\}$ is the set of cold positions for this game translates into the following statement.
Proposition $(a_i)_{i\in\N}$ is the lexicographically minimal sequence for which the map $i\mapsto a_i$ is injective $\N\to\N$, and the map $i\mapsto a_i-i$ is injective $\def\Z{\mathbf Z}\N\to\Z$.
Proof. Since $\dn{n\phi^2}-\dn{n\phi}=n$, one easily sees that both maps are in fact bijections. Establishing minimality requires a bit more work. Lemma 2 shows that when $\hi(k)$ holds, the value $a_k=\dn{k/\phi}$ is the first value not yet used. For the case $\lo(k)$, first observe that the values $a_i-i$ for $0\leq i<k$ form a contiguous segment of $\Z$: the value $k=0$ occupies $0$, the values $0<l<k$ with $\lo(l)$ are $l=\dn{n\phi}$ running through $0<n<k/\phi$ and occupy the corresponding positive values $\dn{n\phi^2}-\dn{n\phi}=n$, while the values $0<h<k$ with $\hi(h)$ are $h=\dn{n\phi^2}$ running through $0<n<k/\phi^2$, and occupy the corresponding negative values $\dn{n\phi}-\dn{n\phi^2}=-n$. Thus there are $k$ successive values $a_i-i$ that are forbidden for $a_k-k$, and the actual value $a_k=\up{k\phi}$ occupies the first positive free value $\up{k\phi}-k=\up{k/\phi}$. This means that to prove minimality in this case, it suffices to exclude as candidates for $a_k$ the values up to $a_k-(k+1)=\up{k\phi}-k-1=\dn{k/\phi}$ inclusive, but this is just what lemma 2 does.
This isn’t even a start on a solution; it’s merely some observations that might be useful (or at least of interest) and that are far too long for a comment.
I’ll write $x(n)$ for $x_n$. Something very interesting happens if we write out $n$ and $x(n)$ in a modified Zeckendorf notation. The modification is that I will write
$$n=\sum_{k\ge 1}e_kF_k\;,$$
where each $e_k\in\{0,1\}$, and if the standard representation, which does not use $F_1$, has $e_2=1$, I permit both $e_2=1,e_1=0$ and $e_2=0,e_1=1$. The choice will not, however, be random.
First, here are the first $19$ values of $x(n)$, marked up to show that to this point there is no counterexample to the claim that $x\big(x(n)\big)=n$ for $n\in\Bbb Z^+$.
$$\begin{array}{r} n:&1&\color{red}{2}&\color{red}{3}&\color{blue}{4}&\underline{5}&\color{blue}{6}&\color{green}{7}&\underline{8}&\color{cyan}{9}&\color{magenta}{10}&\color{green}{11}&\color{purple}{12}&\tiny{13}&\color{cyan}{14}&\tiny{15}&\color{magenta}{16}&\tiny{17}&\tiny{18}&\color{purple}{19}\\ x_n:&1&\color{red}{3}&\color{red}{2}&\color{blue}{6}&\underline{8}&\color{blue}{4}&\color{green}{11}&\underline{5}&\color{cyan}{14}&\color{magenta}{16}&\color{green}{7}&\color{purple}{19}&\tiny{21}&\color{cyan}{9}&\tiny{24}&\color{magenta}{10}&\tiny{27}&\tiny{29}&\color{purple}{12} \end{array}$$
Here is the same table in modified Zeckendorf notation:
$$\begin{array}{r|r|r|r|c|c} n&x(n)&n_{\text{Zeck}}&x(n)_{\text{Zeck}}&\text{Shift}&\text{Fibonacci numbers}\\ \hline 1&1&10&1&\to&F_2,F_1\\ 2&3&100&1000&\leftarrow&F_3,F_4\\ 3&2&1000&100&\to&F_4,F_3\\ 4&6&1001&10010&\leftarrow\\ 5&8&10000&100000&\leftarrow&F_5,F_6\\ 6&4&10010&1001&\to\\ 7&11&10100&101000&\leftarrow\\ 8&5&100000&10000&\to&F_6,F_5\\ 9&14&100001&1000010&\leftarrow\\ 10&16&100100&1001000&\leftarrow\\ 11&7&101000&10100&\to\\ 12&19&101001&1010010&\leftarrow\\ 13&21&1000000&10000000&\leftarrow&F_7,F_8\\ 14&9&1000010&100001&\to\\ 15&24&1000100&10001000&\leftarrow\\ 16&10&1001000&100100&\to\\ 17&27&1001001&10010010&\leftarrow\\ 18&29&1010000&10100000&\leftarrow\\ 19&12&1010010&101001&\to \end{array}$$
The choice of $F_1$ or $F_2$ in the representation of $n$ is determined by the direction of shift. If we replace $\to$ by $0$ and $\leftarrow$ by $1$, the Shift column becomes
$$0101101011011010110\;,$$
which is the beginning of the Fibonacci word, OEIS A096270, that is the fixed point of the map $0\mapsto01,1\mapsto011$.
Not an answer, but it might help somebody. I can't prove this, it is observation. With $\phi = \frac {1+\sqrt 5}2$, the naturals greater than $1$ are partitioned into pairs $\lceil n\phi \rceil$ and $\lceil n\phi^2 \rceil$. This is a partitioning as $\frac 1\phi + \frac 1{\phi^2}=1$. Then $a_{\lceil n\phi \rceil}=\lceil n\phi^2 \rceil$ and $a_{\lceil n\phi^2 \rceil}=\lceil n\phi \rceil$. The gap between them the elements of the pair is $n$, as $\phi^2=1+\phi$. I can't relate this to the divisibility test.
See this paper, A Curious Bijection on Natural Numbers by B. J. Venkatachala in Journal of Integer Sequences, Vol. 12 (2009).
Here are some interesting patterns:
The sequence
$$ a_n = \begin{cases} x_n & x_n < n \\ x_n - n & x_n \geq n \end{cases} $$
satisfies $a_{n+1} - a_n \in \{ 0, 1 \}$.
If $n_i$ is the sequence of indices where $x_{n_i} \geq {n_i}$, then $x_{n_i} = n_i + i$. (starting with $n_0 = 1$)
If $x_n < n$, then $x_{n+1} = (n+1) + x_n$
Here are some more observations that might point towards a more elementary solution. Let $X_n$ denote $\sum_{i=1}^n x_n$. We have the following values:
$$\begin{array}{rrlrr} n & x_n & & X_n & X_n/x_n \\ 1 & 1 & & 1 & 1 \\ 2 & \not1 & 3 & 4 & 2 \\ 3 & 2 & & 6 & 2 \\ 4 & \not2 & 6 & 12 & 3 \\ 5 & \not3 & 8 & 20 & 4 \\ 6 & 4 & & 24 & 4 \\ 7 & \not4 & 11 & 35 & 5 \\ \end{array} $$
Here I have written all of the candidates for $x_n$ and crossed out the non-unique ones. Note that the sequence of candidates seems to be the same as the sequence of factors on the right. Certainly $X_{n-1}/(n-1)$ is a candidate for $x_n$, since $X_{n-1}=a(n-1)$ gives $X_{n-1}+ X_{n-1}/(n-1) =an$. If we knew $x_n < 2n$ then we could prove both that it it the smallest candidate and that you need to add at most one copy of $n$. This would lead to surjectivity since the factors in the right column would go up by at most 1.
That seems true but I can't prove it.
