/- Copyright 2025 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 Curling Number Conjecture

Reference: arxiv/0912.2382 The Curling Number Conjecture by Benjamin Chaffin and N. J. A. Sloane

@[expose] public sectionnamespace Arxiv.«0912.2382»

The curling number

Let $S$ be a finite nonempty sequence of integers. By grouping adjacent terms, it is always possible to write it as $S = X Y Y . . . Y = X Y^k$, where $X$ and $Y$ are sequences of integers and $Y$ is nonempty ($X$ is allowed to be the empty sequence $∅$). There may be several ways to do this: choose the one that maximizes the value of $k$: this $k$ is the curling number of $S$, denoted by $k S$.

noncomputable def k (S : List ℤ) : ℕ := sSup {k : ℕ | ∃ X Y : List ℤ, Y ≠ [] ∧ S = X ++ (List.replicate k Y).flatten}

A nonempty suffix repeated $r$ times uses at least $r$ entries.

@[category API, AMS 11] theorem exponent_le_length {L X Y : List ℤ} {r : ℕ} (hY : Y ≠ []) (hL : L = X ++ (List.replicate r Y).flatten) : r ≤ L.length := L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flatten⊢ r ≤ L.length L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = (X ++ (List.replicate r Y).flatten).length⊢ r ≤ L.length L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = X.length + r * Y.length⊢ r ≤ L.length L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = X.length + r * Y.lengthhpos:1 ≤ Y.length⊢ r ≤ L.length L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = X.length + r * Y.lengthhpos:1 ≤ Y.lengthhmul:r * 1 ≤ r * Y.length⊢ r ≤ L.length L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = X.length + r * Y.lengthhpos:1 ≤ Y.lengthhmul:r ≤ r * Y.length⊢ r ≤ L.length All goals completed! 🐙

The admissible repetition counts in the definition of $k(L)$ are bounded.

@[category API, AMS 11] theorem bddAbove_exponents (L : List ℤ) : BddAbove {r : ℕ | ∃ X Y : List ℤ, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten} := L:List ℤ⊢ BddAbove {r | ∃ X Y, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten} L:List ℤ⊢ L.length ∈ upperBounds {r | ∃ X Y, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten} L:List ℤr:ℕX:List ℤY:List ℤhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flatten⊢ r ≤ L.length All goals completed! 🐙

The curling number cannot exceed the length of the sequence, including the empty case.

@[category API, AMS 11] theorem k_le_length (L : List ℤ) : k L ≤ L.length := L:List ℤ⊢ k L ≤ L.length apply csSup_le (show ∃ r : ℕ, ∃ X Y : List ℤ, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten from ⟨0, L, [0], L:List ℤ⊢ [0] ≠ [] All goals completed! 🐙, L:List ℤ⊢ L = L ++ (List.replicate 0 [0]).flatten All goals completed! 🐙⟩) L:List ℤr:ℕX:List ℤY:List ℤhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flatten⊢ r ≤ L.length All goals completed! 🐙

Every nonempty sequence has curling number at least $1$.

@[category API, AMS 11] theorem one_le_k {L : List ℤ} (hL : L ≠ []) : 1 ≤ k L := L:List ℤhL:L ≠ []⊢ 1 ≤ k L exact le_csSup (bddAbove_exponents L) ⟨[], L, hL, L:List ℤhL:L ≠ []⊢ L = [] ++ (List.replicate 1 L).flatten All goals completed! 🐙⟩

A nonempty sequence has a suffix repeated exactly its curling number of times.

L:List ℤhL:L ≠ []hne:{r | ∃ X Y, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten}.Nonempty⊢ ∃ X Y, Y ≠ [] ∧ L = X ++ (List.replicate (k L) Y).flatten All goals completed! 🐙

One starts with any initial sequence of integers $S₀$, and extends it by repeatedly appending the curling number of the current sequence.

noncomputable def S (S₀ : List ℤ) (n : ℕ) : List ℤ := match n with | 0 => S₀ | n + 1 => (S S₀ n) ++ [Int.ofNat (k (S S₀ n))]

Each extension step appends exactly one integer.

@[category API, AMS 11] theorem S_length (L : List ℤ) (n : ℕ) : (S L n).length = L.length + n := L:List ℤn:ℕ⊢ (S L n).length = L.length + n induction n with L:List ℤ⊢ (S L 0).length = L.length + 0 All goals completed! 🐙 L:List ℤn:ℕih:(S L n).length = L.length + n⊢ (S L (n + 1)).length = L.length + (n + 1) All goals completed! 🐙

Extending a nonempty initial sequence preserves nonemptiness.

@[category API, AMS 11] theorem S_ne_nil {L : List ℤ} (hL : L ≠ []) (n : ℕ) : S L n ≠ [] := L:List ℤhL:L ≠ []n:ℕ⊢ S L n ≠ [] L:List ℤhL:L ≠ []n:ℕhpos:0 < L.length⊢ S L n ≠ [] L:List ℤhL:L ≠ []n:ℕhpos:0 < L.lengthhlen:(S L n).length = L.length + n⊢ S L n ≠ [] L:List ℤhL:L ≠ []n:ℕhpos:0 < L.lengthhlen:(S L n).length = L.length + nh:S L n = []⊢ False L:List ℤhL:L ≠ []n:ℕhpos:0 < L.lengthh:S L n = []hlen:0 = L.length + n⊢ False All goals completed! 🐙

A one-term sequence has curling number $1$, regardless of the integer in it.

a:ℤhle:k [a] ≤ [a].lengthhge:1 ≤ k [a]⊢ k [a] = 1 a:ℤhle:k [a] ≤ 1hge:1 ≤ k [a]⊢ k [a] = 1 All goals completed! 🐙

The conjecture holds immediately for every one-term starting sequence.

@[category test, AMS 11] theorem curling_number_conjecture_singleton (a : ℤ) : ∃ m, k (S [a] m) = 1 := a:ℤ⊢ ∃ m, k (S [a] m) = 1 All goals completed! 🐙

Starting from any nonempty finite integer sequence, repeatedly appending its curling number eventually gives a sequence with curling number $1$ [Chaffin and Sloane, Conjecture 1].

@[category research open, AMS 11] theorem curling_number_conjecture (S₀ : List ℤ) (h : S₀ ≠ []) : ∃ m, k (S S₀ m) = 1 := S₀:List ℤh:S₀ ≠ []⊢ ∃ m, k (S S₀ m) = 1 All goals completed! 🐙end Arxiv.«0912.2382»