Recamán's Sequence Completeness

Completeness of Recamán's Sequence

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

Set $a_0=0$. For $n\geq1$, take $a_n=a_{n-1}-n$ when that number is positive and has not appeared among $a_0,\ldots,a_{n-1}$; otherwise take $a_n=a_{n-1}+n$. Repetitions arising from the addition case are permitted. The target is $\{a_n:n\geq0\}={\mathbb{Z}}_{\geq0}$, not monotonicity of this highly nonmonotone sequence. [S1] [S2]

Statement recorded in the supplied source.

Does every nonnegative integer appear in Recamán's sequence? [S1]

Short English statement

Does the greedy subtract-if-new, otherwise-add rule eventually visit every nonnegative integer?

Research attempt

Scope and source check.

The subtraction candidate must be positive and unused; the addition case has no unused-value test. In particular repeated addition outputs must not be rejected. The community-maintained sequence record [E1] was inspected on 1 October 2026 for the convention and initial terms. The analysis below uses the exact supplied recurrence and distinguishes unboundedness of the values from coverage of all values.

Three elementary invariants.

Induction gives $a_n>0$ for $n\ge1$, because an accepted subtraction is positive and an addition is positive. Also \[ |a_n-a_{n-1}|=n,\qquad 0\le a_n\le\frac{n(n+1)}2. \] The upper bound follows by always taking the larger possible update, starting at zero. Modulo two, addition and subtraction agree, giving \[ a_n\equiv\frac{n(n+1)}2\pmod2. \] Thus the value parity has period four in the index. This restricts possible hitting times of a fixed value but leaves infinitely many admissible indices for either parity.

The sequence is unbounded. If all values were at most $M$, every consecutive difference would be at most $M$ in absolute value, contrary to $|a_n-a_{n-1}|=n$ for $n>M$. This proof is unconditional and does not use the novelty test. It does not establish that any particular small missing value will ever be visited.

An exact late first-hit condition.

Fix $m>0$ and suppose it has not appeared by time $n-1$. A subtraction at time $n$ reaches it exactly when \[ a_{n-1}=n+m. \] If this equality holds, the subtraction is positive and unused by hypothesis, so it is necessarily taken. For $n\ge\max\{m,2\}$, an addition cannot first reach $m$, since $a_{n-1}>0$ and hence $a_{n-1}+n>m$. The initial exception is $a_1=1$. Therefore after finitely many early times the question of ever reaching $m$ is exactly a moving-line intersection problem: must $a_{n-1}$ eventually equal $n+m$ while $m$ is missing?

In particular if a value $m$ is never reached, the graph of the sequence avoids that line at every candidate late time. Unboundedness gives no such intersection automatically. Even a sequence with infinitely many values above and below a line can jump over its integer heights, since the jumps here grow with $n$ rather than being unit steps.

What the least-missing-value argument actually says.

If $m$ is the least positive value absent from a finite prefix, then all positive subtraction candidates below $m$ have already been used. At a time when such a candidate occurs, the rule therefore takes the addition instead. This creates upward jumps near an already-filled region, but supplies no monotone decrease of the distance to the boundary $m$. The next step size changes, and the used set remembers all earlier visits. A proof that "the process must fill the next hole" needs an invariant controlling that changing distance; the recurrence alone has not supplied it.

One can track the moving coordinate $b_n=a_n-n$. The two updates are \[ b_n=b_{n-1}-(n+1)\quad\hbox{after subtraction},\qquad b_n=b_{n-1}+(n-1)\quad\hbox{after addition}. \] A late first hit of $m$ is equivalent to $b_{n-1}=m+1$. These updates still have unbounded jump sizes and history-dependent signs. They do not form a fixed finite-state walk to which recurrence in a finite graph can be applied.

Repetitions are part of the actual sequence.

The recurrence gives $a_{20}=42$ and $a_{24}=42$. At time $24$ the subtraction from $a_{23}=18$ would be negative, so the addition returns to forty-two despite its earlier appearance. A program that disallows this repeated output computes a different sequence and cannot test the catalogue target. The seen set is used only to decide whether a positive subtraction is legal; it is updated after either type of step.

Executed computation.

The script performs the exact recurrence through $n=100000$, retaining the seen set and verifying the parity identity at every step. It obtains $74253$ distinct values including zero, $25748$ repeated steps, and maximum value $592216$. The least missing nonnegative integer in that finite prefix is $61$. This last statement concerns the prefix, not the infinite sequence: no permanence of the missing value is claimed. The first twenty-six terms and these statistics are stored in results_second.json; the reproducer is checks_second.py under _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/.

Remaining gap and outcome.

The attempt proves unboundedness and an exact criterion for a late first visit, but no mechanism forces all those moving-line intersections. It also gives no certified permanently missing integer. Outcome: UNRESOLVED. Long growth, many distinct values, and a changing least missing value remain compatible with either outcome.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1267 (NT-060), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 OEIS Wiki, Recamán's sequence $A005132$. https://oeis.org/wiki/Recam%C3%A1n%27s_sequence. Bibliographic information from the supplied record.

• E1 OEIS Foundation and contributors, A005132, Recamán's sequence. https://oeis.org/A005132. Sequence definition and initial-term record inspected 1 October 2026; the deductions and finite simulation above are supplied independently.