/-
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 FormalConjecturesUtilTripling until the seed's digits reappear
Starting with the least positive integer not used previously, repeatedly triple it and stop the block at the first positive power whose decimal expansion contains the seed's digits. Then repeat from the new least missing positive integer.
References:
@[expose] public sectionnamespace OeisA331631
The decimal digits of seed occur contiguously in the decimal digits of value.
def ContainsSeed (seed value : ℕ) : Prop :=
(Nat.digits 10 seed).IsInfix (Nat.digits 10 value)@[category test, AMS 11]
theorem contains_seed_12_5123 : ContainsSeed 12 5123 := ⊢ ContainsSeed 12 5123
All goals completed! 🐙@[category test, AMS 11]
theorem not_contains_seed_12_5213 : ¬ContainsSeed 12 5213 := ⊢ ¬ContainsSeed 12 5213
⊢ ¬[2, 1] = []
All goals completed! 🐙
exponent is the first positive tripling exponent whose value contains the seed.
def StopsAt (seed exponent : ℕ) : Prop :=
0 < exponent ∧
ContainsSeed seed (seed * 3 ^ exponent) ∧
∀ j, 0 < j → j < exponent → ¬ContainsSeed seed (seed * 3 ^ j)@[category test, AMS 11]
theorem not_stops_at_1_0 : ¬StopsAt 1 0 := ⊢ ¬StopsAt 1 0
All goals completed! 🐙The complete block through its first successful positive tripling exponent.
def blockValues (seed exponent : ℕ) : List ℕ :=
(List.range (exponent + 1)).map fun j ↦ seed * 3 ^ jA block includes its seed and every product through the stopping exponent.
@[category API, AMS 11]
theorem block_values_length (seed exponent : ℕ) :
(blockValues seed exponent).length = exponent + 1 := seed:ℕexponent:ℕ⊢ (blockValues seed exponent).length = exponent + 1
All goals completed! 🐙
value is positive and has not occurred before index start.
def MissingBefore (a : ℕ → ℕ) (start value : ℕ) : Prop :=
0 < value ∧ ∀ i < start, a i ≠ value
seed is the least positive value missing before a block boundary.
def LeastMissingBefore (a : ℕ → ℕ) (start seed : ℕ) : Prop :=
MissingBefore a start seed ∧
∀ value, MissingBefore a start value → seed ≤ valueA total sequence follows the construction when explicit consecutive block boundaries and finite first-stopping exponents witness every block.
def FollowsRule (a : ℕ → ℕ) : Prop :=
∃ boundary stop : ℕ → ℕ,
boundary 0 = 0 ∧
∀ blockIndex,
let start := boundary blockIndex
let seed := a start
LeastMissingBefore a start seed ∧
StopsAt seed (stop blockIndex) ∧
(∀ j ≤ stop blockIndex, a (start + j) = seed * 3 ^ j) ∧
boundary (blockIndex + 1) = start + stop blockIndex + 1
seed is the least positive value absent from the finite history.
def LeastMissing (history : List ℕ) (seed : ℕ) : Prop :=
0 < seed ∧ seed ∉ history ∧
∀ smaller ∈ Finset.Ico 1 seed, smaller ∈ historyA finite history made by appending complete source-valid blocks.
inductive ValidBlockPrefix : List ℕ → Prop
| nil : ValidBlockPrefix []
| append {history : List ℕ} {seed exponent : ℕ}
(valid : ValidBlockPrefix history)
(least : LeastMissing history seed)
(stops : StopsAt seed exponent) :
ValidBlockPrefix (history ++ blockValues seed exponent)
A value occurs at the official OEIS index $n\geq 1$ in a finite valid prefix.
The total sequences in FollowsRule use index $n-1$ for the same term.
def TermAt (n value : ℕ) : Prop :=
0 < n ∧ ∃ xs, ValidBlockPrefix xs ∧ xs[n - 1]? = some valueIndex zero is outside the official OEIS domain.
@[category test, AMS 11]
theorem not_term_at_zero (value : ℕ) : ¬TermAt 0 value := value:ℕ⊢ ¬TermAt 0 value
All goals completed! 🐙private def initialBlocks : List ℕ :=
[1, 3, 9, 27, 81, 2, 6, 18, 54, 162, 4, 12, 36, 108, 324, 5, 15]h0:ValidBlockPrefix []h1:ValidBlockPrefix [1, 3, 9, 27, 81]h2:ValidBlockPrefix [1, 3, 9, 27, 81, 2, 6, 18, 54, 162]h3:ValidBlockPrefix [1, 3, 9, 27, 81, 2, 6, 18, 54, 162, 4, 12, 36, 108, 324]h4:ValidBlockPrefix initialBlocks⊢ ValidBlockPrefix initialBlocks
exact h4 All goals completed! 🐙@[category test, AMS 11]
theorem a_1 : TermAt 1 1 := by ⊢ TermAt 1 1
exact ⟨by ⊢ 0 < 1 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[1 - 1]? = some 1 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_2 : TermAt 2 3 := by ⊢ TermAt 2 3
exact ⟨by ⊢ 0 < 2 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[2 - 1]? = some 3 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_3 : TermAt 3 9 := by ⊢ TermAt 3 9
exact ⟨by ⊢ 0 < 3 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[3 - 1]? = some 9 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_4 : TermAt 4 27 := by ⊢ TermAt 4 27
exact ⟨by ⊢ 0 < 4 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[4 - 1]? = some 27 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_5 : TermAt 5 81 := by ⊢ TermAt 5 81
exact ⟨by ⊢ 0 < 5 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[5 - 1]? = some 81 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_6 : TermAt 6 2 := by ⊢ TermAt 6 2
exact ⟨by ⊢ 0 < 6 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[6 - 1]? = some 2 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_7 : TermAt 7 6 := by ⊢ TermAt 7 6
exact ⟨by ⊢ 0 < 7 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[7 - 1]? = some 6 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_8 : TermAt 8 18 := by ⊢ TermAt 8 18
exact ⟨by ⊢ 0 < 8 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[8 - 1]? = some 18 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_9 : TermAt 9 54 := by ⊢ TermAt 9 54
exact ⟨by ⊢ 0 < 9 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[9 - 1]? = some 54 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_10 : TermAt 10 162 := by ⊢ TermAt 10 162
exact ⟨by ⊢ 0 < 10 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[10 - 1]? = some 162 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_11 : TermAt 11 4 := by ⊢ TermAt 11 4
exact ⟨by ⊢ 0 < 11 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[11 - 1]? = some 4 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_12 : TermAt 12 12 := by ⊢ TermAt 12 12
exact ⟨by ⊢ 0 < 12 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[12 - 1]? = some 12 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_13 : TermAt 13 36 := by ⊢ TermAt 13 36
exact ⟨by ⊢ 0 < 13 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[13 - 1]? = some 36 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_14 : TermAt 14 108 := by ⊢ TermAt 14 108
exact ⟨by ⊢ 0 < 14 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[14 - 1]? = some 108 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_15 : TermAt 15 324 := by ⊢ TermAt 15 324
exact ⟨by ⊢ 0 < 15 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[15 - 1]? = some 324 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_16 : TermAt 16 5 := by ⊢ TermAt 16 5
exact ⟨by ⊢ 0 < 16 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[16 - 1]? = some 5 decide All goals completed! 🐙⟩@[category test, AMS 11]
theorem a_17 : TermAt 17 15 := by ⊢ TermAt 17 15
exact ⟨by ⊢ 0 < 17 decide All goals completed! 🐙, initialBlocks, initialBlocks_valid, by ⊢ initialBlocks[17 - 1]? = some 15 decide All goals completed! 🐙⟩OEIS A331631 states: The sequence is conjectured to be a permutation of the positive integers (see the Crossrefs section).
@[category research open, AMS 11]
theorem conjecture :
∃ a : ℕ → ℕ, FollowsRule a ∧ Function.Injective a ∧
∀ k > 0, ∃ n, a n = k := by ⊢ ∃ a, FollowsRule a ∧ Function.Injective a ∧ ∀ k > 0, ∃ n, a n = k
sorry All goals completed! 🐙end OeisA331631