Newsgroup: it.hobby.enigmi
Titolo: Catene di coppie prime

Chiamo "catena di coppie prime" una permutazione dei primi n interi, tale 
che la somma di tutte le coppie di numeri adiacenti, sia un primo.
es:
n=2     1-2
n=3    1-2-3
n=4   1-4-3-2
n=5  1-4-3-2-5
Qual e' il piu' piccolo valore di n per il quale non e' possibile produrre 
una tale catena ?
Esiste un valore massimo di n dopo il quale non e' piu' possibile ottenere 
soluzioni ?
dario

 soluzioni ?
spoiler
.
.
.
.
.
.
.
.
Penso che non ci sia un limite superiore.
Ogni catena di lunghezza N si puo' estendere a N+1, nel modo seguente 
(indico con [x] l'elemento in posizione x della catena):
1) aggiungere N+1 in posizione [N+1]
2) a partire da [N] e andando all'indietro di 2 in 2, cercare [x] tale 
che [x-1]+[N] sia primo e che [x]+[N+1] sia primo (ovviamente x puo' 
anche essere N stesso).
3) invertire la catena [x]..[N].
La catena [1]...[N+1] cosi' creata e' di nuovo una catena di coppie 
prime.
Qusto algoritmo puo' fallire solo se non si riesce a trovare l'elemento 
[x] al punto 2). Ma direi che al crescere di N la probabilita' di 
trovare [x] *aumenta*, quindi non c'e' fine al procedimento.
Nicola Salmoria

 Penso che non ci sia un limite superiore.
Ho avuto lo stesso sospetto.
ciao.

 Ho avuto lo stesso sospetto.
Col mio stesso procedimento o con altro?
Nicola Salmoria

 Col mio stesso procedimento o con altro?
Con lo stesso metodo del rovesciamento sono arrivato facilmente oltre 50 
termini, e sembrerebbe effettivamente di poter procedere indisturbati, ma 
poi c'e' un'altra osservazione che avvalora questa idea.
Prendiamo una coppia di primi gemelli x e x+2 es: 17 e 19
Allora si puo' formare una catena dove ogni coppia somma alternativamente a 
x e x+2 in questo modo
1, x-1, 3, x-3, 5, x-5,.....x-4, 4, x-2, 2.
Nel nostro esempio:
1,16,3,14,5,12,7,10,9,8,11,6,13,4,15,2,17. Dimostrando che una catena lunga 
x esiste.
Togliendo l'ultimo termine a destra ho una catena lunga x-1.
Spostando l'1 a destra e togliendo x-1 (nel nostro caso il 16) ho una 
catena di x-2 termini. Posso procedere spostando a destra il 3 e togliendo 
l'x-3 (14) ecc... sono sicuro che i termini piu' bassi, spostati a destra 
1,2,3,4,5... possono essere messi in una sequenza legale, perche' gia' 
esplorata.
A questo punto, sicuro di essere arrivato fino a 17, considero la coppia 
gemella 41 e 43 poi 59 e 61 poi 107 e 109, 197 e 199... ecc. questo mi 
spinge abbastanza avanti, certo non sono sicuro di trovare sempre una 
coppia di primi gemelli nell'intervallo desiderato. Come sappiamo non e' 
ancora stato dimostrato che queste coppie di primi siano infinite.
ciao.


Credo che non esista questo numero. Controllando le sequenze generate
per i casi da 2 a 15 si vede che le soluzioni aumentano rapidamente,
quindi é molto difficile che all'improvviso precipitino a zero.
D'altronde all'aumentare della dimensione dei numeri aumentano anche i
numeri primi...
Le soluzioni possibili sono le seguenti: (le soluzioni simmetriche non
sono conteggiate):
 
Sequenze di  2 interi: 1
Sequenze di  3 interi: 1
Sequenze di  4 interi: 4
Sequenze di  5 interi: 2
Sequenze di  6 interi: 8
Sequenze di  7 interi: 12
Sequenze di  8 interi: 30
Sequenze di  9 interi: 70
Sequenze di 10 interi: 664
Sequenze di 11 interi: 1072
Sequenze di 12 interi: 8768
Sequenze di 13 interi: 11648
Sequenze di 14 interi: 37108
Sequenze di 15 interi: 95772
La situazione non cambia di molto considerando anche lo zero; il
numero delle soluzioni aumenta per n > 3. 
Non ho molto tempo da dedicare al NG e in genere lo leggo solo la
domenica (e non sempre); spero che a qualcuno interessi il mio
messaggio anche se in ritardo.
Ciao, Damiano