Профессор Халфбрайн және барлық бөлгіштердің сандары

Кеше қаланың профессоры Халфбрайнмен кездестім. Профессор қатты шаршап, біраз таусылды. Ол маған түнгі және күндерді оң бүтін сандардың дивизорларын қосу арқылы өткізгенін айтты. Мысалы, $ n = 12 $ бүтін бөлімі алты дивизордан тұрады: $ 1,2,3,4,6,12 $, ал осы алты дивизордың сандары $ 1 + 2 + 3 + 4 + 6 + 1 + 2 = 19 $. Профессор $ n $ $ SDD (n) $ барлық бөлгіштерінің сандарының қосындысын белгіледі, сондықтан $ SDD (12) = 19 $. Профессор $ n $, $ SDD (n) $, содан кейін $ SDD (SDD (n)) $, содан кейін $ SDD (SDD (SDD (n)) $, және тағы басқалардан есептелген кейбір ерікті бүтін санмен басталды.

Профессор Халфбрайн теоремасы:   Егер $ n \ 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, көзі
Мен қолмен тексердім: n <1000 үшін дұрыс, сондықтан профессор дұрыс деп ойлаймын
қосылды автор Jawad Al Shaikh, көзі
Мен оны бағдарлама бойынша 2-ден 100 000-ға дейін тексердім. codepad.org/Qv2fv4kD егер кез келген адам менің сценарийімді көшірмесін (айталық, codepad.org n = 241, бірақ менің жергілікті машинада жұмыс істеуге мүмкіндік береді 100,000: speedy.sh/RE8jH /SDDresults.txt )
қосылды автор James, көзі
$ 1 $ оң бүтін сан емес пе?
қосылды автор KoA, көзі

1 жауаптар

Профессор Халфбрайн теоремасы

Шынайы

Дәлелдеу

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 (n) <2500 $ үшін барлық $ n> 2500 $ болуы керек деген талап.
қосылды автор WinW, көзі
Алғашқы $ SDD (n) $ байланысы бар болған кезде қарапайым күшті күш оңай шешім емес пе?
қосылды автор atarax42, көзі
Бұл тек қана математикалық мәселе сияқты жұмбақ сияқты емес.
қосылды автор Dan Lyons, көзі