il piu grande fattore primo di una somma di prodotti dicifre
il piu grande fattore primo di una somma di prodotti dicifre
Sia p(n) il prodotto delle cifre non nulle di un intero positivo n. Calcolare $ \displaystyle \text{gpf}\left(\sum_{1 \le i \le 2009}{p(i)}\right) $
The only goal of science is the honor of the human spirit.
Allora chiamo $ $f(a,b)=\sum_{i=a}^bp(i) $
Inoltre (per comodità poi) noto che $ $\sum_{i=1}^9i=45 $ (quando comparirà un 45 in seguito è implicito che è ottenuto da quest'identità).
Noto che $ $f(1,999)=f(1001,1999) $ dato che in RHS ogni numero ha solo una cifra 1 in più che ovviamente non modifica il prodotto.
Inoltre $ $f(2001,2009)=2\cdot 45=90 $.
In particolare unendo i fatti analizzati ottengo (gli 1,2 identificano 1000,2000)
$ $f(1,2009)=2\cdot f(1,999)+1+2+90 $
Ora devo calcolare $ $f(1,999) $. Considero un numero identificato da 3 cifre anche se a sinistra c'è uno 0 (o 2 zeri).
Divido in 3 casi: due zeri, uno, nessuno zero presente.
La somma dei p(i) con i con 2 zeri è $ $3\cdot 45 $.
La somma dei p(i) con i con 1 zero è $ $3\cdot 45^2 $.
La somma dei p(i) con i senza zeri è $ $45^3 $
Quindi in tutto ora che ho $ $f(1,999) $ posso calcolare $ $f(1,2009) $ che è:
$ $f(1,2009)=2(3\cdot 45+3\cdot 45^2+45^3)+1+2+90=194763 $
facendolo fattorizzare a wolfram mi dice che è
$ $194762=3\cdot 64921 $
Quindi $ $\text{gpf}(f(1,2009))=64921 $
Inoltre (per comodità poi) noto che $ $\sum_{i=1}^9i=45 $ (quando comparirà un 45 in seguito è implicito che è ottenuto da quest'identità).
Noto che $ $f(1,999)=f(1001,1999) $ dato che in RHS ogni numero ha solo una cifra 1 in più che ovviamente non modifica il prodotto.
Inoltre $ $f(2001,2009)=2\cdot 45=90 $.
In particolare unendo i fatti analizzati ottengo (gli 1,2 identificano 1000,2000)
$ $f(1,2009)=2\cdot f(1,999)+1+2+90 $
Ora devo calcolare $ $f(1,999) $. Considero un numero identificato da 3 cifre anche se a sinistra c'è uno 0 (o 2 zeri).
Divido in 3 casi: due zeri, uno, nessuno zero presente.
La somma dei p(i) con i con 2 zeri è $ $3\cdot 45 $.
La somma dei p(i) con i con 1 zero è $ $3\cdot 45^2 $.
La somma dei p(i) con i senza zeri è $ $45^3 $
Quindi in tutto ora che ho $ $f(1,999) $ posso calcolare $ $f(1,2009) $ che è:
$ $f(1,2009)=2(3\cdot 45+3\cdot 45^2+45^3)+1+2+90=194763 $
facendolo fattorizzare a wolfram mi dice che è
$ $194762=3\cdot 64921 $
Quindi $ $\text{gpf}(f(1,2009))=64921 $
Sfrutterei questa proprietà:
$ f(1,10^{k+1}-1)=46\cdot f(1,10^k-1)+45 $
Che riscritta come ricorrenza è (assumendo per comodità p(0)=0):
$ $a_0=0 $
$ $a_{n+1}=46a_n+45 $
A meno di errori grossolani...
Quindi risolvendo si ottiene:
$ $a_n=46^n-1 $
In particolare si ottiene che $ $f(1,10^n)=46^n $
Che è davvero una bella formula :)
p.s. fantastica la soluzione... non me l'aspettavo così pulita xD
$ f(1,10^{k+1}-1)=46\cdot f(1,10^k-1)+45 $
Che riscritta come ricorrenza è (assumendo per comodità p(0)=0):
$ $a_0=0 $
$ $a_{n+1}=46a_n+45 $
A meno di errori grossolani...
Quindi risolvendo si ottiene:
$ $a_n=46^n-1 $
In particolare si ottiene che $ $f(1,10^n)=46^n $
Che è davvero una bella formula :)
p.s. fantastica la soluzione... non me l'aspettavo così pulita xD
potevi anche ragionare così visto che lo 0 "non conta": prendi tutti e soli i numeri di n cifre e dove c'è lo 0 sostituisci 1. E' chiaro che la somma di tutti i prodotti adesso è dato da (1+1+2+3+...+9)^n.. 