prime-chasing
prime-chasing
trovare tutti i primi della forma $n^n+1$ che sono $<10^{19}$.
Re: prime-chasing
Oltre a provare (a manina) i pochi casi, c'è un modo più elegante?
Testo nascosto:
Re: prime-chasing
Io ho tolto solo i multipli di 3 in quanto $n^{3k}$ scomponibile in somma di cubi, ma nulla di più
-
- Messaggi: 217
- Iscritto il: 20 giu 2015, 20:58
Re: prime-chasing
Teoricamente si possono togliere tutti i multipli di numeri dispari. Vanno quindi controllati solo le potenze di 2
Un bresciano esportato nel cremonese
-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
Re: prime-chasing
Forse ho frainteso il testo del quesito? Sto considerando soloRiccardoKelso ha scritto:Io ho tolto solo i multipli di 3 in quanto $n^{3k}$ scomponibile in somma di cubi, ma nulla di più
$ 1^{1} + 1, 2^{2} + 1, 3^{3} + 1,..., 14^{14} + 1, 15^{15} + 1 $
e da questi ho tolto tutti gli $ n > 1 $ dispari
-
- Messaggi: 43
- Iscritto il: 31 dic 2011, 13:00
- Località: Città degli scacchi (VI)
Re: prime-chasing
Penso che RiccardoKelso intendesse scrivere che $n^{3}+1$ divide $n^{3k}+1$.
Comunque mettendo insieme le idee che avete scritto, con un poco di sforzo in più, si arriva a dover controllare solamente un caso non banale...
Comunque mettendo insieme le idee che avete scritto, con un poco di sforzo in più, si arriva a dover controllare solamente un caso non banale...
"La vita è come uno specchio: ti sorride se la guardi sorridendo".
Re: prime-chasing
effettivamente $n$ deve essere una potenza di $2$ infatti se non lo fosse allora $n=t^m$ dove $t=(2^k\cdot m)^{2^k}$ e $m$ è un numero dispari.
Essendo dispari $t^m+1=(t+1)(t^{m-1}-t^{m-2}\cdots -t+1)$.
Ora vi resta da cercare il primi nelle potenze di $2$ e ''basta''
Essendo dispari $t^m+1=(t+1)(t^{m-1}-t^{m-2}\cdots -t+1)$.
Ora vi resta da cercare il primi nelle potenze di $2$ e ''basta''
Re: prime-chasing
per quanto detto fino ad adesso $n$ è uguale a $1$ oppure deve essere pari, più precisamente una potenza di $2$.
quindi $n=2^{2^t\cdot (2k+1)}$ e
$n^n+1=2^{2^t\cdot (2k+1)\cdot 2^{2^t\cdot (2k+1)}}+1=2^{2^{t+2^t(2k+1)}\cdot (2k+1)}+1=(2^{2^{t+2^t(2k+1)}})^{(2k+1)}+1$
ma questo è divisibile per $2^{2^{t+2^t(2k+1)}}+1$ quindi non è sicuramente primo per $k\ge 1$.
Allora $n$ è della forma $n=2^{2^t}$ e sostituendo $t=0,1,2$ a $(2^{2^t})^{2^{2^t}}+1$ si ottiene rispettivamente $5,257,16^{16}+1$.
$5$ e $257$ sono due primi e per fortuna $16^{16}+1>16^{16}=4^{32}>10\cdot 4^{30}=10\cdot (4^5)^{6}>10\cdot (10^3)^{6}=10^{19}$ e quindi non ci interessa.
in definitiva i primi sono $2,5,257$.
quindi $n=2^{2^t\cdot (2k+1)}$ e
$n^n+1=2^{2^t\cdot (2k+1)\cdot 2^{2^t\cdot (2k+1)}}+1=2^{2^{t+2^t(2k+1)}\cdot (2k+1)}+1=(2^{2^{t+2^t(2k+1)}})^{(2k+1)}+1$
ma questo è divisibile per $2^{2^{t+2^t(2k+1)}}+1$ quindi non è sicuramente primo per $k\ge 1$.
Allora $n$ è della forma $n=2^{2^t}$ e sostituendo $t=0,1,2$ a $(2^{2^t})^{2^{2^t}}+1$ si ottiene rispettivamente $5,257,16^{16}+1$.
$5$ e $257$ sono due primi e per fortuna $16^{16}+1>16^{16}=4^{32}>10\cdot 4^{30}=10\cdot (4^5)^{6}>10\cdot (10^3)^{6}=10^{19}$ e quindi non ci interessa.
in definitiva i primi sono $2,5,257$.