質問: 15 $のように固まってしまいます。 教授の定理は本当に正しいのですか、あるいは教授は再び彼の驚異的な数学的な失敗を作りましたか?
回答: ハーフブレイン教授の定理は > 真 > > 証明 > > 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$. > > >