Il divisore dispari

[Hawk]

Mostrare che per ogni intero positivo $ n $:
$ 0<\displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}-\dfrac{2n}{3}<\dfrac{2}{3} $

dove $ g(k) $ è il più grande divisore dispari di $ k $.

Avevo dimenticato di scriverlo, grazie ma_go.

[simone256]

Evvai risolto! Stasera se riesco a finire i compiti di italiano lo scrivo ( )

[simone256]

Eccoci... Ora:
Poniamo $ n=(t_0)2^i+(t_1)2^{i-1}+...+(t_{i-1})2+(t_i) $, con $ 0 \le t_a \le 1 $ (come se fosse in base due diciamo...).

Ragioniamo su $ \displaystyle \frac {g(k)}{k} $, per un generico $ k $ avremo una frazione con al numeratore $ 1 $ e al denominatore il fattore primo $ 2 $ con il relativo esponente della scomposizione in fattori primi di $ k $.

$ \displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}=1+\frac {1}{2}+1+\frac{1}{4}+1+\frac{1}{2}+1+\frac{1}{8}+... $ (naturalmente per $ n>8 $).

Ora prendiamo un generico termine della somma $ (t_a)2^j $;
se $ t_a=1 $ con qualche rapido conto che ometto si può affermare che avremo: $ \displaystyle\sum_{k=1}^{2^j} \dfrac{g(k)}{k} = 2^{j-1}+2^{j-3}+2^{j-5}+...+2^{1-j}+2^{-j} = \frac{2^{j+1} - 2^{1-j}}{2^2-1}+2^{-j} = \frac{2^{j+1}}{3}+\frac{-2^{1-j}+(2+1)2^{-j}}{3} = \frac{2^{j+1}}{3}+\frac{2^{-j}}{3} $

Riscriviamo quindi il testo come:
$ 0<\displaystyle\sum_{j=0}^i t_a \left(\frac{2^{j+1}}{3}+\frac{2^{-j}}{3} -\dfrac{2(2^j)}{3} \right)<\dfrac{2}{3} $,

con $ n=(t_0)2^i+(t_1)2^{i-1}+...+(t_{i-1})2+(t_i) $, con $ 0 \le t_a \le 1 $.


Ora è facile capire che per $ n=0 $ si ha l'uguaglianza con lo $ 0 $, mentre se facciamo tendere $ n $ all'infinito si ha l'uguaglianza con $ \displaystyle \frac{2}{3} $...
Ok, mi sono spiegato malissimo. Consigli su come migliorare l'esposizione sono naturalmente ben accetti purché non accompagnati da insulti

[Hawk]

Eccoci... Ora:

Eccoci... Ora:
Poniamo $ n=(t_0)2^i+(t_1)2^{i-1}+...+(t_{i-1})2+(t_i) $, con $ 0 \le t_a \le 1 $ (come se fosse in base due diciamo...).

Ragioniamo su $ \displaystyle \frac {g(k)}{k} $, per un generico $ k $ avremo una frazione con al numeratore $ 1 $ e al denominatore il fattore primo $ 2 $ con il relativo esponente della scomposizione in fattori primi di $ k $.

$ \displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}=1+\frac {1}{2}+1+\frac{1}{4}+1+\frac{1}{2}+1+\frac{1}{8}+... $ (naturalmente per $ n>8 $).

Ora prendiamo un generico termine della somma $ (t_a)2^j $;
se $ t_a=1 $ con qualche rapido conto che ometto si può affermare che avremo: $ \displaystyle\sum_{k=1}^{2^j} \dfrac{g(k)}{k} = 2^{j-1}+2^{j-3}+2^{j-5}+...+2^{1-j}+2^{-j} = \frac{2^{j+1} - 2^{1-j}}{2^2-1}+2^{-j} = \frac{2^{j+1}}{3}+\frac{-2^{1-j}+(2+1)2^{-j}}{3} = \frac{2^{j+1}}{3}+\frac{2^{-j}}{3} $

Qui ho capito tutto tranne quando dicidi prendere un generico termine della somma $ t_a\cdot 2^j $ e poni $ t_a=1 $, però $ n=(t_0)2^i+(t_1)2^{i-1}+...+(t_{i-1})2+(t_i) $ per cui dovresti porre tutti gli altri termini della sequenza uguali a zero, per intenderci tutti gli $ t_i=0 $ tranne quello con la potenza del due che hai scelto. Tra l'altro dovresti scrivere $ t_a \in \{0,1\} $ e non $ 0 \le t_a \le 1 $.
Al di la di notazioni, praticamente mi sembra di capire che spieghi cosa succede nel caso in cui $ n $ è una potenza del due.

Riscriviamo ora il testo come:
$ 0<\displaystyle\sum_{j=0}^i t_a \left(\frac{2^{j+1}}{3}+\frac{2^{-j}}{3} -\dfrac{2(2^j)}{3} \right)<\dfrac{2}{3} $ con $ n=(t_0)2^i+(t_1)2^{i-1}+...+(t_{i-1})2+(t_i) $, con $ 0 \le t_a \le 1 $.

qui non ho capito quello che hai fatto.

[simone256]

Qui ho capito tutto tranne quando dicidi prendere un generico termine della somma $ t_a\cdot 2^j $ e poni $ t_a=1 $, però $ n=(t_0)2^i+(t_1)2^{i-1}+...+(t_{i-1})2+(t_i) $ per cui dovresti porre tutti gli altri termini della sequenza uguali a zero, per intenderci tutti gli $ t_i=0 $ tranne quello con la potenza del due che hai scelto. Tra l'altro dovresti scrivere $ t_a \in \{0,1\} $ e non $ 0 \le t_a \le 1 $.
Al di la di notazioni, praticamente mi sembra di capire che spieghi cosa succede nel caso in cui $ n $ è una potenza del due.

Allora sì hai perfettamente ragione per quanto riguarda la notazione
Io analizzo la differenza $ \displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}-\dfrac{2n}{3} $ scomponendo diciamo sia il minuendo che il sottraendo:
Se $ n=12 $ per esempio, $ n=2^3+2^2 $ e $ \displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}=\left(1+\frac {1}{2}+1+\frac{1}{4}+1+\frac{1}{2}+1+\frac{1}{8} \right)+\left(1+\frac{1}{2}+1+\frac{1}{4} \right) $.
Quindi io sottrarrò prima ragionando su $ n=8 $ e poi su $ n=4 $... E alla fine faccio una sommatoria delle differenze ottenute che è questa cosa qui:

Riscriviamo ora il testo come:
$ 0<\displaystyle\sum_{j=0}^i t_a \left(\frac{2^{j+1}}{3}+\frac{2^{-j}}{3} -\dfrac{2(2^j)}{3} \right)<\dfrac{2}{3} $ con $ n=(t_0)2^i+(t_1)2^{i-1}+...+(t_{i-1})2+(t_i) $, con $ 0 \le t_a \le 1 $.

Che noto adesso sarebbe corretto scrivere:
$ 0<\displaystyle\sum_{j=0}^i t_{i-j} \left(\frac{2^{j+1}}{3}+\frac{2^{-j}}{3} -\dfrac{2(2^j)}{3} \right)<\dfrac{2}{3} $

Lo so è molto incasinato... Ma credo l'idea funzioni!
Almeno spero...

[Hawk]

Allora intanto semplifico la cosa:
$ 0<\displaystyle\sum_{j=0}^i t_{i-j} \left(\frac{2^{j+1}}{3}+\frac{2^{-j}}{3} -\dfrac{2(2^j)}{3} \right)<\dfrac{2}{3} \Rightarrow 0<\displaystyle\sum_{j=0}^i t_{i-j} \frac{2^{-j}}{3}<\dfrac{2}{3} $.
Moltiplichiamo per $ 3 $ ed otteniamo $ 0<\displaystyle\sum_{j=0}^i t_{i-j} \dfrac{1}{2^j}<2 $ che è evidentemente vero.

Non capisco però ancora come ci arrivi. Quello che dici è scomporre $ n $ come somma di potenze del 2 per poter utilizzare $ \displaystyle\sum_{k=1}^{2^j} \dfrac{g(k)}{k}=\frac{2^{j+1}}{3}+\frac{2^{-j}}{3} $? Ma come ti comporti però se $ n $ è dispari?
Oltretutto sarebbe anche falso perchè $ \displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}=\displaystyle\sum_{k=1}^{2^i+2^{i+1}+....} \dfrac{g(k)}{k} \not =\displaystyle\sum_{k=1}^{2^i} \dfrac{g(k)}{k}+\displaystyle\sum_{k=1}^{2^{i+1}} \dfrac{g(k)}{k}...... $
Scusa probabilmente sono io che non capisco, anche perchè in teoria dei numeri so un po' scarso.

[simone256]

Allora intanto semplifico la cosa:
$ 0<\displaystyle\sum_{j=0}^i t_{i-j} \left(\frac{2^{j+1}}{3}+\frac{2^{-j}}{3} -\dfrac{2(2^j)}{3} \right)<\dfrac{2}{3} \Rightarrow 0<\displaystyle\sum_{j=0}^i t_{i-j} \frac{2^{-j}}{3}<\dfrac{2}{3} $.
Moltiplichiamo per $ 3 $ ed otteniamo $ 0<\displaystyle\sum_{j=0}^i t_{i-j} \dfrac{1}{2^j}<2 $ che è evidentemente vero.

Hai perfettamente ragione... Avevo intenzione di semplificarlo ma non so perchè non l'ho fatto ... Ne ero pure convinto

Non capisco però ancora come ci arrivi. Quello che dici è scomporre $ n $ come somma di potenze del 2 per poter utilizzare $ \displaystyle\sum_{k=1}^{2^j} \dfrac{g(k)}{k}=\frac{2^{j+1}}{3}+\frac{2^{-j}}{3} $? Ma come ti comporti però se $ n $ è dispari?

Beh per esempio se $ n=13 $ lo scompongo come $ 2^3+2^2+2^0 $.

Oltretutto sarebbe anche falso perchè $ \displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}=\displaystyle\sum_{k=1}^{2^i+2^{i+1}+....} \dfrac{g(k)}{k} \not =\displaystyle\sum_{k=1}^{2^i} \dfrac{g(k)}{k}+\displaystyle\sum_{k=1}^{2^{i+1}} \dfrac{g(k)}{k}...... $

Mmm... Forse è la stessa cosa ma per la mia scomposizione di $ n $ dovremmo mettere $ \displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}=\displaystyle\sum_{k=1}^{(t_0)2^i+(t_1)2^{i-1}...} \dfrac{g(k)}{k} =\displaystyle\sum_{k=1}^{2^i} \dfrac{g(k)}{k}+\displaystyle\sum_{k=1}^{2^{i-1}} \dfrac{g(k)}{k}... $
Cerco di spiegarti questa cosa che ho scritto sopra che considero vera sennò il mio ragionamento va a farsi benedire (speriamo in bene ):
Se considero $ n=15 $ avremo $ \displaystyle\sum_{k=1}^{15} \dfrac{g(k)}{k}=\left(1+\frac {1}{2}+1+\frac{1}{4}+1+\frac{1}{2}+1+\frac{1}{8} \right)+\left(1+\frac{1}{2}+1+\frac{1}{4} \right)+\left(1+\frac{1}{2} \right)+ \left(1\right) $
Riesci a vedere che è lo stesso se faccio $ \displaystyle\sum_{k=1}^{8}\dfrac{g(k)}{k}+\displaystyle\sum_{k=1}^{4}\dfrac{g(k)}{k}+\displaystyle\sum_{k=1}^{2}\dfrac{g(k)}{k}+\displaystyle\sum_{k=1}^{1}\frac{g(k)}{k} $? Questo perché... Perché... Mmm... A spiegarlo a parole non riesco ! Mi sono basato su una cosa che mi sembra ovvia, ma per dimostrarla dovrei mettermi lì mezzora per trovare un procedimento lineare e chiaro!

Scusa probabilmente sono io che non capisco, anche perchè in teoria dei numeri so un po' scarso.

Guarda... Io davvero sono una pippa in teoria dei numeri e sono ancora più pippa a spiegare e dimostrare... Se poi si aggiunge la fretta che ho sempre

Spero di aver chiarito i tuoi dubbi e spero ancora di più di avere ragione nel mio ragionamento

[EvaristeG]

Questo perché... Perché... Mmm... A spiegarlo a parole non riesco ! Mi sono basato su una cosa che mi sembra ovvia, ma per dimostrarla dovrei mettermi lì mezzora per trovare un procedimento lineare e chiaro!

Mettitici! Quello che si chiede nella soluzione di un esercizio è proprio che tu spieghi per filo e per segno perché quello che dici è vero, oppure che tu faccia riferimento a qualcosa che tutti sanno che è vero (e di solito è roba che sta in qualche libro o comunque viene insegnata , tipo teoremi e cose così).

[simone256]

Cerco di fare qualche ragionamento su qualche congruenza modulo qualcosa...
Avevo pensato a $ 2^i+k \equiv k (\mod 2^{i-1}) $ che funziona... Ma non penso serva a qualcosa... Ora meglio riposare! Ci penso domani a scuola

MODIFICA:
No... Cazzata... Assoluta...
Nella risposta successiva dovrebbe esserci qualcosa di più sensato!

[simone256]

Nuova idea fresca fresca di stamattina:
Dato il ragionamento iniziale della prima risposta, per dimostrare che
$ \displaystyle\sum_{k=1}^n \dfrac{g(k)}{k}=\displaystyle\sum_{k=1}^{(t_0)2^i+(t_1)2^{i-1}...} \dfrac{g(k)}{k} =\displaystyle(t_0)\sum_{k=1}^{2^i} \dfrac{g(k)}{k}+\displaystyle(t_1)\sum_{k=1}^{2^{i-1}} \dfrac{g(k)}{k}+... $,
devo dimostrare che l'esponente del fattore $ 2 $ di un certo numero naturale $ k $ è lo stesso di quello di un numero naturale $ 2^i+k $, con $ k<2^i $.
La dimostrazione è semplice! Basta raccogliere da $ 2^i+k $ e da $ k $ il fattore due con il massimo esponente $ j $ (di sicuro $ j<i $ perché $ k<2^i $).
Avremo nel primo caso $ 2^j(2^{i-j}+\frac{k}{2^j}) $ il cui fattore $ 2 $ ha sempre esponente $ j $ perchè nella tonda abbiamo un valore certamente dispari;
e nel secondo caso è ovvio che l'esponente del $ 2 $ è sempre $ j $.
Spero sia chiaro