Recamán’s Sequence

Start at 0 and make jumps whose lengths increase by one: first 1, then 2, then 3, and so on. At move $n$, subtract $n$ if the result is positive and has not appeared before. Otherwise add $n$, whether or not that forward result has already appeared.

The first moves give 0 → 1 → 3 → 6. The next jump has length 4, and 6 − 4 = 2 is a new positive value, so the sequence moves back to 2. At the following jump, 2 − 5 would be negative, so it moves forward to 7 instead.

Each move is drawn as a half-circle from its starting value to its destination. The arcs alternate above and below the number line so adjacent moves are easier to follow. The arc's height is a drawing convention; the rule uses only the visited whole numbers and the current jump length.

Two ingredients, and it is worth separating them because only one is doing the interesting work.

The step grows. At move 100 the sequence jumps by 100. It can never settle into a rhythm, because the rhythm changes every time.

The rule has a memory. "Not already visited" means every future move depends on the entire history. This is unusual: most rules in this guide are maps, where the next value depends only on the current one. Kaprekar's routine does not care how you arrived at 3524. Recamán's rule cares about everything.

That distinction is testable rather than rhetorical, and this page tests it. Switch the rule to Forget - go back whenever the landing place is positive, visited or not - and the arithmetic is untouched while the picture collapses into a zigzag over a small range.

So: not the arithmetic. The memory.

Look again at what a forward move means.

The rule always prefers to go back. It goes forward only when it is blocked - either because going back would leave the non-negative integers, or because going back would repeat a value. So the sequence of directions is not a pattern the rule generates. It is a record of when the history got in the way.

This has an immediate consequence, and it is the one that makes the drawing worth looking at:

A backward move can never land on a value the sequence has already reached. Every repeated value is therefore a forward move arriving somewhere it had been before.

Repeats exist - 42 is reached at move 20 and again at move 24 - and every one of them is a collision the rule could not avoid rather than one it chose.

Define $a_0=0$ and, for $n\ge 1$,

Then:

1. Every $a_n$ is a non-negative integer, and $a_n\le \frac{n(n+1)}{2}$. (From a start $a_0$ other than 0, as the laboratory allows, the bound is $a_0+\frac{n(n+1)}{2}$ - what is really bounded is the displacement from the start.)
2. The map $n\mapsto a_n$ is not injective.
3. Whether $\{a_n:n\ge 0\}={\mathbb{Z}}_{\ge 0}$ - whether every non-negative integer appears - is open.

Statement 3 is the one people care about, and it is the one nobody can answer.

Non-negativity and the bound. Each move changes the value by exactly $n$, so all terms are integers. A backward move is taken only when the result is positive, and a forward move only increases the value, so no term is ever negative. After $n$ moves the total distance travelled is at most $1+2+\cdots +n=\frac{n(n+1)}{2}$, and the sequence starts at 0, so $a_n$ cannot exceed that. ∎

Non-injectivity. By exhibiting a repeat: $a_{20}=a_{24}=42$. A single example settles an existence claim completely, which is the one situation where computation and proof coincide. ∎

Appearance. No proof is known, in either direction. Note what is not available here: the argument that saves the happy numbers page - the map cannot outrun itself, so the space closes and enumeration finishes - has no analogue. This sequence is unbounded, so there is no finite region to enumerate and no amount of computing that could finish the job.

The gaps you can see are not evidence. With the original rule and a few hundred terms, the smallest number never reached is 19. It is very tempting to treat a persistent gap as a discovery. It is not: the sequence is unbounded and keeps returning to small values, so a number absent after 1,200 moves may well arrive after a million. The literature reports the first seriously missing candidate as a six-figure number, far beyond anything this page computes.

Some gaps are structural rather than accidental. Switch the step sizes to the odd numbers. Every step now changes the parity, so the terms alternate from wherever they began: $a_n\equiv a_0+n(\mathrm{mod}2)$, which for the original start of 0 reads $a_n\equiv n$. No value is ruled out of the sequence altogether - both parities still turn up - but each one can now only be reached on moves of its own parity, which is a constraint the original rule does not have. That is worth having next to the previous paragraph, because a limitation you can prove and a gap left by a short run look identical in the picture.

The picture is a choice. The arcs, their radii, and which side of the line they fall on are drawing decisions, not facts about the sequence. Plot the same integers as an ordinary line graph and most of the magic evaporates. This is not a debunking - the arc drawing genuinely reveals the alternation between forced and free moves - but a visualisation is an argument, and an argument should be labelled as one.

What this page cannot do. It draws at most 1,200 moves. The open question is about all of them.