Classification of infinite three-largest-proper-divisor sequences (corrected divisibility-by-3 step)

Problem

Let $f(N)$ be the sum of the three largest proper divisors of $N$ (proper means $<N$). We are given an infinite sequence $a_1,a_2,\dots$ of positive integers such that each $a_n$ has at least three proper divisors, and [ a_{n+1}=f(a_n)\qquad(n\ge 1). ] Determine all possible values of $a_1$.

Answer (classification)

Write $v_p(N)$ for the exponent of a prime $p$ in $N$.

All and only the following $a_1$ work:

$a_1$ is divisible by $6$ but not by $5$, $v_2(a_1)$ is odd, and [ v_3(a_1)\ \ge\ \frac{v_2(a_1)+1}{2}. ]

Equivalently, $a_1$ can be written as [ a_1 = 2^{2k+1},3^{\ell},m ] for some integers $k,\ell,m\ge 0$ with [ \ell\ge k+1\quad\text{and}\quad \gcd(m,30)=1. ]

Step 1: in any infinite valid sequence, every term is divisible by $6$

Let $N$ be any term of the sequence, and let $d_1>d_2>d_3$ be the three largest proper divisors of $N$. Define [ q_i := \frac{N}{d_i}\qquad(i=1,2,3). ] Then each $q_i$ is a divisor of $N$, $q_i>1$, the $q_i$ are distinct, and [ N\left(\frac1{q_1}+\frac1{q_2}+\frac1{q_3}\right)=d_1+d_2+d_3=f(N). ]

Lemma 1.1: if $N$ is odd and has at least three proper divisors, then $f(N)<N$

If $N$ is odd then all divisors of $N$ are odd, hence $q_1\ge 3$, $q_2\ge 5$, $q_3\ge 7$ and [ \frac1{q_1}+\frac1{q_2}+\frac1{q_3}\le \frac13+\frac15+\frac17 = \frac{71}{105}<1. ] So $f(N)<N$.

Moreover, if $N$ is odd then $f(N)$ is also odd (sum of three odd divisors). Therefore, if some $a_n$ were odd, the sequence would remain odd and strictly decrease forever, impossible in $\mathbb N$.

Hence in any infinite valid sequence, [ 2\mid a_n\quad\text{for all }n. ]

Lemma 1.2: if $N$ is even and $3\nmid N$ and $N$ has at least three proper divisors, then $f(N)<N$

If $N$ is even then $d_1=N/2$, so $q_1=2$. If additionally $3\nmid N$, then $q_2\ne 3$, so $q_2\ge 4$ and $q_3\ge 5$. Therefore [ \frac1{q_1}+\frac1{q_2}+\frac1{q_3} \le \frac12+\frac14+\frac15 = \frac{19}{20}<1, ] hence $f(N)<N$.

The inequality alone does not imply that divisibility by $3$ is preserved (indeed, e.g. $f(374)=243$). We instead use the following parity-mod-$3$ lemma.

Lemma 1.3 (key fix): if $N$ is even, $3\nmid N$, and $f(N)$ is even, then $3\nmid f(N)$

Assume $N$ is even and $3\nmid N$. Let $d_1>d_2>d_3$ be the three largest proper divisors, and define $q_i=N/d_i$ as above. Then $q_1=2$ and, since $3\nmid N$, all $q_i$ are invertible modulo $3$.

Suppose for contradiction that $3\mid f(N)=d_1+d_2+d_3$. Reducing modulo $3$ and using $d_i=N/q_i$ gives [ 0\equiv f(N)=\sum_{i=1}^3 \frac{N}{q_i} \equiv N\sum_{i=1}^3 q_i^{-1}\pmod 3. ] Since $3\nmid N$, we can cancel $N$ and get [ q_1^{-1}+q_2^{-1}+q_3^{-1}\equiv 0\pmod 3. ] But $q_1=2$ and $2^{-1}\equiv 2\pmod 3$. Also for any $q\not\equiv 0\pmod 3$, we have $q\equiv 1,2\pmod 3$ and $q^{-1}\equiv q\pmod 3$. So the congruence becomes [ 2+q_2+q_3\equiv 0\pmod 3. ] The only way this can happen with $q_2,q_3\in{1,2}$ (mod $3$) is [ q_2\equiv q_3\equiv 2\pmod 3. ] In particular $q_2\not\equiv 1\pmod 3$, so $q_2\ne 4$. But if $4\mid N$, then $4$ is a divisor of $N$ and (because $3\nmid N$) there is no divisor strictly between $2$ and $4$, hence $q_2=4$, contradiction. Therefore $4\nmid N$, so $v_2(N)=1$ and $d_1=N/2$ is odd. Also $q_2,q_3$ are then odd, hence $d_2=N/q_2$ and $d_3=N/q_3$ are even. Thus $f(N)=d_1+d_2+d_3$ is odd, contradicting the assumption that $f(N)$ is even.

So if $f(N)$ is even, necessarily $3\nmid f(N)$.

Corollary 1.4: in any infinite valid sequence, every term is divisible by $3$

Assume for contradiction that $3\nmid a_n$ for some $n$. By Lemma 1.1, every term in an infinite valid sequence is even, hence $a_{n+1}=f(a_n)$ is even. Applying Lemma 1.3 to $N=a_n$ yields $3\nmid a_{n+1}$. Inductively, $3\nmid a_k$ for all $k\ge n$. But then Lemma 1.2 applies at every step $k\ge n$, giving [ a_{k+1}=f(a_k)<a_k\qquad(k\ge n), ] so the tail is a strictly decreasing infinite sequence in $\mathbb N$, impossible.

Therefore $3\mid a_n$ for all $n$.

Combining with Lemma 1.1, we have established the crucial invariant: [ 6\mid a_n\quad\text{for all }n. ]

Step 2: explicit evaluation of $f(N)$ for $6\mid N$

Assume $6\mid N$, and let $d_1>d_2>d_3$ be the three largest proper divisors.

• Always $N/2$ and $N/3$ are proper divisors.
• Any divisor $>N/4$ must be of the form $N/q$ with $q<4$, hence only $q=2,3$ are possible.
• Any divisor $>N/5$ must have $q<5$, hence $q\in{2,3,4}$.
• Any divisor $>N/6$ must have $q<6$, hence $q\in{2,3,4,5}$.

This gives a clean case split:

Lemma 2.1 (three largest proper divisors for $6\mid N$)

1. If $4\mid N$ then the three largest proper divisors are $\frac N2,\frac N3,\frac N4$, hence [ f(N)=\frac N2+\frac N3+\frac N4 = \frac{13}{12}N. ]
2. If $4\nmid N$ but $5\mid N$ then the three largest proper divisors are $\frac N2,\frac N3,\frac N5$, hence [ f(N)=\frac N2+\frac N3+\frac N5 = \frac{31}{30}N. ]
3. If $4\nmid N$ and $5\nmid N$ then the three largest proper divisors are $\frac N2,\frac N3,\frac N6$, hence [ f(N)=\frac N2+\frac N3+\frac N6 = N. ]

Step 3: $5$ never appears in an infinite valid sequence

Assume $5\mid a_n$ for some $n$. From Step 1, $6\mid a_n$, so $30\mid a_n$.

• If $4\nmid a_n$, then Lemma 2.1(2) gives $a_{n+1}=\frac{31}{30}a_n$, which is odd (since $a_n$ has exactly one factor $2$). Contradiction to Lemma 1.1.

Thus whenever $5\mid a_n$ we must have $4\mid a_n$, and Lemma 2.1(1) yields $a_{n+1}=\frac{13}{12}a_n$. This map preserves the factor $5$ but decreases $v_2$ by $2$ each time, so after finitely many steps we reach a term still divisible by $5$ but not by $4$, contradicting the previous paragraph.

Therefore [ 5\nmid a_n\quad\text{for all }n. ]

Step 4: reduction to a $2$-$3$ valuation process

From Steps 1 and 3, for all $n$ we have $6\mid a_n$ and $5\nmid a_n$. Hence Lemma 2.1 reduces to:

[ a_{n+1}=\begin{cases} \frac{13}{12}a_n,&4\mid a_n,\ a_n,&4\nmid a_n. \end{cases} \qquad\text{and always }6\mid a_n. ]

Write $t=v_2(a_1)$ and $s=v_3(a_1)$.

• If $t=1$, then $4\nmid a_1$ so the sequence is constant: $a_n=a_1$.
• If $t\ge 2$, then $4\mid a_1$ and we must apply the map $a\mapsto \frac{13}{12}a$.

To keep $6\mid a_{n+1}$ after a $\frac{13}{12}$ step, we need $12\mid a_n$ and additionally $6\mid a_n/12$, i.e. [ 72\mid a_n \quad\Longleftrightarrow\quad v_2(a_n)\ge 3\text{ and }v_3(a_n)\ge 2. ] Each time we apply $\frac{13}{12}$, [ (v_2,v_3)\mapsto (v_2-2, v_3-1). ] Thus, the number of such steps before $v_2$ reaches $1$ equals [ k = \frac{t-1}{2}. ] This forces $t$ to be odd. After these $k$ steps, $v_3$ becomes $s-k$, and we still need $s-k\ge 1$ in order to remain divisible by $3$. Therefore [ s\ge k+1 = \frac{t+1}{2}. ]

This proves the necessary condition: [ 6\mid a_1,\quad 5\nmid a_1,\quad v_2(a_1)\text{ odd},\quad v_3(a_1)\ge \frac{v_2(a_1)+1}{2}. ]

Step 5: sufficiency

Assume $a_1$ satisfies the condition. Let $t=v_2(a_1)$, $s=v_3(a_1)$, and $k=(t-1)/2$.

• For the first $k$ steps, we have $4\mid a_n$ and $72\mid a_n$, so we may apply $a\mapsto \frac{13}{12}a$, and each term stays divisible by $6$.
• After $k$ steps we reach $a_{k+1}$ with $v_2(a_{k+1})=1$ and $v_3(a_{k+1})=s-k\ge 1$, and still $5\nmid a_{k+1}$.
• Therefore $4\nmid a_{k+1}$ and $5\nmid a_{k+1}$, so Lemma 2.1(3) gives $a_{k+2}=a_{k+1}$ and the sequence is constant from then on.

Finally, every term is divisible by $6$, hence has at least the three proper divisors $\frac N2,\frac N3,\frac N6$. So the sequence is valid for all $n$.

This proves the condition is also sufficient.

Lean4 / mathlib formalization (partial)

Same Lean attachment as in the previous version: it defines next as the sum of the three maxima of Nat.properDivisors, defines the simplified transition g, and sets up the two hard lemmas as sorrys.

import Mathlib.NumberTheory.Divisors
import Mathlib.Data.Finset.Max
import Mathlib.Logic.Function.Iterate

open Finset

namespace DivisorSequence

noncomputable def next (n : ℕ) : ℕ := by
  classical
  let s : Finset ℕ := Nat.properDivisors n
  by_cases h3 : s.card ≥ 3
  ·
    let m1 : ℕ := s.max' (by
      have : 0 < s.card := lt_of_lt_of_le (by decide : (0:ℕ) < 3) h3
      simpa [Finset.card_pos] using this)
    let s1 : Finset ℕ := s.erase m1
    have hs1 : s1.card ≥ 2 := by
      have hm1 : m1 ∈ s := by
        simpa [m1] using s.max'_mem (by
          have : 0 < s.card := lt_of_lt_of_le (by decide : (0:ℕ) < 3) h3
          simpa [Finset.card_pos] using this)
      simpa [s1, Finset.card_erase_of_mem hm1] using (Nat.sub_le_sub_right h3 1)
    let m2 : ℕ := s1.max' (by
      have : 0 < s1.card := lt_of_lt_of_le (by decide : (0:ℕ) < 2) hs1
      simpa [Finset.card_pos] using this)
    let s2 : Finset ℕ := s1.erase m2
    have hs2 : s2.Nonempty := by
      have hm2 : m2 ∈ s1 := by
        simpa [m2] using s1.max'_mem (by
          have : 0 < s1.card := lt_of_lt_of_le (by decide : (0:ℕ) < 2) hs1
          simpa [Finset.card_pos] using this)
      have : s2.card ≥ 1 := by
        simpa [s2, Finset.card_erase_of_mem hm2] using (Nat.sub_le_sub_right hs1 1)
      have : 0 < s2.card := Nat.pos_of_ne_zero (by
        intro h
        have := this
        simp [h] at this)
      simpa [Finset.card_pos] using this
    let m3 : ℕ := s2.max' hs2
    exact m1 + m2 + m3
  ·
    exact 0

noncomputable def g (n : ℕ) : ℕ :=
  if 4 ∣ n then 13 * (n / 12) else n

def Good (n : ℕ) : Prop :=
  ∃ k ℓ m : ℕ, k + 1 ≤ ℓ ∧ Nat.Coprime m 30 ∧ n = 2^(2*k+1) * 3^ℓ * m

theorem g_iterate_on_good {n : ℕ} (hn : Good n) :
    ∃ k ℓ m : ℕ, k + 1 ≤ ℓ ∧ Nat.Coprime m 30 ∧
      ((g^[k]) n = 13^k * 2 * 3^(ℓ-k) * m) ∧
      ((g^[k+1]) n = (g^[k]) n) := by
  classical
  rcases hn with ⟨k, ℓ, m, hkl, hcop, rfl⟩
  refine ⟨k, ℓ, m, hkl, hcop, ?_, ?_⟩
  ·
    induction k with
    | zero =>
        simp [Nat.iterate, g]
    | succ k ih =>
        sorry
  ·
    sorry

theorem next_eq_g_of_mul6 {n : ℕ} (h6 : 6 ∣ n) (h5 : ¬ 5 ∣ n) : next n = g n := by
  sorry

end DivisorSequence

Compilation output

$ cd /opt/lean/Math
$ lake env lean DivisorSequence.lean
DivisorSequence.lean:70:8: warning: declaration uses 'sorry'
DivisorSequence.lean:90:8: warning: declaration uses 'sorry'

Summary

The corrected Step 1 shows that in an infinite valid sequence all terms must be divisible by $6$, using a parity-mod-$3$ argument (Lemma 1.3) rather than the incorrect implication “$f(N)<N$ forces $3\mid N$”. After that, the dynamics reduces to the $\frac{13}{12}$ / identity map on $6\mid N$, $5\nmid N$, and $(v_2,v_3)$ tracking gives the stated complete classification.