OliForum Matematico

Sia $ d(n) $ il più grande divisore dispari di n.
Sia $ D(n)=\sum_{i=1}^n d(i) $ e $ T(n)=\sum_{i=1}^n i $.
Dimostrare che esistono infiniti n tali che $ 3D(n)=2T(n) $.

Era il numero 17 della gara a premi dello stage di parma, risolto da me in autobus alle 08.19 del mattino (Sam mi continuerà a maledire per l'orario di consegna ). Mi è parso bellino, anche se uguale a tutti i problemi con $ d(n) $

Se non m'inganna il sonno, dovrebbero funzionare tutti gli n del tipo $ n=2^k-2 $. Magari domani posto i passaggi...

'notte!

darkcrystal ha scritto:Se non m'inganna il sonno, dovrebbero funzionare tutti gli n del tipo $ n=2^k-2 $. Magari domani posto i passaggi...

'notte!

non ti inganna...
dai posta questi conticini

Raccattando i fogliacci di ieri sera, la mia dimo è questa (ce ne sarà una più corta, ma funziona: perchè sprecarsi? )
Voglio dimostrare per induzione che, posto $ H(k)=D(2^k-2) $, si ha $ H(k)= \frac{2^{2k}+2}{3}-2^k $ con k>1.
Per fare questo ragiono per induzione su k.
H(2)=D(2)=2 e si verifica che la formula vale.
Per calcolare H(k+1), dividiamo gli interi fra 1 e $ 2^k-2 $ in tre gruppi: quelli compresi fra 1 e $ 2^k-2 $, $ 2^k-1 e 2^k $, e infine quelli compresi fra $ 2^k+1 $ e $ 2^k+2^k+2 $
La sommatoria si scrive dunque $ \displaystyle \sum_{i=1}^{2^k-2}d(i) + d(2^k-1)+d(2^k)+\sum_{i=1}^{2^k-2}d(2^k+i) $$ \displaystyle= H(k) + (2^k -1) + 1 + \sum_{i=1}^{2^k-2}d(2^k+i) $.
Per l'ultima sommatoria uso due lemmi che tu stesso hai dimostrato viewtopic.php?t=6719 (inizio con il sostituire d(2^k+i)) e la riscrivo:
$ \displaystyle H(k) + 2^k + H(k) +2^k \left( \sum_{i=1}^{2^k}\frac{d(i)}{i} - \frac{d(2^k-1)}{2^k-1}-\frac{d(2^k)}{2^k} \right) $, da cui son solo pochi conti e si arriva a $ 2H(k) + \frac{2^{2k}+1}{3}-1 $. A questo punto sostituisco il mio H(k) che è per ipotesi induttiva $ H(k)=\frac{2^{2k}+1}{3}-2^k $ ed è un altro semplice conto verificare che la mia relazione è vera.
A questo punto, avendo l'espressione "chiusa" per $ D(2^n-2) $ è banale fare il conto di $ 2T(2^n-2)=2 \frac{(2^n-2)(2^n-1)}{2} = (2^n-2)(2^n-1) $ e scoprire che è proprio uguale a $ 3D(2^n-2) $

Ciao!

Funziona più che bene, ma c'è un modo quasi uguale ma più semplice senza impelagarsi con l'induzione...
Basta notare che se n=2^h, allora è possibile scrivere D(n) in forma chiusa con una progressione geometrica alla quale va aggiunto uno, per trovare D(2^h-2) basta poi togliere d(n)=d(2^h)=1 e d(n-1)=d(2^h-1)=2^h-1 e sviluppare i calcoli, senza incasinarsi troppo la vita