The miraculous fish problem: sums of cubes of digits halts to 153 for multiples of 3

90 Views Asked by At

The fun name is a nod to the verse:

So Simon Peter climbed back into the boat and dragged the net ashore. It was full of large fish, $153$, but even with so many the net was not torn. - John 21:11

But we are here to talk about mathematics:

Let $f(n)$ denote the sum of the cubes of the digits of $n$. Let $n_1=n$ be any multiple of $3$. We claim the sequence $n_k=f(n_{k-1})$ converges to the fixed point $n=153$ of $f$.

Proof: If $f(n)=n$ then $10^{d-1} \leq n \leq 729d$ since the sum of the cubes of the digits can at most be $9^3$ individually, and we have $d$ digits. This inequality is only true for $d=1,2,3,4$ and then for $d\geq 5$ we have $10^{d-1} > 729d$. Searching through $1,2\dotsc, 2916$ on a computer for fixed points we find four nontrivial fixed points: $153, 370, 371$, and $407$. Only the first is a multiple of $3$. We can prove either directly that the sum of the cubes of the digits of a multiple of $3$ is also a multiple of $3$ or simply use Fermat's little theorem. Thus every term of the sequence $n_k$ is a multiple of $3$. For $n\geq 10,000$ it follows that $f(n) \leq 5\cdot 729 = 3645\leq 10,000 \leq n$ so $f(n)\leq n$ for $n\geq 10,000$. We can check on a computer that starting from every multiple of $3$ that is less than or equal to $10,000$ eventually halts at $153$. For any multiple of $3$ greater than $10,000$ the iteration maps it to a multiple of $3$ less than $10,000$ by our previous statement, and these all have been checked to halt. Therefore, every multiple of $3$ eventually halts under this sequence at $153$.

Question: I don't really like this proof because it involves searching on a computer. Is there another proof that avoids brute-force searching?

Bonus Question: Can we bound the number of steps to halt: $T_n = \inf\{k\geq 1: n_k = 153\}$ where $n_1=n$ is a multiple of $3$. I believe $T_n \leq 14$. At least I have checked this numerically for all multiples of 3 up to 100,000.