# Bijection $f\colon\mathbb{N}\to\mathbb{N}$ with $f(0)=0$ and $|f(n)-f(n-1)|=n$

Let $$\mathbb{N}=\{0,1,2,\ldots\}$$. Does there exist a bijection $$f\colon\mathbb{N}\to\mathbb{N}$$ such that $$f(0)=0$$ and $$|f(n)-f(n-1)|=n$$ for all $$n\geq1$$?

The values $$f(1)=1$$, $$f(2)=3$$, and $$f(3)=6$$ are forced. After that, you might choose to continue with

$$\begin{array}{c|c}n&f(n)\\\hline0&0\\1&1\\2&3\\3&6\\4&2\end{array}\qquad\begin{array}{c|c}n&f(n)\\\hline5&7\\6&13\\7&20\\8&28\\9&37\end{array}\qquad\begin{array}{c|c}n&f(n)\\\hline10&27\\11&16\\12&4\\13&17\\14&31\end{array}$$

Here, after deceasing to $$f(4)=2$$, the next smallest remaining value was 4. I chose to continue to increase until there was a clear way down to 4 and back up.

As mentioned in the comments, the greedy algorithm where you decrease whenever you can is given by sequence A005132 in the OEIS. However, this sequence gets stuck at $$f(20)=42$$, $$f(21)=63$$, $$f(22)=41$$, $$f(23)=18$$ as there is no possible value for $$f(24)$$. Also, this greedy approach would take longer to get to the value $$4$$.

In general, if $$k$$ is the smallest number that you haven't hit yet then the strategy of increasing until there is a clear way down to $$k$$ and a clear way back up seems to be a reasonable strategy. This is the strategy employed by the table above. Unfortunately, Symlic's answer shows that this strategy doesn't work (in fact, it will never hit the value 5). Therefore, a more sophisticated strategy is required.

If you instead consider $$f\colon\mathbb{N}\to\mathbb{Z}$$ then alternating between increasing and decreasing is a valid bijection. However, employing this technique in original situation will often lead to you getting stuck in coming back up.

• related sequence – lulu Jun 21 '18 at 20:47
• Why did you set $f(8)=20$? $12$ was available... is there a clear (automatable) rule which you followed? The sequence I linked to above follows the rule "go down if the slot is available, otherwise go up." Alas, the sequence you get that way is neither injective nor surjective (though it sure looks surjective). – lulu Jun 21 '18 at 20:56
• If you set $f(8)=12$ then it takes more time to hit $4$. You could think of the rule as: Continue to increase until it is possible to "go down until you hit the target and then go up until you are in the clear". – Thomas Browning Jun 21 '18 at 20:57
• But then you are stuck as you would have to go back up to $10$. – Thomas Browning Jun 23 '18 at 21:28
• The composition $g\circ f$ probably will not satisfy the condition $|g(f(n))-g(f(n-1))|=n$ for all $n\geq1$. – Thomas Browning Jun 26 '18 at 5:01

The good news is that your function will never get stuck. The bad news is that the reason quite easy: your function will never have value 5. Let see how to get it.

Suppose there are $k$ and $\ell$ such that $f(\ell) = 5$, and $f(n) = f(n - 1) + n$ for all $13 \le n \le k$, and $f(n) = f(n - 1) - n$ for all $k < n \le l$. Then $$f(k) = 4 + \sum_{n = 13}^k n = 4 + \frac{k(k + 1)}2 - 78 = \frac{k(k + 1)}2 - 74$$ and $$5 = f(\ell) = f(k) - \sum_{n = k + 1}^{\ell} n = \frac{k(k + 1)}2 - 74 - \frac{\ell(\ell + 1)}2 + \frac{k(k + 1)}2,$$ i. e., $$k(k + 1) = 79 + \frac{\ell(\ell + 1)}2.$$ It is easy to see that $\frac{\ell(\ell + 1)}2 \bmod 9 \in \{\,0, 1, 3, 6\,\}$ and $k(k + 1) \bmod 9 \in \{\,0, 2, 3, 6\,\}$. Since $79 \bmod 9 = 7$ we get a contradiction, which means that there are no such $k$ and $\ell$.

• Very nice! This shows that a more sophisticated choice of $f$ is required. – Thomas Browning Jun 27 '18 at 1:54

Such a bijection exists.

It is convenient to assume that we are looking for an infinite jump sequence on $\mathbb N$ starting from $0$, never returning to a previous position and ultimately filling all $\mathbb N$. The distance of the $n$th jump is restricted to be $n$, we can choose only its direction. So our task is to find the appropriate sequence $\mathcal D$ of jump directions like $\mathcal D=(+\!+\!+\!-\!+\dots)$, where $+$ means jumping $n$ positions forward and $-$ means jumping $n$ positions backward, $n$ is the number of the sign in the sequence. The term state below stands for a pair $(n, m)$, where $n \in \mathbb N$ is time and $m \in \mathbb N$ is position (it results from adding $\pm n$ to a previous position when $n>0$ and corresponds to $f(n)$ in the original statement). A state $(n, m)$ is called safe if $m$ is the largest position up to the time $n$ (i.e. $f(t)<f(n)$ for all $t<n$).

The solution relies on two jump patterns. Lower index $k \in \mathbb N$ after some subpattern $\mathcal P$ (which may be a single sign or a bracketed group) below means that $\mathcal P$ must be repeated $k$ times.

## Saturator

Pattern: $\mathcal S_k = +_2(-+)_k$

Prerequisite: safe state $(n, m)$.

Parameter: $k, \; 0 \le k \le n$.

Result: safe state $(n+2k+2, m+2n+k+3)$.

Comment: the table below summarizes state change during the pattern realization. Position never goes into the "unsafe" area below $m$.

$$\begin{array}{|c|ccc|} \hline \text{Time (from ... to)} && \;\text{Position}\\ n+\bullet & m+\bullet & m+n+\bullet & m+2n+\bullet\\ \hline 0 \,\dots\, 2 & \color{lime}{0} & 1 & 3\\ 2i+3 \,\dots\, 2i+4 && -i & i+4\\ \hline \text{min pos} & 0 & -k+1 &3\\ \text{max pos} & 0 & 1 & \color{lime}{k+3}\\ \hline \end{array}$$

Positions are grouped in columns according to $n$-driven bands. For brevity, common summands like $n + \bullet$ are put into header, they must be added to what's written beneath. The line containing $i$, where $0 \le i < k$, describes a cycle repeated $k$ times. As $k \le n$, the bands never intersect. This is also reflected in the last two rows. For example, the minimal position in the second band is $m+n-k+1$, which is greater than the sole position $m$ in the first band.

Particular case: $k=n$. This Saturator, called the complete Saturator and denoted simply by $\mathcal S$, will be used most often. It transforms the safe state $(n, m)$ to the safe state $(3n+2, m+3n+3)$. Looking at the ratio $t = \frac m {n+1}$ for each state, it transforms $t$ to $\frac {m+3n+3} {3n+3}=1 + \frac t 3$. The map $t \to 1 + \frac t 3$ has one fixed point: $t_0 = \frac 3 2$, so starting from any safe state and using $\mathcal S$ an appropriate number of times it is possible to get $t$ as close as needed to $\frac 3 2$.

## Fencer

Pattern: $\mathcal F_k = +(+_3\!-_3)_k\!+_5\!-\!+\!-_6+_6$

Prerequisites: safe state $(n, m)$ and previously unattended position $a = m - (15k+47)$.

Parameter: $k$ (fixed, determined by $a$), $0 \le k < \frac {n-33} 9$.

Result: new safe state, $a$ is attended.

Comment: the table below summarizes state change during the pattern realization. The only position inside "unsafe" area is $a$, which is indicated by the red color.

$$\begin{array}{|c|ccccccc|} \hline \text{Time (from ... to)} &&&& \;\text{Position}\\ n+\bullet & m\!+\!\bullet & m\!+\!n\!+\!\bullet & m\!+\!2n\!+\!\bullet & m\!+\!3n\!+\!\bullet & m\!+\!4n\!+\!\bullet & m\!+\!5n\!+\!\bullet & m\!+\!6n\!+\!\bullet\\ \hline 0 \,\dots\, 1 & \color{lime}{0} & 1\\ 6i+2 \,\dots\, 6i+4 &&& -3i+3 & 3i+6 & 9i+10\\ 6i+5 \,\dots\, 6i+7 && -9i-8 & -3i-1 & 3i+5\\ 6k+2 \,\dots\, 6k+6 &&& -3k+3 & 3k+6 & 9k+10 & 15k+15 & 21k+21\\ 6k+7 \,\dots\, 6k+8 &&&&&& 15k+14 &21k+22\\ 6k+9 \,\dots\, 6k+14 & \color{red}{-15k-47} & -9k-33 & -3k-20 & 3k-8 & 9k+3 & 15k+13\\ 6k+15 \,\dots\, 6k+20 && -9k-32 & -3k-16 & 3k+1 & 9k+19 & 15k+38 & \color{lime}{21k+58}\\ \hline \text{min pos} & -15k-47 & -9k-33 & -3k-20 & \min(5, 3k\!-\!8) & \min (10, 9k\!+\!3) & 15k+13 & 21k+21\\ \text{max pos} & 0 & 1 & 3 & 3k+6 & 9k+19 & 15k+38 & 21k+58\\ \hline \end{array}$$

Two lines containing $i$, where $0 \le i < k$, describe a cycle repeated $k$ times. As $9k+33 < n$, two first bands don't intersect. The same is true for other band pairs. For example, $3k+21<9k+33<n$, thus the second and the third bands don't intersect.

## Sequence construction

We are starting from the safe state $(0, 0)$ and empty $\mathcal D$. The latter will be composed of $\mathcal S_k$ and $\mathcal F_k$ only. The strategy is to use the Fencer pattern repeatedly making "lunges" at the lowest unattended positions. The main purpose of the Saturator pattern is to provide prerequisites for the Fencer. If there is no unattended position below the current one (as it is at the beginning), $\mathcal S$ simply executes until it arrives. Then, after fixing minimal unattended position $a$, the Saturator must increase $m$ such that $m \equiv a+2 \pmod {15}$ and $0 \le \frac {m-a-47} {15} < \frac {n-33} 9 \iff a+47 \le m < \frac 5 3 n + a - 8$. The inequality $a+47 \le m$ can be easily achieved since the Saturator always increases $m$. After that apply the complete Saturator one or more times until the ratio $t=\frac {m'}{n'+1}$ for the next expected pair $(n',m')=(3n_{i-1}\!+\!2, m\!+\!3n_{i-1}\!+\!3)$ becomes lower than $\frac {5 / 3 \, (n'-28) + a - 8} {n'+1}$. This will happen some time because, as noted above, $t_i \to \frac 3 2$, $n_i \to +\infty$ and $\frac 3 2 < \frac 5 3$. To make the Fencer available, apply "almost complete" Saturator $\mathcal S_k$ with $k=n_{i-1}-d$ instead of $k=n_{i-1}$, where $d$ is chosen between $0$ and $14$ such that $m'-d \equiv a+2 \pmod {15}$. Then $n_i=n'-2d \ge n'-28$, $m_i=m'-d$, thus $m_i \le m'<\frac {5 / 3 \, (n'-28) + a - 8} {n'+1} (n'+1) \le \frac 5 3 n_i + a - 8$ and all prerequisites for the Fencer are fulfilled. As the lowest unattended position is greater than $n$ after the $n$th application of the Fencer, any position ultimately will be attended.

• I will have to take some time to go through the details but this looks very promising. – Thomas Browning Jul 1 '18 at 0:08

John McClane's answer is correct. Here is a much clearer writeup.

We construct an infinite sequence $$(x_1,x_2,\dots) \in \{+,-\}^\mathbb{N}$$ so that the associated $$(y_1,y_2,\dots) \in \mathbb{N}^\mathbb{N}$$ formed by $$y_0 = 0$$ and $$y_n := x_1+2x_2+\dots+nx_n$$ for $$n \ge 1$$ has $$\{y_n : n \ge 0\} = \mathbb{N}$$ with no two $$y_n$$'s equal. Note that $$f(n) := y_n$$ is then the desired bijection.

For a finite sequence $$(x_1,\dots,x_n)$$ with associated $$(y_1,\dots,y_n)$$, we say $$(n,y_n)$$ is safe if $$y_j < y_n$$ for $$j < n$$. For $$k \ge 0$$, define sign patterns $$\mathcal{S}_k := +_2(-+)_k$$ and $$\mathcal{F}_k := +(+_3-_3)_k+_5-+-_6+_6$$, where the subscript denotes repetition (e.g. $$(-+)_2 := -+-+$$).

Lemma: Suppose $$(x_1,\dots,x_n)$$ has $$(n,y_n)$$ safe.

(1) For any $$0 \le k \le n$$, if we let $$x_{n+1},\dots,x_{n+2k+2}$$ be $$\mathcal{S}_k$$, we have that $$(n+2k+2,y_{n+2k+2})$$ is safe and $$y_j > y_n$$ for $$n+1 \le j \le n+2k+2$$.

(2) If $$k := \frac{y_n-a-47}{15}$$ is an integer with $$0 \le k < \frac{n-33}{9}$$, then if we let $$x_{n+1},\dots,x_{n+6k+20}$$ be $$\mathcal{F}_k$$, we have that $$(n+6k+20,y_{n+6k+20})$$ is safe, $$y_{j_0} = a$$ for exactly one $$1 \le j_0 \le 6k+20$$, and if $$y_j < y_n$$ for some $$1 \le j \le 6k+20$$, then $$j = j_0$$.

Let's construct $$(x_n)_n$$ (and thus finish the problem) assuming the lemma. Start with $$x_1,x_2 = +,+$$. Suppose that, at some point, we have $$x_1,\dots,x_n$$ constructed with $$(n,y_n)$$ safe, $$n \ge 2$$. Let $$a$$ be the smallest positive integer not in $$\{y_1,\dots,y_n\}$$ (since $$(n,y_n)$$ is safe, such an $$a$$ will exist if and only if we don't have $$\{y_1,\dots,y_n\} = \{1,2,\dots,n\}$$, but we'll certainly never have this, as our construction proceeds). Via an abuse of notation, we let $$\mathcal{S} = \mathcal{S}(n)$$, at index $$n$$, denote $$\mathcal{S}_n$$.

We define $$x_{n+1},x_{n+2},\dots,x_{n'}$$ by repeating $$\mathcal{S}$$ a certain number of times, about to be specified (to make sure we are on the same page, $$x_{n+1},\dots,x_{3n+2}$$ are formed from $$\mathcal{S}_n$$, and then $$x_{3n+3,\dots,9n+8}$$ are formed from $$\mathcal{S}_{3n+2}$$, etc.). We apply $$\mathcal{S}$$ enough times so that (1) $$y_{n'} \ge a+47$$ and (2) $$\frac{y_{n'}}{n'+1} < 1.6$$; (1) is clearly possible, since $$\mathcal{S}$$ increases $$y_j$$ by $$3j+3$$, and (2) is possible, since applying $$\mathcal{S}$$ changes the ratio of $$\frac{y_j}{j+1}$$ to $$\frac{y_j+3j+3}{3j+3}$$ and the map $$t \mapsto 1+\frac{t}{3}$$ iterates closer and closer to $$\frac{3}{2}$$. Finally, choose $$d \in \{0,\dots,14\}$$ so that $$y_{n'}+3n'-d+3-a-47 \equiv 0 \pmod{15}$$, let $$k = n'-d$$, and let $$x_{n'+1},\dots,x_{n'+2k+2}$$ be formed by $$\mathcal{S}_k$$. Let $$n'' = n'+2k+2$$. Note $$y_{n''} \ge y_{n'} \ge a+47$$, and $$\frac{y_{n''}}{n''+1} < 1.6$$, since $$\frac{y_{n'}}{n'+1} < 1.6$$. By construction, $$y_{n''}-a-47 = y_{n'}+2n'+k+3-a-47 = y_{n'}+3n'-d+3-a-47 \equiv 0 \pmod{15},$$ and $$\frac{y_{n''}-a-47}{15} < \frac{n''-33}{9}$$ if and only if $$y_{n''} < \frac{5}{3}n'+a-8$$, but $$\frac{y_{n''}}{n''+1} \le 1.6 \le \frac{\frac{5}{3}n''+a-8}{n''+1}$$ (since $$n'' \ge n'$$ is large). And we also have $$\frac{y_{n''}-a-47}{15} \ge 0$$. Therefore, with $$k = \frac{m-a-47}{15}$$, we may define $$x_{n''+1},\dots,x_{n''+6k+20}$$ by $$\mathcal{F}_k$$ to attain $$a$$ and no other points below $$y_{n''}$$ (by the lemma).

So we first do the above construction with $$n=2$$ and $$a=2$$. We get some $$n''$$, and there will be some other smallest value of $$a$$ not in $$\{y_1,\dots,y_{n''}\}$$. Note that $$(n'',y_{n''})$$ is safe by the lemma (repeatedly). Then do the above construction starting at $$n''$$ with respect to this new $$a$$. Etc., etc.. It is clear that the resulting $$(y_n)_n$$ will cover each positive integer exactly once.

Proof of Lemma:

(1). This is pretty straightforward.

(2). It's easy to see that $$(n+6k+20,y_{n+6k+20})$$ is safe. Really the only proof of the rest of this part of the lemma is just to write everything out explicitly. Here is John's table: $$\begin{array}{|c|ccccccc|} \hline \text{Time (from ... to)} &&&& \;\text{Position}\\ n+\bullet & m\!+\!\bullet & m\!+\!n\!+\!\bullet & m\!+\!2n\!+\!\bullet & m\!+\!3n\!+\!\bullet & m\!+\!4n\!+\!\bullet & m\!+\!5n\!+\!\bullet & m\!+\!6n\!+\!\bullet\\ \hline 0 \,\dots\, 1 & \color{lime}{0} & 1\\ 6i+2 \,\dots\, 6i+4 &&& -3i+3 & 3i+6 & 9i+10\\ 6i+5 \,\dots\, 6i+7 && -9i-8 & -3i-1 & 3i+5\\ 6k+2 \,\dots\, 6k+6 &&& -3k+3 & 3k+6 & 9k+10 & 15k+15 & 21k+21\\ 6k+7 \,\dots\, 6k+8 &&&&&& 15k+14 &21k+22\\ 6k+9 \,\dots\, 6k+14 & \color{red}{-15k-47} & -9k-33 & -3k-20 & 3k-8 & 9k+3 & 15k+13\\ 6k+15 \,\dots\, 6k+20 && -9k-32 & -3k-16 & 3k+1 & 9k+19 & 15k+38 & \color{lime}{21k+58}\\ \hline \end{array}$$

The leftmost column denotes the value of $$j$$ so that the corresponding value in the "position" part of the table shows either $$y_{j-n}-y_n$$, or $$y_{j-n}-y_n-n$$, or $$\dots$$, or $$y_{j-n}-y_n-6n$$. The point is that $$y_{j-n}$$ is less than $$y_n$$ only when it is $$y_n-15k-47$$ (i.e. $$a$$), which just happens once.

• Thanks for taking the time to do this! I'll look over this when I have time. – Thomas Browning Feb 13 at 16:33