Delirii da matematici
mentre forse qualcuno (me compreso) si danna per dimostrare che k non divide mai 2^k - 1, do un altro esercizio semplice semplice (uhuh)
Per ogni primo dispari p si definisce sugni interi positivi n la funzione
Lp(n) = #{2 <= m <= n tale che (p^m - 1)/2m è un intero positivo}
darne una stima asintotica.
bah...
ciao, ubermensch
Per ogni primo dispari p si definisce sugni interi positivi n la funzione
Lp(n) = #{2 <= m <= n tale che (p^m - 1)/2m è un intero positivo}
darne una stima asintotica.
bah...
ciao, ubermensch
Risposte
sembra vi sia un inaspettato legame con il logaritmo in base due di n... addirittura per p=3 sembra risulti
L3(n) = lg2(n)
L3(n) = lg2(n)
e l' esercizio quale sarebbe? 
"ubermensch":
mentre forse qualcuno (me compreso) si danna per dimostrare che k non divide mai 2^k - 1, do un altro esercizio semplice semplice (uhuh)
ma se $k=1$ allora abbiamo $2^1-1=1$ che e' divisibile per $k=1$, oppure non valgono i casi in cui $2^k-1=k$? (che poi questo è l' unico
)
Scusate so un pò rincoglionito.. ho corretto tutto
"ubermensch":
mentre forse qualcuno (me compreso) si danna per dimostrare che k non divide mai 2^k - 1, do un altro esercizio semplice semplice (uhuh)
Per ogni primo dispari p si definisce sugni interi positivi n la funzione
Lp(n) = #{2 <= m <= n tale che (p^m - 1)/2m è un intero positivo}
darne una stima asintotica.
bah...
ciao, ubermensch
Cercherò di dimostrare qualcosa riguardo a L2(n), però a mio parere dovresti definire la funzione anche per i numeri che non sono primi.
Ciao,ciao
cerca di rilassarti un po' 
"eafkuor":
cerca di rilassarti un po'
Dici a me?
per p=2 non è definita la funzione.. solo per primi dispari..
per ora vediamo il caso p primo dispari.. poi si vedrà
per ora vediamo il caso p primo dispari.. poi si vedrà
"carlo23":
[quote="eafkuor"]cerca di rilassarti un po'
Dici a me?[/quote]
no mi riferivo a uber (che afferma di essere un po' rincoglionito) pensando che la causa fosse l' impressionante quantita' di tempo che egli dedica alla matematica
"ubermensch":
per p=2 non è definita la funzione.. solo per primi dispari..
per ora vediamo il caso p primo dispari.. poi si vedrà
Si è vero, volevo dire L3(n).
Magari questo può essere utile:
$2^(n+1)$ divide sempre $a^(2^n)-1$ con $a$ dispari >1
Dimostrazione
per induzione
1)$n=0$: $1$ divide certamente $a^(1)-1$
2)se $2^(n+1)$ divide $a^(2^n)-1$ allora $2^(n+2)$ divide $a^(2^(n+1))-1$ infattti si ha
$a^(2^(n+1))-1=(a^(2^n)-1)(a^(2^n)+1)$
e essendo $a$ dispari la 2 segue immediatamente
Questo è sufficiente a dimostrare che Lp(n) diverge per n --> infinito, più precisamente si ha
$Lp(2^n)>n-1$
e
$Lp(n)>int(lg_2(n)-1)$
l'intuizione di ubermensch riguardo al legame con il logaritmo base 2 era giusta!
$2^(n+1)$ divide sempre $a^(2^n)-1$ con $a$ dispari >1
Dimostrazione
per induzione
1)$n=0$: $1$ divide certamente $a^(1)-1$
2)se $2^(n+1)$ divide $a^(2^n)-1$ allora $2^(n+2)$ divide $a^(2^(n+1))-1$ infattti si ha
$a^(2^(n+1))-1=(a^(2^n)-1)(a^(2^n)+1)$
e essendo $a$ dispari la 2 segue immediatamente
Questo è sufficiente a dimostrare che Lp(n) diverge per n --> infinito, più precisamente si ha
$Lp(2^n)>n-1$
e
$Lp(n)>int(lg_2(n)-1)$
l'intuizione di ubermensch riguardo al legame con il logaritmo base 2 era giusta!
bravo carlo... anche perchè il legame con lg2(n) discende proprio da quella proprietà!!
e c'è di più...
ho fatto delle verifiche fino a p=101 e n=2^20 e ho trovato il seguente risultato:
1) in tutti i casi Lp(n) è asintotico a lg2(n) (nel senso che fino a 2^20 il rapporto fra le due funzioni è molto vicino ad 1.. inoltre la convergenza sembra monotona decrescente per n>=12)
2) in alcuni casi (esattamente 11) si ha Lp(n) = lg2(n)
fantastico!!
quasi quasi aprirei la caccia alla dimostrazione!!
ciao
e c'è di più...
ho fatto delle verifiche fino a p=101 e n=2^20 e ho trovato il seguente risultato:
1) in tutti i casi Lp(n) è asintotico a lg2(n) (nel senso che fino a 2^20 il rapporto fra le due funzioni è molto vicino ad 1.. inoltre la convergenza sembra monotona decrescente per n>=12)
2) in alcuni casi (esattamente 11) si ha Lp(n) = lg2(n)
fantastico!!
quasi quasi aprirei la caccia alla dimostrazione!!
ciao
"ubermensch":
quasi quasi aprirei la caccia alla dimostrazione!!
L'ideale sarebbe trovare una funzione F(n) > Lp(n) e tale che $lim sup_n F(n)-lg_2(n)=C $ dove C è una costante.
"ubermensch":
bravo carlo... anche perchè il legame con lg2(n) discende proprio da quella proprietà!!
Ma allora ci eri già arrivato.
Comunque in Teoria dei Numeri sono sorprendenti i legami che i logaritmi hanno con le funzioni aritmetiche.
si.. ci ero già arrivato... alla fine, se ci pensi, il fatto che hai dimostrato è un caso particolare del teorema di Euler-Fermat..
beh.. se la trovi... batti un colpo
sinceramente è la prima volta che mi trovo davanti a stime asintotiche e non so neanche da che parte cominciare!!
ciao, ubermensch
beh.. se la trovi... batti un colpo
sinceramente è la prima volta che mi trovo davanti a stime asintotiche e non so neanche da che parte cominciare!!
ciao, ubermensch
fra l'altro (scusa l'ignoranza), ma mi spiegheresti perchè trovare una F(n) tale che.... equivale a dimostrare che lg2(n) e Lp(n) sono asintotiche?
grazie
ciao, ubermensch
grazie
ciao, ubermensch
"ubermensch":
fra l'altro (scusa l'ignoranza), ma mi spiegheresti perchè trovare una F(n) tale che.... equivale a dimostrare che lg2(n) e Lp(n) sono asintotiche?
grazie
ciao, ubermensch
Non ho detto che equivale a dire che sono asintotiche, intendevo dire che sarebbe l'ideale poichè l'errore F(n)-Lp(n) sarebbe sempre < C.
Ciao
P.S. ho fatto qualche progresso appena riesco lo posto.
Definisco la funzione $L_a(n)$ esattamente come la tua funzione $L_p(n)$ solo senza la restrizione
che $p$ sia un numero primo (deve però essere dispari).
Poi definisco anche $l_a(n)$ come la funzione uguale a 1 se $(a^n-1)/(2n)$ è intero, 0 altrimenti.
è ovvio che si ha:
$L_a(n)=sum_(k=2)^n l_a(k)$
Adesso non è difficile dimostrare che
1) se $l_a(k)=1$ allora $l_a(k^n)=1 forall n$. Per dimostrarlo si può procedere come avevo fatto per le potenze di 2
2) se $k$ e $h$ sono primi tra loro e $l_a(k)=1$ e $l_a(h)=1$ allora $l_a(kh)=1$. Infatti si ha che
$a^(kh)-1=(a^k-1)(a^(k(h-1))+a^(k(h-2))+...+1)$
$a^(kh)-1=(a^h-1)(a^(h(k-1))+a^(h(k-2))+...+1)$
e il risultato segue dal fatto che $2k$ divide $a^k-1$ e $2h$ divide $a^h-1$ e $k$ e $h$ sono primi tra loro.
Se adesso definisco l'insieme $T(a)$ come l'insieme dei "generatori" cioè degli interi $b$ tali che $2b$ divide $a^b-1$
e che non esistano due interi $e$ e $f$ tali che $ef=b$ e che $(a^e-1)/(2e)$ $(a^f-1)/(2f)$ siano interi.
Dalla 1 e la 2 segue che tutti gli interi $b$ tali che $l_a(b)=1$ sono prodotti di soli "generatori". E quindi si ha
3)$L_a(n)=|U_a(n)|$
dove $U_a(n)={m
Adesso sorge spontaneo cercare di dimostrare se $T(a)$ ha o non ha un numero finito di elementi, sarebbe un analogo della dimostrazione
dell'infinità dei numeri primi.
Tra l'altro se $T(a)$ ha finiti elementi allora si può ottenere una formula esatta per $L_a(n)$
P.S. spero di non averti detto cose che sapevi già, ma soprattutto di non aver detto castronerie.
che $p$ sia un numero primo (deve però essere dispari).
Poi definisco anche $l_a(n)$ come la funzione uguale a 1 se $(a^n-1)/(2n)$ è intero, 0 altrimenti.
è ovvio che si ha:
$L_a(n)=sum_(k=2)^n l_a(k)$
Adesso non è difficile dimostrare che
1) se $l_a(k)=1$ allora $l_a(k^n)=1 forall n$. Per dimostrarlo si può procedere come avevo fatto per le potenze di 2
2) se $k$ e $h$ sono primi tra loro e $l_a(k)=1$ e $l_a(h)=1$ allora $l_a(kh)=1$. Infatti si ha che
$a^(kh)-1=(a^k-1)(a^(k(h-1))+a^(k(h-2))+...+1)$
$a^(kh)-1=(a^h-1)(a^(h(k-1))+a^(h(k-2))+...+1)$
e il risultato segue dal fatto che $2k$ divide $a^k-1$ e $2h$ divide $a^h-1$ e $k$ e $h$ sono primi tra loro.
Se adesso definisco l'insieme $T(a)$ come l'insieme dei "generatori" cioè degli interi $b$ tali che $2b$ divide $a^b-1$
e che non esistano due interi $e$ e $f$ tali che $ef=b$ e che $(a^e-1)/(2e)$ $(a^f-1)/(2f)$ siano interi.
Dalla 1 e la 2 segue che tutti gli interi $b$ tali che $l_a(b)=1$ sono prodotti di soli "generatori". E quindi si ha
3)$L_a(n)=|U_a(n)|$
dove $U_a(n)={m
Adesso sorge spontaneo cercare di dimostrare se $T(a)$ ha o non ha un numero finito di elementi, sarebbe un analogo della dimostrazione
dell'infinità dei numeri primi.
Tra l'altro se $T(a)$ ha finiti elementi allora si può ottenere una formula esatta per $L_a(n)$
P.S. spero di non averti detto cose che sapevi già, ma soprattutto di non aver detto castronerie.
ehm.. temo che devo perderci un pò di tempo per capire cos'hai scritto!!!...
comunque ti faccio i complimenti!! sei bravissimo!! ma hai solo 23 anni??
p.s. io per ora sto facendo solo verifiche al pc;
per la cronaca, fino a p=151 e n=2^25 sembra valere la seguente stima fantastica
lg2(n) + 3 >= Lp(n) >= lg2(n)
ciao
comunque ti faccio i complimenti!! sei bravissimo!! ma hai solo 23 anni??
p.s. io per ora sto facendo solo verifiche al pc;
per la cronaca, fino a p=151 e n=2^25 sembra valere la seguente stima fantastica
lg2(n) + 3 >= Lp(n) >= lg2(n)
ciao
"ubermensch":
ehm.. temo che devo perderci un pò di tempo per capire cos'hai scritto!!!...
comunque ti faccio i complimenti!! sei bravissimo!! ma hai solo 23 anni??
p.s. io per ora sto facendo solo verifiche al pc;
per la cronaca, fino a p=151 e n=2^25 sembra valere la seguente stima fantastica
lg2(n) + 3 >= Lp(n) >= lg2(n)
ciao
Grazie,grazie mille per i tuoi complimenti.
23 non sono i mie anni (altrimenti dovrei cambiare login tutte le volte che è il mio compleanno!), 23 era il numero primo preferito da John Nash.
Io veramente avrei quattordici anni... quindici il nove gennaio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo