OliForum Matematico

Problema: siano $ n\in\mathbb{N}_0 $ ed $ x_n $ il numeratore della frazione ridotta rappresentativa dell'$ n $-esimo numero armonico $ \displaystyle H_n = 1 + \frac{1}{2} + \ldots + \frac{1}{n} $. E' vero o falso ch'esistono finiti $ n\in\mathbb{N}_0 $ tali che $ x_n $ sia divisibile per $ 5 $ ?

Questo e il risultato di un giorno di lavoro… Probabilmente ho preso qualche abbaglio: ci sono alcune cosa che non ho voglia di controllare… perdonatemi… ognuno fa quel che puo, no ???


STEP 1: la max potenza di 5 che compare in un numero nell’intervallo [1,n] deve comparire almeno 4 volte.

Dimo : Suppongo che 5^k / n! (dove n! e il denominatore brutale senza semplificazioni) e 5^z la max potenza di 5 che divida un n nell'intervallo. Facendo il mcd ogni numero al numeratore risulta divisibile per 5^(k-z+1) meno alcuni numeri divisibili solo per 5^(k-z). Essi possono essere solo i numeratori relativi ai numeri i*5^z con 1<=i<=4. E compaiono nella somma al numeratore come n ! / (5^z*i). Dato che 1, 1+1/2, 1+1/2+1/3 non sono divisibili per 5 al numeratore in questi casi si avrebbe che il numeratore totale e somma di un numero divisibile per 5^(k-z+1) e di uno non divisibile. La non divisibilita del numeratore per 5^(k-z+1) segue… dato che 1+1/2+1/3+1/4 al numeratore e divisibile per 5 non possiamo avere il medesimo assurdo ma cmq abbiamo apparentemente guadagnato lo STEP1…

STEP 2 : contiamo i numeri in questo modo. Prima sommiamo le potenze di 5 e poi i numeri primi con 5 e raccogliamo, ottenendo al numeratore :

[n !/ 5+n !/5^2+…+n !/5^z] (1+1/2+1/3+1/4) + n! [Sum(1/i)]

dove la sommatoria e estesa ai numeri i primi con 5. Raccogliendo e svolgendo le serie geometriche :

n! * 25/24 * (5^z-1)/5^(z-1) + n! [Sum(1/i)]

il primo termine e divisibile solo per 5^(k-z+3) mentre il secondo almeno per 5^k (questo perche gli i sono primi con 5)… Quindi il numeratore e divisibile solo per 5^(k-z+3)… infatti se fosse divisibile per 5^(k-z+2) un termine sarebbe divisibile ma non l’altro, portando alla conclusione…

Scegliendo z abbastanza grande i ragionamenti sopra dovrebbero funzionare e abbiamo che il numeratore possiede meno fattori di 5 del denominatore, suggerendo che i casi siano finiti… (in particolare credo vada bene solo 1+1/2+1/3+1/4…)

Leggere le tue soluzioni, riuscerndo a coglierne il senso occulto, è spesso un'impresa eroica, mio caro info...

info ha scritto:STEP 1: la max potenza di 5 che compare in un numero nell’intervallo [1,n] deve comparire almeno 4 volte.

Mi spieghi che cavolo significa? Sarò tonto, ma questo per me non è né italiano né matematichese... Forse c'è sottinteso qualcosa del tipo "Se blahblabhblah allora la massima potenza di 5 che bluhbluhbluh è tale da comparire almeno 4 volte?" Ti spiacerebbe essere un pochetto più chiaro, in nome di Cicero?

info ha scritto:Dimo : Suppongo che 5^k / n! (dove n! e il denominatore brutale senza semplificazioni) e 5^z la max potenza di 5 che divida un n nell'intervallo.

Che casino... Vediamo se ho capito! Fissato un $ n\in\mathbb{N}_0 $, poniamo $ k = v_5(n!) $ e $ z_i = v_5(i) $, per ogni $ i = 1, 2, \ldots, n $. Qui $ v_5(\cdot) $ è la valutazione $ 5 $-adica dell'intero passato per argomento (click). Qual che sia $ i = 1, 2, \ldots, n $, si può scrivere allora $ i = 5^{z_i} \cdot q_i $ ed $ n! = 5^k \cdot q $, dove $ q, q_i \in \mathbb{N}_0 $ e $ \gcd(5, q_i) = \gcd(5,q) = 1 $.

info ha scritto:Facendo il mcd ogni numero al numeratore risulta divisibile per 5^(k-z+1) meno alcuni numeri divisibili solo per 5^(k-z).

Con le notazioni del problema: $ \displaystyle x_n \mid \sum_{i=1}^n 5^{k-q_i} \cdot t_i $, dove $ t_i = q/q_i $ è un intero positivo, per ogni $ i = 1, 2, \ldots, n $.

Mo' vado in palestra, più tardi magari continuo nella mia opera di traduzione in lingua italiana dall'infolandese... Nel frattempo, se puoi, fammi sapere se ho capito bene il senso di quel che hai scritto, fino al punto in cui sono arrivato a leggere. Ciao...

HiTLeuLeR ha scritto:Leggere le tue soluzioni, riuscerndo a coglierne il senso occulto, è spesso un'impresa eroica, mio caro info...

info ha scritto:STEP 1: la max potenza di 5 che compare in un numero nell’intervallo [1,n] deve comparire almeno 4 volte.

Mi spieghi che cavolo significa? Sarò tonto, ma questo per me non è né italiano né matematichese... Forse c'è sottinteso qualcosa del tipo "Se blahblabhblah allora la massima potenza di 5 che bluhbluhbluh è tale da comparire almeno 4 volte?" Ti spiacerebbe essere un pochetto più chiaro, in nome di Cicero?

Alura, se n e tale che il numero armonico al numeratore rispetta le ipotesi del problema allora n deve possedere anche questa proprieta... mi sembrava sottointeso, cmq... cosi va meglio ... Cmq consolati, tanto di sol ne scrivo ben poche... ogni tanto ti tocca ....vai avanti, mio buon Ercole... ah... per il bluhbluhbluh vedi dopo (la definizione di z insomma)

HiTLeuLeR ha scritto:

info ha scritto:Dimo : Suppongo che 5^k / n! (dove n! e il denominatore brutale senza semplificazioni) e 5^z la max potenza di 5 che divida un n nell'intervallo.

Che casino... Vediamo se ho capito! Fissato un $ n\in\mathbb{N}_0 $, poniamo $ k = v_5(n!) $ e $ z_i = v_5(i) $, per ogni $ i = 1, 2, \ldots, n $. Qui $ v_5(\cdot) $ è la valutazione $ 5 $-adica dell'intero passato per argomento (click). Qual che sia $ i = 1, 2, \ldots, n $, si può scrivere allora $ i = 5^{z_i} \cdot q_i $ ed $ n! = 5^k \cdot q $, dove $ q, q_i \in \mathbb{N}_0 $ e $ \gcd(5, q_i) = \gcd(5,q) = 1 $.

Davvero questa parte e cosi incasinata? cmq no, non ho aggiunto notazioni su zi, io parlavo solamente di z che se vuoi e il max dell'insieme avente come elementi tutti i zi da te definiti... Per quanto riguarda il resto mi pare sia a posto...

HiTLeuLeR ha scritto:

info ha scritto:Facendo il mcd ogni numero al numeratore risulta divisibile per 5^(k-z+1) meno alcuni numeri divisibili solo per 5^(k-z).

Con le notazioni del problema: $ \displaystyle x_n \mid \sum_{i=1}^n 5^{k-q_i} \cdot t_i $, dove $ t_i = q/q_i $ è un intero positivo, per ogni $ i = 1, 2, \ldots, n $.

mmm... per sicurezza rispiego in breve... Per ottenere la frazione io ho fatto il mcd brutale.... cioe ho l'identita:

1+1/2+1/3+...+1/n = [n! /1+n!/2+...+n!/n]/n!

la frazione non e ridotta ai minimini termini ma per i nostri scopi ci basta dimostrare che se x_n NON gode della proprieta allora la max potenza di 5 che divide il numeratore (che faccio notare e una somma di interi) e minore di 5^k (con k deifinito)... Il numeratore ha termine generico n! / m con m appartenente ad [1,m], e cioe 5^(k-z+1) divide tutti i termini meno quelli per cui m contiene una potenza di 5^z... Con i ragionamenti dopo si vorrebbe vedere che di questi particolari m ce ne devono essere per forza 4 (piu di 4 non possono essere)... con lo STEP 2 anche questo vorrebbe essere eliminato...

HiTLeuLeR ha scritto: Mo' vado in palestra, più tardi magari continuo nella mia opera di traduzione in lingua italiana dall'infolandese... Nel frattempo, se puoi, fammi sapere se ho capito bene il senso di quel che hai scritto, fino al punto in cui sono arrivato a leggere. Ciao...

ok ok... la palestra fa sempre bene!!!! Ma dato che l'hai fatta ieri ti sarai ripreso per continuare l'avventurosa lettura, no?

Inizio a capire... Riscrivo il tutto a parole mie, per accertarmi di aver effettivamente inteso bene!

Claim #1: essendo $ n\in\mathbb{N}_0 $, poniamo $ z_i = v_5(i) $, per ogni $ i = 1, 2, \ldots, n $, e $ \displaystyle z = \max_{1 \leq i \leq n} {z_i} $. E allora $ 4 \cdot 5^{z} \leq n $.

Dim.: essendo $ k = v_5(n!) $, esistono $ q, q_1, \ldots, q_n \in \mathbb{N}_0 $, con $ \gcd(5, q) = \gcd(5, q_1) = \ldots = \gcd(5, q_n) = 1 $, tali che $ n! = 5^k q $ ed $ i = 5^{z_i} q_i $, per ogni $ i = 1, 2, \ldots, n $. Dunque $ H_n = \displaystyle \frac{1}{5^k q} \sum_{i=1}^n 5^{k-z_i} \cdot t_i $, dove $ t_i = q/q_i $ è un intero, qual che sia $ i = 1, 2, \ldots, n $. Da qui $ H_n = \displaystyle \frac{1}{5^z q} \sum_{i=1}^n 5^{z-z_i} \cdot t_i = \frac{1}{5^z q} \left(\sum_{i\in \mathcal{M}} t_i + \sum_{i\in\mathcal{N}-\mathcal{M}}5u_i\right) $, dove $ \mathcal{N} = \{1, 2, \ldots, n\} $; $ \mathcal{M} = \{i\in\mathcal{N}: z_i = z\} $ ed $ u_i = 5^{z-z_i -1} \cdot t_i $ è un intero, per $ i\in\mathcal{N}-\mathcal{M} $, eccetto nel caso in cui la seconda sommatoria sia vuota, e quindi (comunque) uguale a zero.

Sostanzialmente, si tratta di provare che $ \mathcal{M} = \{5^z, 2 \cdot 5^z, 3\cdot 5^z, 4 \cdot 5^z\} $. Intanto è ovvio che ogni elemento di $ \mathcal{M} $ dev'essere della forma $ 5^z \cdot v $, con $ v\in\mathbb{N}_0 $ e $ \gcd(v,5) = 1 $. Inoltre, se $ 5^z \cdot v \in \mathcal{M} $, per qualche $ v \in\mathbb{N}_0 $, allora nondimeno $ 5^z \cdot u \in \mathcal{M} $, per ogni $ u = 1, 2, \ldots, v $. Infine $ v \leq 4 $, poiché altrimenti $ 5^{z+1} \leq n $, contro l'ipotesi di massimalità di $ z $. Senonché $ 5 \mid x_n $ solo se $ \displaystyle\sum_{i\in\mathcal{M}} t_i \equiv 0 \bmod 5 $, e quindi $ 1 + 2^{-1} + \ldots + v^{-1} \equiv 0 \bmod 5 $, dove gli inversi sono appunto calcolati in $ \mathbb{Z}/5\mathbb{Z} $. Da qui (fatte due verifiche) $ v = 4 $, e quindi la tesi, q.e.d.

Quest'è come ho interpretato lo step #1 della tua presunta soluzione. Se mi confermi il tutto, passo subito a leggere il seguito... In ogni caso ti anticipo che le tue conclusioni (sì, gli ho dato un'occhiata!) sono certamente sbagliate. E giusto per farti capire cosa intendo: $ x_4 \equiv x_{20} \equiv x_{24} \equiv 0 \bmod 5 $.

beh... confermo... cmq perlomeno i tuoi risultati sono negli intervalli consentiti dallo STEP 1... almeno quello e corretto insomma... forse mi dovrei dedicare a problemi piu alla mia portata... bah... ma dov'e l'errore? [spero che lo STEP 2 sia comprensibile: ho solo svolto i calcoli al numeratore dividendo potenze di 5 e non]

ciao!

ps: colgo cmq l'occasione per ringraziarti delle correzioni...

Procediamo per induzione

Abbiamo che $ H_4 $ è tale che il suo numeratore sia divisibile per $ 5 $. Ora supponiamo che $ H_n $ soddisfi questa proprietà.

Vediamo cos'è il numero $ H_{5n} $. Scriviamolo raccogliendo tutti i termini col 5 e quelli senza 5:

$ \displaystyle H_{5n}=\frac 15 ( \frac 11+ \frac 12+...+\frac 1n) + $
$ \displaystyle +(\frac 11+\frac 12 + \frac 13+ \frac 14)+(\frac 16+..+\frac 19)+...+(\frac 1{5n-4}+..+\frac 1{5n-1}) $

Ora chiamando la somma di tutti i termini in cui non compare il 5 $ \frac pq $ con $ q $ non divisibile per $ 5 $ ovviamente, abbiamo che:
$ \displaystyle H_{5n}=\frac 15H_n + \frac pq $
ma, per ipotesi induttiva $ H_n $ è della forma $ \frac {5r}s $ con $ s $ non divisibile per $ 5 $ allora abbiamo che:
$ \displaystyle H_{5n}=\frac ab $
dove $ b $ non è multiplo di $ 5 $. Ma allora tra $ H_{5n},H_{5n+1},..,H{5n+4} $ ci sarà sicuramente una frazione tale che 5 divide il suo numeratore essendo vero che modulo 5 essa sarà $ 0 $

info ha scritto:STEP 2 : contiamo i numeri in questo modo. Prima sommiamo le potenze di 5 e poi i numeri primi con 5 e raccogliamo, ottenendo al numeratore :

[n !/ 5+n !/5^2+…+n !/5^z] (1+1/2+1/3+1/4) + n! [Sum(1/i)]

dove la sommatoria e estesa ai numeri i primi con 5. Raccogliendo e svolgendo le serie geometriche :

n! * 25/24 * (5^z-1)/5^(z-1) + n! [Sum(1/i)]

il primo termine e divisibile solo per 5^(k-z+3) mentre il secondo almeno per 5^k (questo perche gli i sono primi con 5)… Quindi il numeratore e divisibile solo per 5^(k-z+3)… infatti se fosse divisibile per 5^(k-z+2) un termine sarebbe divisibile ma non l’altro, portando alla conclusione…

Sì, info, il tuo ragionamento è meravigliosamente corretto!!! Solo bisogna sistemare qualche piccolo dettaglio (vedi i passaggi segnati in grassetto). Tutto nasce chiaramente da un errore di calcolo. Ché infatti $ \displaystyle\sum_{k=1}^z 5^{-k} = \frac{1 - 5^{-(z+1)}}{1-5^{-1}} - 1 = \frac{5 - 5^{-z}}{4} - 1 = \frac{5^z - 1}{4 \cdot 5^z} $. Correggi appena puoi, mi raccomando! E sta' pure tranquillo: le conclusioni sono comunque salve... Ah, dimenticavo...

info ha scritto:[...] Scegliendo z abbastanza grande [...]

Sì, ché forse avresti fatto molto meglio a dichiarare fin dall'inizio che i tuoi argomenti sono appunto fondati sull'assunzione che $ n $ sia sufficientemente grande, nel corso dei calcoli. Magari a priori non ne sarebbe stato chiaro il perché, ma se ci pensi un attimo...

Conclusioni: esistono soltanto finiti $ n\in\mathbb{N}_0 $ tali che $ 5 \mid x_n $, e sono tutti e soli $ < 5^3 $.

Davvero un ottimo lavoro, info caro! Bravo bravo bravo... Non c'è alcun dubbio che il problema fosse impegnativo. Ancora complimenti!!!

Come è successo già in passato, Simo, le tue idee si perdono fra le pieghe di argomenti eristici, di cui (naturalmente) non ti dai pena di fornire dimostrazione, ma che piuttosto assumi per buoni sulla base di chissà quale vago sentore di verità...

Simo_the_wolf ha scritto:[...] allora tra $ H_{5n},H_{5n+1},..,H_{5n+4} $ ci sarà sicuramente una frazione tale che 5 divide il suo numeratore [...]

Bene... Lascio a te il piacere di scovare il baco nella tua soluzione! Ma per tutta risposta ti notifico che $ x_{100} \equiv 1 \bmod 5 $ e $ x_{101} \equiv x_{104} \equiv 3 \bmod 5 $, sebbene $ x_{20} \equiv 0 \bmod 5 $. Ché d'altro canto il nostro info ha dimostrato - lui sì! - che esistono solo finiti $ n\in\mathbb{N}_0 $ tali che $ x_n \equiv 0 \bmod 5 $, per cui...

Ok, ho fallato...
Vediamo di rimediare al mio errore.

Innanzitutto introduciamo un lemma che dice:
$ \folall k \in N_0 $
$ \displaystyle \frac 1{5k+1}+\frac 1{5k+2}+\frac 1{5k+3}+\frac 1{5k+4} \equiv 0 \pmod{25} $

Dimostrazione.

$ \displaystyle \frac 1{5k+1}+\frac 1{5k+2}+\frac 1{5k+3}+\frac 1{5k+4} = $
$ \displaystyle=\frac {50(10k^3+15k^2+7k+1)}{(5k+1)(5k+2)(5k+3)(5k+4)} \equiv 0 \pmod{25} $

Da questo si deduce subito che $ \displaystyle H_{5a+s} \equiv \frac {H_a}5 +\sum_{k=1}^s \frac 1{5a+k} \pmod{25} $ (dove $ s<5 $) e quindi se $ 5|H_n $ allora deve essere che $ \displaystyle 5|H_{\lfloor \frac n5 \rfloor} $ (se non fosse così $ H_n $ avrebbe un 5 al denominatore). Andando indietro ci deve essere un $ r<5 $ tale che $ 5|H_r $ e l'unico è $ H_4=\frac {25}{12} $

Riguardando la formula sopra vediamo che $ \displaystyle \sum_{k=1}^s \frac 1{5a+k} \equiv H_s \pmod{5} $ e quindi abbiamo che $ H_{5a+s} \equiv \frac {H_a}5 + H_s \pmod{5} $ dove $ H_0=0 $ come nostra definizione.

Ora procediamo a ritroso a partire da 4 e diciamo subito che gli unici interi $ 4<n<25 $ tali che $ 5|H_n $ devono essere tali che $ \lfloor \frac n5 \rfloor =4 $ per le ragioni esposte prima e per il fatto che l'unico intero moniore di 5 che soddisfa le nostre ipotesi è 4.

Quindi abbiamo $ n=5*4+s $ con $ 0\leq s<5 $. Quindi $ H_n \equiv \frac 5{12} +H_s \equiv H_s \pmod{5} $ e per le osservazioni fatte prima $ s=0,4 $. Ora sappiamo che:

$ \displaystyle H_{24}\equiv H_{20}+ \sum_{k=1}^4 \frac 1{20+k} \equiv H_{20} \equiv \frac {H_4}5 \pmod{25} $
$ \displaystyle \frac {H_{24}}5\equiv \frac {H_{20}}5 \equiv \frac {H_4}{25}\equiv 3 \pmod{5} $

Ora abbiamo che, sempre per le ragioni prima esposte, gli unici interi $ 24<n<125 $ che possono soddisfare le condizione devono essere tali che $ \lfloor \frac n5 \rfloor=20,24 $ ma abbiamo che:
$ \displaystyle H_{20*5+s} \equiv \frac {H_{20}}5 +H_s \equiv 3+H_s \pmod{5} $
$ \displaystyle H_{24*5+s} \equiv \frac {H_{24}}5 +H_s \equiv 3+H_s \pmod{5} $
Ma $ H_s\equiv -1,0,1 \pmod{5} $* per $ 0\leq s<5 $ e quindi $ H_n $ non potrà mai soddisfare le condizioni per $ n>25 $. Ergo esistono finiti n, in particolare 4, 20, 24 tali che il numeratore di $ H_n $ sia divisibile per 5.

Spero questa volta di aver fatto bene...

*$ H_0 \equiv 0 \pmod{5} $
$ H_1 = 1 \equiv 1 \pmod{5} $
$ H_2 = \frac 32 \equiv -1 \pmod{5} $
$ H_3 = \frac {11}6 \equiv 1 \pmod{5} $
$ H_4 \equiv 0 \pmod{5} $