Difficile

Messaggioda Valerio Capraro » 13/04/2006, 18:55

Siano $p,q$ due numeri primi e $s$ un intero positivo. Dare una formula asintotica per il numero degli interi minori o uguali di s fattorizzabili solo tramite p e q. Generalizzare ad n primi.
Valerio Capraro
Advanced Member
Advanced Member
 
Messaggio: 1151 di 2528
Iscritto il: 04/02/2004, 00:58
Località: Southampton (UK)

Messaggioda ficus2002 » 13/04/2006, 21:46

Bisogna stimare la cardinalità dell'insieme
${(alpha,beta):p^alpha \cdot q^beta \le s}$
Per ogni $alpha$ tale che $p^alpha\le s$ si ha $q^beta\le s/(p^alpha)$ per ogni $beta=0,1,\ldots,[log (s/p^alpha)/log q]$. Inoltre si ha $p^alpha\le s$ per $alpha=0,1,\ldots,[log (s/p^alpha)]$. Quindi la cardinalità dell'insieme vale $sum_{alpha=0}^{[log s/log p]}[log (s/p^alpha)/log q]$.

Ora osserviamo che $sum_{alpha=0}^{[log s/log p]}log (s/p^alpha)/log q=1/2 (log^2 s) / (log p log q) - 1/2 log s / log q$.

Premettiamo questo
Lemma: Sia $a_k$ una successione. Se definitivamente è $sum_{k=0}^{n} a_n > c n$ per qualche costante $c>1$ allora $sum_{k=0}^{n} [a_k]$ e $sum_{k=0}^{n} a_k$ sono asintotiche per $n \rightarrow +oo$.
Dim: $1- n/(sum_{k=0}^{n} a_k) < (sum_{k=0}^{n} [a_k]) / (sum_{k=0}^{n} a_k) \le 1.

osserviamo che la sommatoria di prima soddisfa le ipotesi del Lemma, quindi $sum_{alpha=0}^{[log s/log p]}[log (s/p^alpha)/log q] ∼ 1/2 (log^2 s) / (log p log q) - 1/2 log s / log q$.
ficus2002
Average Member
Average Member
 
Messaggio: 98 di 596
Iscritto il: 09/02/2006, 18:35

Messaggioda Valerio Capraro » 14/04/2006, 11:51

puoi ancora osservare che $-\frac{1}{2}\frac{lgs}{lgq}=o(lg^2s)$ e toglierlo, mantenendo l'equivalenza asintotica.
E per n primi, idee?

comunque, bravo.. intanto!
Valerio Capraro
Advanced Member
Advanced Member
 
Messaggio: 1154 di 2528
Iscritto il: 04/02/2004, 00:58
Località: Southampton (UK)

Messaggioda ficus2002 » 14/04/2006, 19:52

ubermensch ha scritto:E per n primi, idee?

Ho tentato l'induzione su $n$ ma non è immediata...

ubermensch ha scritto:comunque, bravo.. intanto!

grazie :wink: :!:
ficus2002
Average Member
Average Member
 
Messaggio: 101 di 596
Iscritto il: 09/02/2006, 18:35

Messaggioda Valerio Capraro » 19/04/2006, 17:11

non credo che l'induzione porti a qualcosa... anche perchè la stima che hai trovato va bene solo per n=2.. o meglio: la stima che ho trovato io per n qualsiasi è una generalizzazione della tua, ma è diversa
Valerio Capraro
Advanced Member
Advanced Member
 
Messaggio: 1167 di 2528
Iscritto il: 04/02/2004, 00:58
Località: Southampton (UK)


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti