31
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is $1$ not a positive integer? $\endgroup$ – KoA May 25 '16 at 9:51
  • $\begingroup$ Obviously this is false, 1 + 3 + 5 + 1 + 5, you use 1 and 5 twice, SDD(15) = 1 + 3 + 5 = 9 not 15 $\endgroup$ – Vincent May 25 '16 at 10:05
  • 3
    $\begingroup$ @VincentAdvocaat You have to take the sum of the digits of all divisors, and since 15 is also a divisor of 15 you have to add the two digits it consists of (1 and 5). $\endgroup$ – Wu33o May 25 '16 at 10:11
  • 1
    $\begingroup$ I have checked manually : it is true for n<1000 so it think professor is right $\endgroup$ – Fabich May 25 '16 at 10:52
  • 1
    $\begingroup$ I tested it programmatically for values 2 - 100,000. codepad.org/Qv2fv4kD if anyone'd like to copy my script (note that codepad.org timed out after n=241, but running it on my local machine let it work all the way through 100,000: speedy.sh/RE8jH/SDDresults.txt) $\endgroup$ – Paul L May 25 '16 at 13:51
30
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Once you have that first $SDD(n)$ bound, wouldn't a simple brute force be by far the easiest solution? $\endgroup$ – Yakk May 25 '16 at 15:11
  • 1
    $\begingroup$ Yeah, you're right. That is what I did originally but I thought it might be interesting to give an idea of how you could reduce the bound further without resorting directly to programming. $\endgroup$ – hexomino May 25 '16 at 15:22
  • 12
    $\begingroup$ This doesn't feel like a puzzle, more like just a math problem. $\endgroup$ – Simply Beautiful Art May 25 '16 at 20:04
  • $\begingroup$ The claim that $SDD(n)<n$ for all $n<2500$ should probably be for all $n>2500$ instead. $\endgroup$ – Marc van Leeuwen May 25 '16 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.