Professor Halfbrain and the sum of the digits of all divisors

Question

Yesterday I met professor Halfbrain in the city. The professor looked tired and somewhat exhausted. He told me that he had spent his nights and days with adding up digits of divisors of positive integers. For instance the integer $n=12$ has the six divisors $1,2,3,4,6,12$, and the sum of the digits of these six divisors is $1+2+3+4+6+1+2=19$. The professor denoted the sum of the digits of all divisors of $n$ by $SDD(n)$, so that in particular $SDD(12)=19$. The professor started with some arbitrary integer $n$, computed $SDD(n)$, then computed $SDD(SDD(n))$, then $SDD(SDD(SDD(n)))$, and so on.

Professor Halfbrain's theorem: If we start with an arbitrary positive integer $n\ge2$ and iteratively compute the sum SDD of the digits of all divisors, then we eventually reach the integer $15$.

For example, let us start with $n=4$. Then the next integer is $SDD(4)=1+2+4=7$. The next integer is $SDD(7)=1+7=8$. The next integer is $SDD(8)=1+2+4+8=15$. Then we are stuck, as $SDD(15)=1+3+5+1+5=15$.

Is the professor's theorem really correct, or has the professor once again made one of his phenomenal mathematical blunders?

Answer 1

Professor Halfbrain's theorem is

True

Proof

If we let the number of divisors of a positive integer $n$ be denoted $d(n)$, then an easy upper bound to get on this value is $$d(n) < 2\sqrt{n}.$$ The reasoning here is that each divisor less than the square root "pairs off" with one greater so there is a 1-1 mapping between the divisors less than the square root and greater than the square root. If the number $n$ is a square then its root pairs with itself.

The number of digits in each of these divisors is $ \le \lfloor \log_{10}(n) \rfloor +1$ and each digit is $\le 9$ so a "very loose" upper bound on $SDD(n)$ is $$ SDD(n) < 9 (2 \sqrt{n}) (\lfloor \log_{10}(n) \rfloor + 1 )$$

For $n = 10000$, we have $\sqrt{n} > 18(\lfloor \log_{10}(n) \rfloor + 1)$ and since the slope of the function on the left is always greater than that on the right for $n > 10000$, we find that

For $n \ge 10000$, $$ SDD(n) < n $$

Hence, iteratively applying $SDD$ to numbers greater than $10000$ will eventually yield a number less than $10000$.

We know that the largest highly composite number less than $10000$ is $7560$ which has $64$ divisors. This means that all integers $n <10000$ have less than or equal to $64$ divisors so that (using the inequalities above) $$ SDD(n) < 64(9)(\lfloor \log_{10}(n) \rfloor + 1)$$ and using this inequality, it's easy to verify that $SDD(n) < n$ for $n>2500$.

We can apply this reasoning a couple of more times to reduce the bound again but it's not too hard to check (I wrote a quick python script) that the inequality $SDD(n) < n$ holds for $48 < n < 2500$. Hence, for any $n > 48$, repeatedly iterating $SDD$ to the number eventually yields a number $\le 48$. Thus, it suffices to check the cases where $n \le 48$.

In fact, you can narrow this down a little more and only check those $n \le 48$ for which $SDD(n) \ge n$ holds (using a similar reasoning as before). For $n \ge 2$, the integers that satisfy that inequality are $n = 2,3,4,5,6,7,8,9,12,14,15,16,18,24,28,36,48$

The example in the question has checked it for case $4,7,8$ and $15$. Further, we have $SDD(3) = 4$ and $SDD(2)=3$ which confirms it for these cases.
Then, $SDD(5)=6$, $SDD(6)=12$, $SDD(12) = 19$, $SDD(19) = 11$, $SDD(11) = 3$ and applying to $3$ iteratively gets to $15$. This confirms it for $5,6$ and $12$
Also, $SDD(9) = 13$ and $SDD(13) = 5$, which confirms it for $9$ and $SDD(14) = 15$ which confirms it for $14$.
For $n=16$, $SDD(16) = 22$ and $SDD(22) = 9$
For $n=18$, $SDD(18) = 30$, $SDD(30) = 27$ and $SDD(27) = 22$.
For $n=24$, $SDD(24) = 33$ and $SDD(33) = 12$.
For $n=28$, $SDD(28) = 29$ and $SDD(29) = 12$.
For $n=36$, $SDD(36) = 46$ and $SDD(46) = 18$.
Finally, for $n=48$, $SDD(48) = 52$, $SDD(52)= 26$ and $SDD(26) = 15$.