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

Decimal concatenation of a cofactor and the largest prime factor

For a composite positive integer $n$, let $p$ be its largest prime factor. The sequence value $a(n)$ concatenates the decimal representations of $n/p$ and $p$, in that order. It fixes primes and one, and is extended here by $a(0)=0$. OEIS A397122 records the prime reached by iterating this map from each starting value, or $-1$ if no prime is reached.

References:

@[expose] public sectionnamespace OeisA401006

The number of decimal digits of a natural number, counting zero as one digit.

def decimalDigitCount (n : ℕ) : ℕ := if n = 0 then 1 else (Nat.digits 10 n).length

Append the decimal digits of b to those of a.

def decimalAppend (a b : ℕ) : ℕ := a * 10 ^ decimalDigitCount b + b

Zero, one, and primes are fixed; a composite number is replaced by its cofactor after removing one largest prime factor, followed by that prime factor in decimal.

def a (n : ℕ) : ℕ := if n ≤ 1 then n else if n.Prime then n else decimalAppend (n / n.maxPrimeFac) n.maxPrimeFac

Zero is the artificial fixed point outside the official OEIS indexing.

@[category API, AMS 11] theorem a_zero : a 0 = 0 := ⊢ a 0 = 0 All goals completed! 🐙

One is a fixed point.

@[category API, AMS 11] theorem a_one : a 1 = 1 := ⊢ a 1 = 1 All goals completed! 🐙

Every prime is a fixed point.

@[category API, AMS 11] theorem a_prime {p : ℕ} (hp : p.Prime) : a p = p := p:ℕhp:Nat.Prime p⊢ a p = p All goals completed! 🐙@[category test, AMS 11] theorem a_0 : a 0 = 0 := ⊢ a 0 = 0 All goals completed! 🐙@[category test, AMS 11] theorem a_1 : a 1 = 1 := ⊢ a 1 = 1 All goals completed! 🐙@[category test, AMS 11] theorem a_2 : a 2 = 2 := ⊢ a 2 = 2 All goals completed! 🐙@[category test, AMS 11] theorem a_3 : a 3 = 3 := ⊢ a 3 = 3 All goals completed! 🐙@[category test, AMS 11] theorem a_4 : a 4 = 22 := ⊢ a 4 = 22 All goals completed! 🐙@[category test, AMS 11] theorem a_5 : a 5 = 5 := ⊢ a 5 = 5 All goals completed! 🐙@[category test, AMS 11] theorem a_6 : a 6 = 23 := ⊢ a 6 = 23 All goals completed! 🐙@[category test, AMS 11] theorem a_7 : a 7 = 7 := ⊢ a 7 = 7 All goals completed! 🐙@[category test, AMS 11] theorem a_8 : a 8 = 42 := ⊢ a 8 = 42 All goals completed! 🐙@[category test, AMS 11] theorem a_44 : a 44 = 411 := ⊢ a 44 = 411 All goals completed! 🐙@[category test, AMS 11] theorem a_49 : a 49 = 77 := ⊢ a 49 = 77 All goals completed! 🐙@[category test, AMS 11] theorem a_77 : a 77 = 711 := ⊢ a 77 = 711 All goals completed! 🐙@[category test, AMS 11] theorem a_711 : a 711 = 979 := ⊢ a 711 = 979 All goals completed! 🐙@[category test, AMS 11] theorem a_979 : a 979 = 1189 := ⊢ a 979 = 1189 All goals completed! 🐙@[category test, AMS 11] theorem a_1189 : a 1189 = 2941 := ⊢ a 1189 = 2941 All goals completed! 🐙hf:(17 * 173).maxPrimeFac = 173⊢ a 2941 = 17173 hf:Nat.maxPrimeFac 2941 = 173⊢ a 2941 = 17173 All goals completed! 🐙hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321 hf:Nat.maxPrimeFac 17173 = 1321⊢ a 17173 = 131321 All goals completed! 🐙

Decimal append is larger than the corresponding product when both inputs are positive.

x:ℕy:ℕhx:0 < xhy:0 < yhypow:y < 10 ^ decimalDigitCount y⊢ x * y < decimalAppend x y All goals completed! 🐙

Applying $a$ to a composite integer above one strictly increases its value.

n:ℕhn:1 < nhprime:¬Nat.Prime nhp:Nat.Prime n.maxPrimeFachq:0 < n / n.maxPrimeFachlt:n < decimalAppend (n / n.maxPrimeFac) n.maxPrimeFac⊢ n < a n All goals completed! 🐙

A starting value reaches a prime after finitely many iterations of $a$.

def ReachesPrime (n : ℕ) : Prop := ∃ k : ℕ, ((a^[k]) n).Prime

Zero never reaches a prime under iteration.

k:ℕhk:Nat.Prime 0⊢ False All goals completed! 🐙

One never reaches a prime under iteration.

k:ℕhk:Nat.Prime 1⊢ False All goals completed! 🐙@[category test, AMS 11] theorem prime_131321 : Nat.Prime 131321 := ⊢ Nat.Prime 131321 All goals completed! 🐙

The orbit starting from $49$ reaches the prime $131321$ after seven steps.

@[category test, AMS 11] theorem reaches_prime_49 : ReachesPrime 49 := ⊢ ReachesPrime 49 orbit:a^[7] 49 = 131321⊢ ReachesPrime 49 All goals completed! 🐙

If we start at $n \ge 2$, and repeatedly apply the map $k \mapsto a(k)$, we will eventually reach a prime, which is then a fixed point.

— OEIS A401006

@[category research open, AMS 11] theorem eventually_prime : ∀ n : ℕ, 2 ≤ n → ReachesPrime n := ⊢ ∀ (n : ℕ), 2 ≤ n → ReachesPrime n All goals completed! 🐙end OeisA401006