/- 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 FormalConjecturesUtil

The cup-of-coffee sequence

The sequence starts with $1, 2$. Each later term is the least unused positive integer such that, for every prime, runs of consecutive multiples have length exactly two. The local rule requires prime factors that have just appeared to occur once more, and forbids prime factors that occurred in both of the preceding terms.

References:

@[expose] public sectionnamespace OeisA280864

Prime factors whose run began at previous and must continue at the next term.

def requiredFactors (previousPrevious previous : ℕ) : Finset ℕ := previous.primeFactors \ previousPrevious.primeFactors

Prime factors whose run has length two and must end before the next term.

def forbiddenFactors (previousPrevious previous : ℕ) : Finset ℕ := previous.primeFactors ∩ previousPrevious.primeFactors

Whether candidate obeys the prime-factor run rule after the two preceding values.

def Eligible (previousPrevious previous candidate : ℕ) : Prop := 0 < candidate ∧ (∀ p ∈ requiredFactors previousPrevious previous, p ∣ candidate) ∧ (∀ p ∈ forbiddenFactors previousPrevious previous, ¬p ∣ candidate)@[category test, AMS 11] theorem not_eligible_zero : ¬Eligible 1 2 0 := ⊢ ¬Eligible 1 2 0 All goals completed! 🐙@[category test, AMS 11] theorem not_eligible_missing_required_factor : ¬Eligible 1 2 3 := ⊢ ¬Eligible 1 2 3 All goals completed! 🐙@[category test, AMS 11] theorem not_eligible_with_forbidden_factor : ¬Eligible 2 4 8 := ⊢ ¬Eligible 2 4 8 All goals completed! 🐙@[category test, AMS 11] theorem eligible_3_6_8 : Eligible 3 6 8 := ⊢ Eligible 3 6 8 All goals completed! 🐙

The value candidate has not appeared before index n.

def UnusedBefore (a : ℕ → ℕ) (n candidate : ℕ) : Prop := ∀ i < n, a i ≠ candidate

At index n, the sequence takes the least unused eligible positive value.

def GreedyAt (a : ℕ → ℕ) (n : ℕ) : Prop := Eligible (a (n - 2)) (a (n - 1)) (a n) ∧ UnusedBefore a n (a n) ∧ ∀ candidate, Eligible (a (n - 2)) (a (n - 1)) candidate → UnusedBefore a n candidate → a n ≤ candidate

A total sequence obeys the initial conditions and every subsequent greedy step.

def FollowsRule (a : ℕ → ℕ) : Prop := a 0 = 1 ∧ a 1 = 2 ∧ ∀ n, 2 ≤ n → GreedyAt a n

A later value in a rule-following sequence differs from every earlier value.

a:ℕ → ℕi:ℕj:ℕha0:a 0 = 1ha1:a 1 = 2ha:∀ (n : ℕ), 2 ≤ n → GreedyAt a nhij:i < 1hi:i = 0⊢ a i ≠ a 1 a:ℕ → ℕj:ℕha0:a 0 = 1ha1:a 1 = 2ha:∀ (n : ℕ), 2 ≤ n → GreedyAt a nhij:0 < 1⊢ a 0 ≠ a 1 All goals completed! 🐙 a:ℕ → ℕi:ℕj✝:ℕha0:a 0 = 1ha1:a 1 = 2ha:∀ (n : ℕ), 2 ≤ n → GreedyAt a nj:ℕhij:i < j + 2⊢ a i ≠ a (j + 2) exact (ha (j + 2) (a:ℕ → ℕi:ℕj✝:ℕha0:a 0 = 1ha1:a 1 = 2ha:∀ (n : ℕ), 2 ≤ n → GreedyAt a nj:ℕhij:i < j + 2⊢ 2 ≤ j + 2 All goals completed! 🐙)).2.1 i hij

Unusedness at every greedy step makes every rule-following sequence injective.

@[category API, AMS 11] theorem followsRule_injective {a : ℕ → ℕ} (ha : FollowsRule a) : Function.Injective a := a:ℕ → ℕha:FollowsRule a⊢ Function.Injective a a:ℕ → ℕha:FollowsRule ai:ℕj:ℕhij:a i = a j⊢ i = j a:ℕ → ℕha:FollowsRule ai:ℕj:ℕhij:a i = a jhne:¬i = j⊢ False a:ℕ → ℕha:FollowsRule ai:ℕj:ℕhij:a i = a jhne:¬i = jhlt:i < j⊢ Falsea:ℕ → ℕha:FollowsRule ai:ℕj:ℕhij:a i = a jhne:¬i = jhgt:j < i⊢ False a:ℕ → ℕha:FollowsRule ai:ℕj:ℕhij:a i = a jhne:¬i = jhlt:i < j⊢ False All goals completed! 🐙 a:ℕ → ℕha:FollowsRule ai:ℕj:ℕhij:a i = a jhne:¬i = jhgt:j < i⊢ False All goals completed! 🐙

candidate is the least unused eligible value following the two displayed final values.

def LeastEligibleUnused (history : List ℕ) (previousPrevious previous candidate : ℕ) : Prop := Eligible previousPrevious previous candidate ∧ candidate ∉ history ∧ ∀ smaller ∈ Finset.Ico 1 candidate, ¬Eligible previousPrevious previous smaller ∨ smaller ∈ history

A finite list generated by the same greedy rule, without assuming an infinite continuation.

inductive ValidPrefix : List ℕ → Prop | nil : ValidPrefix [] | one : ValidPrefix [1] | two : ValidPrefix [1, 2] | append {history : List ℕ} {previousPrevious previous candidate : ℕ} (valid : ValidPrefix (history ++ [previousPrevious, previous])) (least : LeastEligibleUnused (history ++ [previousPrevious, previous]) previousPrevious previous candidate) : ValidPrefix (history ++ [previousPrevious, previous, candidate])

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, ValidPrefix xs ∧ xs[n - 1]? = some value

Index 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 initialPrefix : List ℕ := [1, 2, 4, 3, 6, 8, 5, 10, 12, 9]h2:ValidPrefix [1, 2]h3:ValidPrefix [1, 2, 4]h4:ValidPrefix [1, 2, 4, 3]h5:ValidPrefix [1, 2, 4, 3, 6]h6:ValidPrefix [1, 2, 4, 3, 6, 8]h7:ValidPrefix [1, 2, 4, 3, 6, 8, 5]h8:ValidPrefix [1, 2, 4, 3, 6, 8, 5, 10]h9:ValidPrefix [1, 2, 4, 3, 6, 8, 5, 10, 12]h10:ValidPrefix initialPrefix⊢ ValidPrefix initialPrefix All goals completed! 🐙@[category test, AMS 11] theorem a_1 : TermAt 1 1 := ⊢ TermAt 1 1 exact ⟨⊢ 0 < 1 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[1 - 1]? = some 1 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_2 : TermAt 2 2 := ⊢ TermAt 2 2 exact ⟨⊢ 0 < 2 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[2 - 1]? = some 2 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_3 : TermAt 3 4 := ⊢ TermAt 3 4 exact ⟨⊢ 0 < 3 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[3 - 1]? = some 4 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_4 : TermAt 4 3 := ⊢ TermAt 4 3 exact ⟨⊢ 0 < 4 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[4 - 1]? = some 3 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_5 : TermAt 5 6 := ⊢ TermAt 5 6 exact ⟨⊢ 0 < 5 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[5 - 1]? = some 6 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_6 : TermAt 6 8 := ⊢ TermAt 6 8 exact ⟨⊢ 0 < 6 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[6 - 1]? = some 8 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_7 : TermAt 7 5 := ⊢ TermAt 7 5 exact ⟨⊢ 0 < 7 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[7 - 1]? = some 5 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_8 : TermAt 8 10 := ⊢ TermAt 8 10 exact ⟨⊢ 0 < 8 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[8 - 1]? = some 10 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_9 : TermAt 9 12 := ⊢ TermAt 9 12 exact ⟨⊢ 0 < 9 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[9 - 1]? = some 12 All goals completed! 🐙⟩@[category test, AMS 11] theorem a_10 : TermAt 10 9 := ⊢ TermAt 10 9 exact ⟨⊢ 0 < 10 All goals completed! 🐙, initialPrefix, initialPrefix_valid, ⊢ initialPrefix[10 - 1]? = some 9 All goals completed! 🐙⟩

Conjectured to be a permutation of the positive integers.

@[category research open, AMS 11] theorem conjecture : ∃ a : ℕ → ℕ, FollowsRule a ∧ ∀ k > 0, ∃ n, a n = k := ⊢ ∃ a, FollowsRule a ∧ ∀ k > 0, ∃ n, a n = k All goals completed! 🐙end OeisA280864