/-
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 FormalConjecturesUtilDecimal 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 OeisA401006The 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 + bZero, 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.maxPrimeFacZero 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
change Nat.maxPrimeFac 2941 = 173 at hf hf:Nat.maxPrimeFac 2941 = 173⊢ a 2941 = 17173
norm_num [a, hf, decimalAppend, decimalDigitCount] All goals completed! 🐙
@[category test, AMS 11]
theorem a_17173 : a 17173 = 131321 := by ⊢ a 17173 = 131321
have hf : Nat.maxPrimeFac (13 * 1321) = 1321 := by
rw [Nat.maxPrimeFac_mul (by ⊢ 13 ≠ 0 ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321 decide All goals completed! 🐙 ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321) (by ⊢ 1321 ≠ 0 ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321 decide All goals completed! 🐙 ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321),
(by ⊢ Nat.Prime 13 ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321 norm_num All goals completed! 🐙 ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321 : Nat.Prime 13).maxPrimeFac_eq_self,
(by ⊢ Nat.Prime 1321 ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321 norm_num All goals completed! 🐙 ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321 : Nat.Prime 1321).maxPrimeFac_eq_self] ⊢ max 13 1321 = 1321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321
norm_num hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321 hf:(13 * 1321).maxPrimeFac = 1321⊢ a 17173 = 131321
change Nat.maxPrimeFac 17173 = 1321 at hf hf:Nat.maxPrimeFac 17173 = 1321⊢ a 17173 = 131321
norm_num [a, hf, decimalAppend, decimalDigitCount] All goals completed! 🐙Decimal append is larger than the corresponding product when both inputs are positive.
@[category API, AMS 11]
theorem mul_lt_decimal_append {x y : ℕ} (hx : 0 < x) (hy : 0 < y) :
x * y < decimalAppend x y := by x:ℕy:ℕhx:0 < xhy:0 < y⊢ x * y < decimalAppend x y
have hypow : y < 10 ^ decimalDigitCount y := by
simpa [decimalDigitCount, hy.ne'] using
(Nat.lt_base_pow_length_digits (b := 10) (m := y) (by x:ℕy:ℕhx:0 < xhy:0 < y⊢ 1 < 10 x:ℕy:ℕhx:0 < xhy:0 < yhypow:y < 10 ^ decimalDigitCount y⊢ x * y < decimalAppend x y norm_num All goals completed! 🐙 x:ℕy:ℕhx:0 < xhy:0 < yhypow:y < 10 ^ decimalDigitCount y⊢ x * y < decimalAppend x y)) x:ℕy:ℕhx:0 < xhy:0 < yhypow:y < 10 ^ decimalDigitCount y⊢ x * y < decimalAppend x y
exact (Nat.mul_lt_mul_of_pos_left hypow hx).trans (Nat.lt_add_of_pos_right hy) All goals completed! 🐙Applying $a$ to a composite integer above one strictly increases its value.
@[category API, AMS 11]
theorem lt_a_of_not_prime {n : ℕ} (hn : 1 < n) (hprime : ¬n.Prime) : n < a n := by n:ℕhn:1 < nhprime:¬Nat.Prime n⊢ n < a n
have hp : n.maxPrimeFac.Prime := Nat.prime_maxPrimeFac_of_one_lt n hn n:ℕhn:1 < nhprime:¬Nat.Prime nhp:Nat.Prime n.maxPrimeFac⊢ n < a n
have hq : 0 < n / n.maxPrimeFac := Nat.div_pos Nat.maxPrimeFac_le hp.pos n:ℕhn:1 < nhprime:¬Nat.Prime nhp:Nat.Prime n.maxPrimeFachq:0 < n / n.maxPrimeFac⊢ n < a n
have hlt := mul_lt_decimal_append hq hp.pos n:ℕhn:1 < nhprime:¬Nat.Prime nhp:Nat.Prime n.maxPrimeFachq:0 < n / n.maxPrimeFachlt:n / n.maxPrimeFac * n.maxPrimeFac < decimalAppend (n / n.maxPrimeFac) n.maxPrimeFac⊢ n < a n
rw [Nat.div_mul_cancel Nat.maxPrimeFac_dvd 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 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] at hlt 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
simpa [a, not_le.mpr hn, hprime] using hlt All goals completed! 🐙A starting value reaches a prime after finitely many iterations of $a$.
def ReachesPrime (n : ℕ) : Prop :=
∃ k : ℕ, ((a^[k]) n).PrimeZero never reaches a prime under iteration.
@[category test, AMS 11]
theorem not_reaches_prime_zero : ¬ ReachesPrime 0 := by ⊢ ¬ReachesPrime 0
rintro ⟨k, hk⟩ k:ℕhk:Nat.Prime (a^[k] 0)⊢ False
rw [Function.iterate_fixed a_zero k k:ℕhk:Nat.Prime 0⊢ False k:ℕhk:Nat.Prime 0⊢ False] at hk k:ℕhk:Nat.Prime 0⊢ False
exact Nat.not_prime_zero hk All goals completed! 🐙One never reaches a prime under iteration.
@[category test, AMS 11]
theorem not_reaches_prime_one : ¬ ReachesPrime 1 := by ⊢ ¬ReachesPrime 1
rintro ⟨k, hk⟩ k:ℕhk:Nat.Prime (a^[k] 1)⊢ False
rw [Function.iterate_fixed a_one k k:ℕhk:Nat.Prime 1⊢ False k:ℕhk:Nat.Prime 1⊢ False] at hk k:ℕhk:Nat.Prime 1⊢ False
exact Nat.not_prime_one hk All goals completed! 🐙@[category test, AMS 11]
theorem prime_131321 : Nat.Prime 131321 := by ⊢ Nat.Prime 131321 norm_num 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 := by ⊢ ReachesPrime 49
have orbit : (a^[7]) 49 = 131321 := calc
(a^[7]) 49 = (a^[6]) (a 49) := Function.iterate_succ_apply a 6 49
_ = (a^[6]) 77 := congrArg (a^[6]) a_49
_ = (a^[5]) (a 77) := Function.iterate_succ_apply a 5 77
_ = (a^[5]) 711 := congrArg (a^[5]) a_77
_ = (a^[4]) (a 711) := Function.iterate_succ_apply a 4 711
_ = (a^[4]) 979 := congrArg (a^[4]) a_711
_ = (a^[3]) (a 979) := Function.iterate_succ_apply a 3 979
_ = (a^[3]) 1189 := congrArg (a^[3]) a_979
_ = (a^[2]) (a 1189) := Function.iterate_succ_apply a 2 1189
_ = (a^[2]) 2941 := congrArg (a^[2]) a_1189
_ = (a^[1]) (a 2941) := Function.iterate_succ_apply a 1 2941
_ = (a^[1]) 17173 := congrArg (a^[1]) a_2941
_ = (a^[0]) (a 17173) := Function.iterate_succ_apply a 0 17173
_ = (a^[0]) 131321 := congrArg (a^[0]) a_17173
_ = 131321 := rfl orbit:a^[7] 49 = 131321⊢ ReachesPrime 49
exact ⟨7, (congrArg Nat.Prime orbit).mpr prime_131321⟩ 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.
@[category research open, AMS 11]
theorem eventually_prime : ∀ n : ℕ, 2 ≤ n → ReachesPrime n := by ⊢ ∀ (n : ℕ), 2 ≤ n → ReachesPrime n
sorry All goals completed! 🐙end OeisA401006