/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilRecamán's sequence
Start with $a(0)=0$. At step $n>0$, subtract $n$ from the preceding term when the result is nonnegative and has not appeared earlier; otherwise add $n$.
References:
@[expose] public sectionnamespace OeisA5132Choose the next Recamán value from a finite history and a step size: use the positive unseen subtraction candidate when possible, and the addition candidate otherwise.
def nextTerm (previous : List ℕ) (step : ℕ) : ℕ :=
let current := previous.getLastD 0
if step < current ∧ current - step ∉ previous then current - step else current + stepThe complete list $[a(0),\ldots,a(n)]$ of Recamán values through index $n$.
def sequencePrefix : ℕ → List ℕ
| 0 => [0]
| n + 1 =>
let previous := sequencePrefix n
previous ++ [nextTerm previous (n + 1)]The finite prefix through index $n$ has exactly $n+1$ entries.
@[simp, category API, AMS 11]
theorem prefix_length : ∀ n, (sequencePrefix n).length = n + 1
| 0 => rfl
n:ℕ⊢ (sequencePrefix (n + 1)).length = n + 1 + 1 n:ℕ⊢ (sequencePrefix (n + 1)).length = n + 1 + 1 All goals completed! 🐙Zero remains in every generated prefix.
@[simp, category API, AMS 11]
theorem zero_mem_prefix : ∀ n, 0 ∈ sequencePrefix n
⊢ 0 ∈ sequencePrefix 0 ⊢ 0 ∈ sequencePrefix 0 All goals completed! 🐙
n:ℕ⊢ 0 ∈ sequencePrefix (n + 1) n:ℕ⊢ 0 ∈ sequencePrefix (n + 1) All goals completed! 🐙Recamán's sequence value at index $n$, read from the end of its complete finite prefix.
def a (n : ℕ) : ℕ :=
(sequencePrefix n).getLastD 0
The OEIS nonnegative subtraction condition is equivalent to the strict-positive version used
by nextTerm, because a zero candidate has already appeared in every prefix.
mp n:ℕhle:n + 1 ≤ a nhunseen:a n - (n + 1) ∉ sequencePrefix nhlt:¬n + 1 < a nhzero:a n - (n + 1) = 0⊢ 0 ∈ sequencePrefix n
exact zero_mem_prefix n All goals completed! 🐙
· mpr n:ℕ⊢ n + 1 < a n ∧ a n - (n + 1) ∉ sequencePrefix n → n + 1 ≤ OeisA5132.a n ∧ OeisA5132.a n - (n + 1) ∉ sequencePrefix n rintro ⟨hlt, hunseen⟩ mpr n:ℕhlt:n + 1 < a nhunseen:a n - (n + 1) ∉ sequencePrefix n⊢ n + 1 ≤ a n ∧ a n - (n + 1) ∉ sequencePrefix n
exact ⟨by n:ℕhlt:n + 1 < a nhunseen:a n - (n + 1) ∉ sequencePrefix n⊢ n + 1 ≤ a n omega All goals completed! 🐙, hunseen⟩The prefix at the next index is obtained by appending exactly one recurrence step.
@[simp, category API, AMS 11]
theorem prefix_succ (n : ℕ) :
sequencePrefix (n + 1) =
sequencePrefix n ++ [nextTerm (sequencePrefix n) (n + 1)] := by n:ℕ⊢ sequencePrefix (n + 1) = sequencePrefix n ++ [nextTerm (sequencePrefix n) (n + 1)]
rfl All goals completed! 🐙The public sequence satisfies the defining Recamán recurrence, including its positive and unseen subtraction conditions.
@[simp, category API, AMS 11]
theorem a_succ (n : ℕ) :
a (n + 1) =
if n + 1 < a n ∧ a n - (n + 1) ∉ sequencePrefix n then
a n - (n + 1)
else
a n + (n + 1) := by n:ℕ⊢ a (n + 1) = if n + 1 < a n ∧ a n - (n + 1) ∉ sequencePrefix n then a n - (n + 1) else a n + (n + 1)
simp [a, sequencePrefix, nextTerm] All goals completed! 🐙The public recurrence in the exact nonnegative-subtraction grammar used by OEIS.
@[category API, AMS 11]
theorem a_succ_oeis (n : ℕ) :
a (n + 1) =
if n + 1 ≤ a n ∧ a n - (n + 1) ∉ sequencePrefix n then
a n - (n + 1)
else
a n + (n + 1) := by n:ℕ⊢ a (n + 1) = if n + 1 ≤ a n ∧ a n - (n + 1) ∉ sequencePrefix n then a n - (n + 1) else a n + (n + 1)
simpa only [subtraction_condition_iff] using a_succ n All goals completed! 🐙The current sequence value occurs in the complete prefix through its index.
@[category API, AMS 11]
theorem a_mem_prefix (n : ℕ) : a n ∈ sequencePrefix n := by n:ℕ⊢ a n ∈ sequencePrefix n
cases n with
| zero => zero ⊢ a 0 ∈ sequencePrefix 0 simp [a, sequencePrefix] All goals completed! 🐙
| succ n => succ n:ℕ⊢ a (n + 1) ∈ sequencePrefix (n + 1) simp [a, sequencePrefix, nextTerm] All goals completed! 🐙@[category test, AMS 11]
theorem a_0 : a 0 = 0 := by ⊢ a 0 = 0 decide All goals completed! 🐙@[category test, AMS 11]
theorem a_1 : a 1 = 1 := by ⊢ a 1 = 1 decide All goals completed! 🐙@[category test, AMS 11]
theorem a_2 : a 2 = 3 := by ⊢ a 2 = 3 decide All goals completed! 🐙@[category test, AMS 11]
theorem a_3 : a 3 = 6 := by ⊢ a 3 = 6 decide All goals completed! 🐙@[category test, AMS 11]
theorem a_4 : a 4 = 2 := by ⊢ a 4 = 2 decide All goals completed! 🐙@[category test, AMS 11]
theorem a_5 : a 5 = 7 := by ⊢ a 5 = 7 decide All goals completed! 🐙@[category test, AMS 11]
theorem a_6 : a 6 = 13 := by ⊢ a 6 = 13 decide All goals completed! 🐙The value at index $20$ is $42$, which is repeated later.
@[category test, AMS 11]
theorem a_20 : a 20 = 42 := by ⊢ a 20 = 42
set_option maxRecDepth 100000 in
decide All goals completed! 🐙The value $42$ occurs again at index $24$.
@[category test, AMS 11]
theorem a_24 : a 24 = 42 := by ⊢ a 24 = 42
set_option maxRecDepth 100000 in
decide All goals completed! 🐙Recamán's sequence is not injective: its entries at indices $20$ and $24$ are both $42$.
@[category test, AMS 11]
theorem not_injective : ¬ Function.Injective a := by ⊢ ¬Function.Injective a
intro h h:Function.Injective a⊢ False
have : (20 : ℕ) = 24 := h (a_20.trans a_24.symm) h:Function.Injective athis:20 = 24⊢ False
omega All goals completed! 🐙“I conjecture that every number eventually appears” — N. J. A. Sloane, OEIS A005132.
Sloane later added that he was no longer sure every number appears. The coverage question remains open and is formalized here as surjectivity onto the natural numbers.
@[category research open, AMS 11]
theorem conjecture : Function.Surjective a := by ⊢ Function.Surjective a
sorry All goals completed! 🐙end OeisA5132