Прафесар Halfbrain і сума лічбаў ўсіх дзельнікаў

Учора я сустрэў прафесар Halfbrain ў горадзе. Прафесар выглядаў стомленым і трохі знясіленыя. Ён сказаў мне, што ён праводзіў дні і ночы з сумаваннем лічбаў дзельнікаў станоўчых цэлых лікаў. Напрыклад, у цэлы лік $ N = 12 $ мае шэсць дзельнікаў $ 1,2,3,4,6,12 $ і суму лічбаў гэтых шасці дзельнікаў $ 1 + 2 + 3 + 4 + 6 + 1 + 2 = 19 $. Прафесар пазначыў суму лічбаў ўсіх дзельнікаў $ N $ на $ SDD (N) $, так што, у прыватнасці, $ SDD (12) = 19 $. Прафесар пачаў з некаторым лікам адвольнага $ N $, вылічаецца $ SDD (п) $, то вылічаецца $ SDD (SDD (п)) $, то $ SDD (SDD (SDD (п))) $, і гэтак далей.

<Р> <моцны> тэарэма прафесара Halfbrain у:   Калі мы пачнем з адвольным натуральным лікам $ п \ ge2 $ і итеративно вылічыць суму SDD лічбаў ўсіх дзельнікаў, то ў канчатковым выніку дасягнуць цэлага ліку $ 15 $.

Напрыклад, давайце пачнем з $ n = 4 $. Тады наступны цэлы лік складае $ SDD (4) = 1 + 2 + 4 = 7 $. Наступнае лік складае $ SDD (7) = 1 + 7 = 8 $. Наступнае лік складае $ SDD (8) = 1 + 2 + 4 + 8 = 15 $. Тады мы затрымаліся, як і $ SDD (15) = 1 + 3 + 5 + 1 + 5 = 15 $.

Ці з'яўляецца тэарэма прафесара сапраўды правільна, ці мае прафесар яшчэ раз зрабіў адзін з яго фенаменальных матэматычных пралікаў?

31
Відавочна, што гэта з'яўляецца ілжывым, 1 + 3 + 5 + 1 + 5, можна выкарыстоўваць 1 і 5 двойчы, SDD (15) = 1 + 3 + 5 = 9 не 15
дададзена аўтар Roby, крыніца
@VincentAdvocaat Вы павінны ўзяць суму лічбаў ўсіх дзельнікаў, і з 15 з'яўляецца таксама дзельнікам 15 вы павінны дадаць дзве лічбы яна складаецца з (1 і 5).
дададзена аўтар glglgl, крыніца
Я праверыў ўручную: гэта дакладна для п <1000, так што думаю, што прафесар правоў
дададзена аўтар Jawad Al Shaikh, крыніца
Я праверыў гэта праграмна для значэнняў 2 - 100000. codepad.org/Qv2fv4kD калі anyone'd хочаце скапіяваць мой сцэнар (звярніце ўвагу, што codepad.org скончыўся пасля п = 241, але запусціць яго на маёй лакальнай машыне няхай працуе ўвесь шлях да 100000: speedy.sh/RE8jH /SDDresults.txt )
дададзена аўтар James, крыніца
$ 1 $ ня станоўчае цэлы лік?
дададзена аўтар KoA, крыніца

1 адказы

Тэарэма прафесара Halfbrain з'яўляецца

<Р> True

доказ

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

30
дададзена
Так, вы маеце рацыю. Гэта тое, што я першапачаткова, але я думаў, што гэта можа быць цікава, каб даць ўяўленне пра тое, як вы маглі б паменшыць звязаныя далей, не звяртаючыся непасрэдна да праграмавання.
дададзена аўтар hexomino, крыніца
Так, дзякуй. Я толькі што выправіў.
дададзена аўтар hexomino, крыніца
Зацвярджэнне, што $ SDD (п) <п $ для ўсіх $ п <2500 $, верагодна, варта для ўсіх $ п> 2500 $ замест гэтага.
дададзена аўтар WinW, крыніца
Пасля таго, як вы ёсць, што першыя $ SDD (п) $ звязаны, не проста грубая сіла будзе самым простым рашэннем?
дададзена аўтар atarax42, крыніца
Гэта не падобна на галаваломку, больш падобна проста праблемы матэматыкі.
дададзена аўтар Dan Lyons, крыніца