Nuovo criterio di primalità?
Ciao ragazzi, ci terrei a farvi vedere una cosa, di cui mi sono accorto un po' di tempo fa e che mi ha tenuto occupato per molto nel tentativo di trovare una dimostrazione. Dopo essermi scervellato abbastanza, senza praticamente nessun risultato concreto a parte numerosi calcoli che mi danno ragione, getto la spugna, e chiedo a voi che di sicuro ne sapete più di me e potete aprirmi gli occhi, nel bene e nel male.
Ricordo la definizione della funzione floor[a/b] $= ⌊a/b⌋$ come il più piccolo intero minore o uguale al rapporto a/b.
Ad esempio $ ⌊10/3⌋=3 $ , $ ⌊1/2⌋=0 $ , $ ⌊7/4⌋ = 1 $ , $ ⌊6/2⌋=3 $
Mi sono trovato ad enunciare la seguente congettura, dopo molti calcoli a favore, e non essendo in grado di trovare una dimostrazione soddisfacente:
" Se, preso un qualsiasi numero intero $n>6$, la somma che segue si annulla, allora $n$ è un numero primo."
$ sum_(k=2)^[(n-1)/2] (⌊n/k⌋-⌊(n-1)/k⌋)$
"Se la serie non si annulla, $n$ non è primo. "
Provare che tutto ciò è vero equivale ovviamente a dimostrare che, se $n$ è un numero primo, e preso un parametro naturale $k in [2, (n-1)/2] $ , $ AA k $ si ha che $ ⌊n/k⌋=⌊(n-1)/k⌋ $
Eseguendo i calcoli fino ad n=100, i conti tornano, nel senso che se n è primo la somma viene nulla, se non è primo la somma da un risultato diverso da zero.
Qua sotto, giusto per vedere se funziona a caso o no, vi metto il calcolo con due numeri:
$n=2939$ che sappiamo essere primo:
$sum_(k=2)^[(2939-1)/2] [⌊2939/k⌋-⌊(2939-1)/k⌋]= sum_(k=2)^[1469] [⌊2939/k⌋-⌊(2938)/k⌋]= 0 $
Ed effettivamente la somma si annulla!
$n=3423$ che sappiamo non essere primo:
$sum_(k=2)^[(3423-1)/2] [⌊3423/k⌋-⌊(3423-1)/k⌋]= sum_(k=2)^[1711] [⌊3423/k⌋-⌊(3422)/k⌋]= 6$
Ed effettivamente la somma non si annulla.
Ovviamente questi due casi non sono niente di che, però, per ora, per ogni calcolo effettuato il risultato mi da un giusto riscontro della primalità di un numero, nel caso questa ipotesi sia vera, sarebbe una condizione sufficiente di primalità, magari non troppo comoda come modalità di calcolo, però pur sempre un criterio di primalità!
A voi la parola! Vi saluto
Andrea Lo Sardo
Ricordo la definizione della funzione floor[a/b] $= ⌊a/b⌋$ come il più piccolo intero minore o uguale al rapporto a/b.
Ad esempio $ ⌊10/3⌋=3 $ , $ ⌊1/2⌋=0 $ , $ ⌊7/4⌋ = 1 $ , $ ⌊6/2⌋=3 $
Mi sono trovato ad enunciare la seguente congettura, dopo molti calcoli a favore, e non essendo in grado di trovare una dimostrazione soddisfacente:
" Se, preso un qualsiasi numero intero $n>6$, la somma che segue si annulla, allora $n$ è un numero primo."
$ sum_(k=2)^[(n-1)/2] (⌊n/k⌋-⌊(n-1)/k⌋)$
"Se la serie non si annulla, $n$ non è primo. "
Provare che tutto ciò è vero equivale ovviamente a dimostrare che, se $n$ è un numero primo, e preso un parametro naturale $k in [2, (n-1)/2] $ , $ AA k $ si ha che $ ⌊n/k⌋=⌊(n-1)/k⌋ $
Eseguendo i calcoli fino ad n=100, i conti tornano, nel senso che se n è primo la somma viene nulla, se non è primo la somma da un risultato diverso da zero.
Qua sotto, giusto per vedere se funziona a caso o no, vi metto il calcolo con due numeri:
$n=2939$ che sappiamo essere primo:
$sum_(k=2)^[(2939-1)/2] [⌊2939/k⌋-⌊(2939-1)/k⌋]= sum_(k=2)^[1469] [⌊2939/k⌋-⌊(2938)/k⌋]= 0 $
Ed effettivamente la somma si annulla!
$n=3423$ che sappiamo non essere primo:
$sum_(k=2)^[(3423-1)/2] [⌊3423/k⌋-⌊(3423-1)/k⌋]= sum_(k=2)^[1711] [⌊3423/k⌋-⌊(3422)/k⌋]= 6$
Ed effettivamente la somma non si annulla.
Ovviamente questi due casi non sono niente di che, però, per ora, per ogni calcolo effettuato il risultato mi da un giusto riscontro della primalità di un numero, nel caso questa ipotesi sia vera, sarebbe una condizione sufficiente di primalità, magari non troppo comoda come modalità di calcolo, però pur sempre un criterio di primalità!
A voi la parola! Vi saluto
Andrea Lo Sardo
Risposte
Ciao, dunque il criterio mi sembra funzionare. Propongo una spiegazione (la scrivo di getto, non è formale quindi non la chiamo ovviamente dimostrazione) intuitiva.
Denoto per semplicità il floor di a/b come $\lfloor a/b \rfloor$.
Dunque, quando dici
questo è vero perché chiaramente si ha sempre che
$ \lfloor n/k \rfloor >= \lfloor (n-1)/k \rfloor$ per ogni $n$ e $k
Fissiamo quindi un $n$, un $k in [2, (n-1)/2]$, e vediamo che succede ai termini $ \lfloor n/k \rfloor$ e $\lfloor (n-1)/k \rfloor$ nel caso $n$ primo e $n$ non primo.
Se $n$ è non primo, visto che il $k$ varia tra $2$ e $(n-1)/2$, sicuramente essendo $n$ non primo esiste un $k$ tale che $k | n$ ovvero $k$ è un divisore di $n$.
Chiamiamo questo divisore $\bar k$.
Allora: $n/\bar k$ è un numero intero (chiamiamolo $M$), quindi $\lfloor n / \bar k \rfloor = n / \bar k = M$.
Di conseguenza, $\lfloor (n-1)/\bar k \rfloor = M - 1$.
Quindi l'addendo della sommatoria corrispondente a $\bar k$ è non nullo, quindi tutta la somma è non nulla.
Viceversa, se invece $n$ è primo, non esiste nessun $k$ che divide $n$ quindi la quantità $n/\bar k$ è sempre non intera.
Allora lo possiamo scrivere come $n = k*d + r$, con $d$ intero e $r in [1, k -1]$ (chiaramente $r != 0$ per quanto appena detto).
Quindi, sottraendo -1, abbiamo che $n - 1 = k * d + (r-1)$ quindi il resto della divisione (chiamiamolo $hat r = r -1$ di $n-1$ diviso $k$ varia in $\hat r in [0,k-2]$ (quindi è possibile che eventualmente $n-1$ sia divisibile per $k$ ovviamente).
Non potendosi mai verificare quindi che $\hat r < 0 $ o che $hat r >=k$, la quantità intera $d$ è rimane la stessa sia quando divido $n$ per $k$ sia quando divido $n-1$ per $k$.
Quindi, $ \lfloor n/k \rfloor = \lfloor (n-1)/k \rfloor = d$, e di conseguenza tutti i termini nella sommatoria si annullano.
Sono confidente che questo criterio funziona.
Tuttavia, ti faccio notare una cosa. Il criterio più semplice per testare la primalità di un numero $n$ è controllare se la divisione $n/k$ per ogni $k in [2, n/2]$ dà resto zero oppure no (ovviamente dopo $n/2$ non esistono mai eventuali divisori (in realtà è sufficiente arrivare a $sqrt(n)$...)). Computazionalmente, stai facendo circa $n/2$ divisioni.
Con il tuo criterio, nella somma ci sono circa $n/2$ termini (approssimo tanto per $n$ grande è irrilevante la stima), e ogni termine contiene due divisioni da calcolare. Computazionalmente, stai facendo $n/2 * 2 = n$ divisioni.
Sempre computazionalmente parlando quindi, il tuo criterio è meno performante perfino del test di primalità più semplice, quindi per grandi numeri è assolutamente impossibile da sfruttare anche con i computer più potenti
Spero di essere stato chiaro e se ho scritto stupidaggini correggetemi!
Ciao
Denoto per semplicità il floor di a/b come $\lfloor a/b \rfloor$.
Dunque, quando dici
Provare che tutto ciò è vero equivale ovviamente a dimostrare che, se $n$ è un numero primo, e preso un parametro naturale $k in [2, (n-1)/2] $ , $ AA k $ si ha che $ \lfloor n/k \rfloor = \lfloor (n-1)/k \rfloor$
questo è vero perché chiaramente si ha sempre che
$ \lfloor n/k \rfloor >= \lfloor (n-1)/k \rfloor$ per ogni $n$ e $k
Fissiamo quindi un $n$, un $k in [2, (n-1)/2]$, e vediamo che succede ai termini $ \lfloor n/k \rfloor$ e $\lfloor (n-1)/k \rfloor$ nel caso $n$ primo e $n$ non primo.
Se $n$ è non primo, visto che il $k$ varia tra $2$ e $(n-1)/2$, sicuramente essendo $n$ non primo esiste un $k$ tale che $k | n$ ovvero $k$ è un divisore di $n$.
Chiamiamo questo divisore $\bar k$.
Allora: $n/\bar k$ è un numero intero (chiamiamolo $M$), quindi $\lfloor n / \bar k \rfloor = n / \bar k = M$.
Di conseguenza, $\lfloor (n-1)/\bar k \rfloor = M - 1$.
Quindi l'addendo della sommatoria corrispondente a $\bar k$ è non nullo, quindi tutta la somma è non nulla.
Viceversa, se invece $n$ è primo, non esiste nessun $k$ che divide $n$ quindi la quantità $n/\bar k$ è sempre non intera.
Allora lo possiamo scrivere come $n = k*d + r$, con $d$ intero e $r in [1, k -1]$ (chiaramente $r != 0$ per quanto appena detto).
Quindi, sottraendo -1, abbiamo che $n - 1 = k * d + (r-1)$ quindi il resto della divisione (chiamiamolo $hat r = r -1$ di $n-1$ diviso $k$ varia in $\hat r in [0,k-2]$ (quindi è possibile che eventualmente $n-1$ sia divisibile per $k$ ovviamente).
Non potendosi mai verificare quindi che $\hat r < 0 $ o che $hat r >=k$, la quantità intera $d$ è rimane la stessa sia quando divido $n$ per $k$ sia quando divido $n-1$ per $k$.
Quindi, $ \lfloor n/k \rfloor = \lfloor (n-1)/k \rfloor = d$, e di conseguenza tutti i termini nella sommatoria si annullano.
Sono confidente che questo criterio funziona.
Tuttavia, ti faccio notare una cosa. Il criterio più semplice per testare la primalità di un numero $n$ è controllare se la divisione $n/k$ per ogni $k in [2, n/2]$ dà resto zero oppure no (ovviamente dopo $n/2$ non esistono mai eventuali divisori (in realtà è sufficiente arrivare a $sqrt(n)$...)). Computazionalmente, stai facendo circa $n/2$ divisioni.
Con il tuo criterio, nella somma ci sono circa $n/2$ termini (approssimo tanto per $n$ grande è irrilevante la stima), e ogni termine contiene due divisioni da calcolare. Computazionalmente, stai facendo $n/2 * 2 = n$ divisioni.
Sempre computazionalmente parlando quindi, il tuo criterio è meno performante perfino del test di primalità più semplice, quindi per grandi numeri è assolutamente impossibile da sfruttare anche con i computer più potenti
Spero di essere stato chiaro e se ho scritto stupidaggini correggetemi!
Ciao
Sono molto d'accordo con quello che ha detto gygabyte017, nel senso che mi sembra che tu abbia riscritto in termini piu' complicati la proprietà di non essere divisibile per nessun numero diverso da se stesso. Infatti la cosa può essere vista in questo modo:
$n in NN$, quindi $AA k
Riguardo ciò non vorrei sbagliarmi ma credo che la complessità computazionale sia la stessa, nel senso che sono considerati trascurabili eventuali fattori moltiplicativi.
$n in NN$, quindi $AA k
"gygabyte017":
Sempre computazionalmente parlando quindi, il tuo criterio è meno performante perfino del test di primalità più semplice, quindi per grandi numeri è assolutamente impossibile da sfruttare anche con i computer più potenti
Riguardo ciò non vorrei sbagliarmi ma credo che la complessità computazionale sia la stessa, nel senso che sono considerati trascurabili eventuali fattori moltiplicativi.
Ahahahaha grazie mille, ho capito, e mi sento abbastanza stupido. Si un po' me lo aspettavo che sarebbe stata una cavolata, però è sempre meglio essere positivi e affidarsi a chi ne sa più di te! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo