Divisor-dynamics via 2- and 3-adic valuations: complete classification of all valid starts

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: if the process is infinite, every term is divisible by $6$

Let $N$ be any term of the sequence. Let $d_1>d_2>d_3$ be the three largest proper divisors of $N$, and define [ q_i := \frac{N}{d_i}\qquad(i=1,2,3). ] Then $q_i$ are divisors of $N$, $q_i>1$, and they are distinct; moreover $q_1<q_2<q_3$ and [ d_1+d_2+d_3 = N\left(\frac1{q_1}+\frac1{q_2}+\frac1{q_3}\right). ]

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

Because $N$ is odd, each $q_i$ is odd, hence $q_1\ge 3$, $q_2\ge 5$, $q_3\ge 7$. Therefore [ \frac1{q_1}+\frac1{q_2}+\frac1{q_3}\le \frac13+\frac15+\frac17 = \frac{71}{105}<1, ] so $f(N)=d_1+d_2+d_3 < N$.

Thus if some $a_n$ were odd, the sequence would become strictly decreasing forever (since oddness is preserved: sum of three odd divisors is odd), impossible for a sequence of positive integers with each term $\ge 6$. Hence every $a_n$ is even.

Lemma 1.2: if $N$ is not divisible by $3$ and has at least three proper divisors, then $f(N)<N$

Since $3\nmid N$, none of the $q_i$ equals $3$. Because $N$ is even (by Lemma 1.1 applied to the sequence), we have $q_1=2$. Also $q_2\ge 4$ (if $4\mid N$) and in any case $q_2\ge 5$ if $4\nmid N$. Finally $q_3\ge 5$. In all cases we obtain the uniform bound [ \frac1{q_1}+\frac1{q_2}+\frac1{q_3}\le \frac12+\frac14+\frac15 = \frac{19}{20}<1, ] so again $f(N)<N$.

Therefore no term of an infinite valid sequence can be $\not\equiv 0\pmod 3$, hence every $a_n$ is divisible by $3$.

Combining, in any infinite valid sequence, [ 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. ]

So once $6\mid a_n$ holds, the dynamics depends only on divisibility by $4$ and $5$.

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

Assume for contradiction that $5\mid a_n$ for some $n$. We already know $6\mid a_n$, so $30\mid a_n$.

• If $4\nmid a_n$, then by Lemma 2.1(2) we get [ a_{n+1}=\frac{31}{30}a_n. ] But $a_n$ has exactly one factor $2$ (since $4\nmid a_n$), so dividing by $30$ removes that factor, and multiplying by $31$ does not restore it. Hence $2\nmid a_{n+1}$, contradicting Step 1 (all terms are even).

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 operation does not remove the factor $5$, but it decreases $v_2$ by $2$ each time. After finitely many iterations, $v_2$ drops below $2$ so $4\nmid a_m$ while still $5\mid a_m$, 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$.

But 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 already 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 are allowed to apply $a\mapsto \frac{13}{12}a$, and each term stays divisible by $6$.
• After $k$ steps we reach a number $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 by Lemma 2.1(3) we get $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)

The Lean file below defines next (sum of the three largest proper divisors) using Nat.properDivisors and successive maxima, and introduces the simplified function g capturing the closed-form update for numbers divisible by $6$ and not by $5$.

The two remaining sorrys correspond exactly to:

1. proving the explicit iterate formula for g on the normal form $2^{2k+1}3^\ell m$;
2. proving the key arithmetic lemma next_eq_g_of_mul6 (the divisor-ordering step of Lemma 2.1).

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

-- hard divisor-ordering lemma

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 process is forced into multiples of $6$ and can never contain a factor $5$. On this restricted set, the map is either the identity (when $4\nmid N$) or multiplication by $\frac{13}{12}$ (when $4\mid N$). Tracking $(v_2,v_3)$ yields the exact necessary-and-sufficient condition stated at the beginning.