Congetture sui numeri primi

[Bersan]

Ciao a tutti. Mi chiamo Bersan e sono un appassionato di logica, matematica e in particolare di numeri. Ho sviluppato una particolare funzione che prendendo come argomento un numero intero positivo n determina se 2*n+1 è primo. Siccome i miei amici etichettano benevolmente come "bersanate" le mie riflessioni ho deciso di chiamare la funzione Bersana. Chiedo scusa in anticipo per la formattazione del messaggio ma essendo non vedente è un compito difficile per me.

____________________________________________________________


• Bersana(n) è sempre compreso da p + 1 a n dove p è la massima potenza di 2 inferiore o uguale a n
• Se Bersana(n) = n allora ( 2 * n + 1) è numero primo
• Se Bersana(n) non è un divisore di n allora ( 2 * n + 1) non è numero primo

______________________________________________________________________________
Funzione Bersana(N)
______________________________________________________________________________


Bersana(n) agisce sull'insieme dei numeri interi positivi da 1 a n.
Modifica la posizione degli elementi dell'insieme, tramite la procedura che spiego in seguito, e restituisce il numero di volte in cui bisogna applicare tale procedura affinché gli elementi tornino alla loro disposizione iniziale


Se n è pari

posiziona nella prima metà dell'insieme in ordine decrescente gli elementi che prima occupavano posizioni pari e nella seconda metà in ordine crescente quelli che occupavano posizioni dispari.

{n, n-2, n-4, ..., 2, 1, 3, 5, ..., n-1}


Dunque per ogni vp (vecchia posizione) la np (nuova posizione) sarà:

Se vp è pari: np = n / 2 + 1 - vp / 2
Altrimenti: np = n / 2 + (vp + 1) / 2

ad esempio per n = 10

(posizione iniziale) = { 1 2 3 4 5 6 7 8 9 10}

bersana:

1. { 10 8 6 4 2 1 3 5 7 9 }
2. { 9 5 1 4 8 10 6 2 3 7 }
3. { 7 2 10 4 5 9 1 8 6 3 }
4. { 3 8 9 4 2 7 10 5 1 6 }
5. { 6 5 7 4 8 3 9 2 10 1 }
6. { 1 2 3 4 5 6 7 8 9 10} = (posizione iniziale)

bersana(10) = 6



Se n è dispari


Posiziona nell'insieme in ordine decrescente gli elementi che prima occupavano posizioni dispari e in seguito in ordine crescente quelli che occupavano posizioni pari.

{n, n-2, n-4, ..., 1, 2, 4, 6, ..., n-1}


Dunque per ogni vp (vecchia posizione) la np (nuova posizione) sarà:

Se vp è pari: np = (n + 1) / 2 + vp / 2
Altrimenti: np = (n + 1) / 2 - (vp - 1) / 2

ad esempio per n = 9

(posizione iniziale) = { 1 2 3 4 5 6 7 8 9 }

Bersana:

1. { 9 7 5 3 1 2 4 6 8 }
2. { 8 4 1 5 9 7 3 2 6 }
3. { 6 3 9 1 8 4 5 7 2 }
4. { 2 5 8 9 6 3 1 4 7 }
5. { 7 1 6 8 2 5 9 3 4 }
6. { 4 9 2 6 7 1 8 5 3 }
7. { 3 8 7 2 4 9 6 1 5 }
8. { 5 6 4 7 3 8 2 9 1 }
9. { 1 2 3 4 5 6 7 8 9 } = (posizione iniziale)

bersana(9) = 9


Che ne pensate?

[Gauss91]

Con qualche esempio che ho provato (utilizzando numeri piccoli) sembrerebbe che funzioni.
Potresti allegare la dimostrazione o vuoi che la troviamo noi?

[Nonno Bassotto]

Dal titolo del post, mi sa che non abbia le dimostrazioni...

Anch'io ho provato con numeri piccoli (fino a 16) e sembra funzionare, tranne il claim che Bersana(n) è sempre almeno la potenza di 2 precedente a n. Infatti Bersana(16) = 5 (a meno di errori miei).

Qualcuno prova a scrivere un programmino per testare la cosa fino a 10000? Io oggi sono un po' incasinato per farlo.

[Bersan]

Con qualche esempio che ho provato (utilizzando numeri piccoli) sembrerebbe che funzioni.
Potresti allegare la dimostrazione o vuoi che la troviamo noi? :)

Grazie per avermi risposto. Purtroppo io non ho la dimostrazione delle mie congetture che sono frutto della mia osservazione.
Se qualcuno volesse dimostrare o confutare una o più delle seguenti affermazioni sarei molto felice.

• Se Bersana(n) = n allora 2*n+1 è primo

• Se Bersana(n) non è un divisore di n allora 2*n+1 non è primo

• Se n non si Bersana regolarmente (spiego in seguito cosa intendo per regolarità della funzione Bersana) allora 2*n+1 non è primo

• il valore di Bersana(n) non supera n

• Quando il primo elemento dell'insieme n durante la funzione Bersana(n) torna al suo posto tutti gli altri elementi sono a loro posto.

• Il valore minimo di Bersana(n) non può essere inferiore a p dove p è la minima potenza di 2 maggiore di n

• Bersana(2^p) = P + 1 (valore minimo di Bersana)

• Bersana(2^p × [2^(p+1) ± 1]) = 3(p+1)

• Bersana(2^p × (2^p ± 1)) = 2(2p +1)
• Bersana(2^p × [2^(p-1) ± 1]) = p × (2^p ± 1)


____________________________________________________________________

Regolarità della funzione Bersana(n)
____________________________________________________________________


Si può dire che n si Bersana regolarmente se e solo se tutti gli elementi del insieme impiegano lo stesso numero di modifiche della propria posizione per ritornare a loro posto.

Ad esempio per n = 10

Bersana:
1. { 10 8 6 4 2 1 3 5 7 9 }
2. { 9 5 1 4 8 10 6 2 3 7 }
3. { 7 2 10 4 5 9 1 8 6 3 }
4. { 3 8 9 4 2 7 10 5 1 6 }
5. { 6 5 7 4 8 3 9 2 10 1 }
6. { 1 2 3 4 5 6 7 8 9 10} = (posizione iniziale)

Basterebbe il fatto che l'elemento nella posizione 4 rimane sempre al suo posto per dire che 10 non si Bersana regolarmente



Per n = 8

Bersana:
1. { 8 6 4 2 1 3 5 7 }
2. { 7 3 2 6 8 4 1 5 }
3. { 5 4 6 3 7 2 8 1 }
4. { 1 2 3 4 5 6 7 8 }
Bersana(n) = 4
Tutti gli elementi fanno un percorso di 4 passaggi per tornare a loro posto.
Dunque si può dire che 8 si Bersana regolarmente

[Bersan]

Dal titolo del post, mi sa che non abbia le dimostrazioni...

Anch'io ho provato con numeri piccoli (fino a 16) e sembra funzionare, tranne il claim che Bersana(n) è sempre almeno la potenza di 2 precedente a n. Infatti Bersana(16) = 5 (a meno di errori miei).

No, non ti sbagli. Mi sono sbagliato io a scrivere (potenza minore di n) invece di scrivere (potenza non maggiore di n) Già corretto...

Comunque, le affermazioni che ho scritto nel post precedente sono testate per n fino al 2^16.

EDIT: chiuso un tag. ma_go

[ma_go]

ok, quello che intendi dire davvero e' "l'esponente della massima potenza di due bla bla"

giusto per curiosita', quanti sono i numeri (tra 1 e 2^16) tali che Bersana(n)=n?

[Bersan]

Per n da 1 a 2^16 (tutti i primi fino al valore massimo di 2*n+1 sono 12250)


___________________________________________________________

1. La condizione (Bersana(n) = n)
si verifica 6899 volte e in tutti i casi 2*n+1 è primo

2. La condizione (n divisibile per Bersana(n))
Si verifica 12300 volte e 2*n+1 e primo in 12250 casi (tutti i primi del intervallo). Rimane il fatto che in 50 casi 2*n+1 non è primo.

Si può dire che se n non è divisibile per Bersana(n) allora 2*n+1 non è primo


3 se alla condizione (n divisibile per Bersana(n)) si aggiunge che (n si Bersana regolarmente)
I casi di 2*n+1 non primi si riducono a 9 è il resto sono tutti i primi del intervallo

Si può dire che se n non si Bersana regolarmente allora 2*n+1 non è primo

___________________________________________________________

[fph]

Secondo me salta fuori che è collegata a qualcosa di classico.
Sono troppo pigro per scriverlo io, ma immagino che tu abbia un programma per calcolarla, quindi: potresti mica scriverci i valori di B(n), diciamo per n da 1 a 50? Magari mettendoci di fianco anche B(n) e $ B(n)\pm 1 $ scritti in binario, che ha tutta l'aria di essere utile. Se però questo ti genera guai non ti preoccupare, dammi solo i numeri e li converto io in binario.

[fph]

A proposito, sarà mica questa?

[trugruo]

fph l'ha trovata,è proprio quella xd

[fph]

Nah, il lavoro non è finito. Se si usa l'altra definizione, le relazioni con i primi a questo punto dovrebbero essere facili esercizi sugli ordini moltiplicativi; però resta da provare che le due definizioni coincidono (una lista di numeri non basta...).

[FrancescoVeneziano]

Io ho dimostrato che se la permutazione definita da Bersan è un n-ciclo, allora 2n+1 deve essere primo, che mi sembra un buon passo verso la tesi.

Tra l'altro, se invece di considerare quella permutazione lì si considera la sua coniugata rispetto al "flip" $ \tau(x)=n+1-x $, risulta abbastanza chiaro che l'ordine moltiplicativo di 2 modulo 2n+1 è la quantità da tener d'occhio.
Provo più tardi a scrivere tutto per bene.

[Bersan]

Forse a qualcuno può essere utile la tabella seguente.
Per n fino a 2^17 Bersana(n) è regolare in 23012 casi
2*n+1 è primo in 22999 di questi (tutti i primi fino a 2^18 + 1).

Questi sono i 13 casi in cui 2*n+1 non è primo

Codice: Seleziona tutto

n		|	Bersana(n)	|		2*n+1 (non primo)
___________________________________________________________________________________
1023		|	11		|		2047
1638		|	14		|		3277
2016		|	18		|		4033
4160		|	26		|		8321
32640		|	24		|		65281
40290		|	30		|		80581
42744		|	26		|		85489
44178		|	74		|		88357
52326		|	38		|		104653
65280		|	34		|		130561
110364		|	51		|		220729
126620		|	26		|		253241
128499		|	29		|		256999

Cosa hanno in comune questi numeri?

[Bersan]

Per n fino a 2^20 n si Bersana regolarmente in 155650 casi;
in 155610 di questi 2*n+1 è primo e nei rimanenti 40 è un semiprimo.

[Haile]

Cosa hanno in comune questi numeri?

Sono pseudoprimi. Guarda qui e qui.

Pare quindi che il tuo sia un test di pseudoprimalità(?)