Professor Halfbrain en de som van de cijfers van alle delers

Gisteren ontmoette ik professor Halfbrain in de stad. De professor zag er moe en enigszins uitgeput uit. Hij vertelde me dat hij zijn nachten en dagen had doorgebracht met het optellen van cijfers van delers van positieve gehele getallen. Het gehele getal $ n = 12 $ heeft bijvoorbeeld de zes delers $ 1,2,3,4,6,12 $ en de som van de cijfers van deze zes delers is $ 1 + 2 + 3 + 4 + 6 + 1 + 2 = 19 $. De professor noemde de som van de cijfers van alle delers van $ n $ bij $ SDD (n) $, dus in het bijzonder $ SDD (12) = 19 $. De professor begon met een willekeurig geheel getal $ n $, $ SDD (n) $ berekend, vervolgens $ SDD (SDD (n)) $ berekend, vervolgens $ SDD (SDD (SDD (n))) $, enzovoort.

Stelling van professor Halfbrain:   Als we beginnen met een willekeurig positief geheel getal $ n \ ge2 $ en iteratief de som SDD berekenen van de cijfers van alle delers, bereiken we uiteindelijk het gehele getal $ 15 $.

Laten we bijvoorbeeld beginnen met $ n = 4 $. Het volgende gehele getal is dan $ SDD (4) = 1 + 2 + 4 = 7 $. Het volgende gehele getal is $ SDD (7) = 1 + 7 = 8 $. Het volgende gehele getal is $ SDD (8) = 1 + 2 + 4 + 8 = 15 $. Dan zitten we vast, als $ SDD (15) = 1 + 3 + 5 + 1 + 5 = 15 $.

Is de stelling van de professor echt correct, of heeft de professor opnieuw een van zijn fenomenale wiskundige blunders gemaakt?

31
Uiteraard is dit onwaar, 1 + 3 + 5 + 1 + 5, je gebruikt 1 en 5 tweemaal, SDD (15) = 1 + 3 + 5 = 9 niet 15
toegevoegd de auteur Roby, de bron
@VincentAdvocaat Je moet de som nemen van de cijfers van alle delers, en aangezien 15 ook een deler van 15 is, moet je de twee cijfers die deze bevat (1 en 5) toevoegen.
toegevoegd de auteur glglgl, de bron
Ik heb het handmatig gecontroleerd: het is waar voor n <1000, dus het denkt dat professor gelijk heeft
toegevoegd de auteur Jawad Al Shaikh, de bron
Ik heb het programmatisch getest voor waarden van 2 - 100.000. codepad.org/Qv2fv4kD als iemand mijn script wil kopiëren (merk op dat codepad.org na n n = 241, maar als ik het op mijn lokale computer gebruik, moet het helemaal door 100.000 werken: speedy.sh/RE8jH /SDDresults.txt )
toegevoegd de auteur James, de bron
Is $ 1 $ geen positief geheel getal?
toegevoegd de auteur KoA, de bron

1 antwoord

De stelling van professor Halfbrain is

True

Bewijs

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
toegevoegd
Ja je hebt gelijk. Dat is wat ik oorspronkelijk deed, maar ik dacht dat het misschien interessant zou zijn om een ​​idee te geven van hoe je de band verder zou kunnen reduceren zonder direct te gaan programmeren.
toegevoegd de auteur hexomino, de bron
Ja bedankt. Ik heb het zojuist gecorrigeerd.
toegevoegd de auteur hexomino, de bron
De claim dat $ SDD (n) <2500 $ moet in plaats daarvan voor alle $ n> 2500 $ zijn.
toegevoegd de auteur WinW, de bron
Zodra je die eerste $ SDD (n) $ gebonden hebt, zou een eenvoudige brute kracht dan niet veruit de gemakkelijkste oplossing zijn?
toegevoegd de auteur atarax42, de bron
Dit voelt niet als een puzzel, meer als een wiskundig probleem.
toegevoegd de auteur Dan Lyons, de bron