Il problema e' il seguente:

Il numero n piu' piccolo per cui e' possibile trovare questa sequenza circolare e' 32:


Questa sequenza e' stata trovata per primo da Federico Ramondino (A112663) e in seguito Raffaele Rossi ha fornito una dimostrazione sintetica che la sequenza circolare non si puo' ottenere per n<32 (anche Proietti ci era andato vicino...). Vediamo il suo ragionamento!

Una condizione necessaria affinche' si possa costruire la sequenza circolare e' che ciascun numero da 1 a n deve essere "collegato" ad almeno altri due numeri (due numeri sono collegati se la loro somma e' un quadrato perfetto).
Questa osservazione permette intanto di escludere tutti gli n<=30:
- se n<=13 allora il 2 e' collegato solo con il 7;
- se 14<=n<=16 allora l'8 e' collegato solo con l'1;
- se n=17 allora il 17 e' collegato solo con l'8;
- se 18<=n<=30 allora il 18 e' collegato solo con il 7.

Per n=31 tutti i numeri hanno almeno altri due numeri collegati quindi questa osservazione non basta. Vediamo la situazione:

1 e' collegato a 3,8,15,24;
2 e' collegato a 7,14,23;
3 e' collegato a 1,6,13,22;
4 e' collegato a 5,12,21;
5 e' collegato a 4,11,20,31;
6 e' collegato a 3,10,19,30;
7 e' collegato a 2,9,18,29;
8 e' collegato a 1,17,28;
9 e' collegato a 7,16,27;
10 e' collegato a 6,15,26;
11 e' collegato a 5,14,25;
12 e' collegato a 4,13,24;
13 e' collegato a 3,12,23;
14 e' collegato a 2,11,22;
15 e' collegato a 1,10,21;
16 e' collegato a 9,20;
17 e' collegato a 8,19;
18 e' collegato a 7,31;
19 e' collegato a 6,17,30;
20 e' collegato a 5,16,29;
21 e' collegato a 4,15,28;
22 e' collegato a 3,14,27;
23 e' collegato a 2,13,26;
24 e' collegato a 1,12,25;
25 e' collegato a 11,24;
26 e' collegato a 10,23;
27 e' collegato a 9,22;
28 e' collegato a 8,21;
29 e' collegato a 7,20;
30 e' collegato a 6,19;
31 e' collegato a 5,18.

Grazie a questo schema possiamo iniziare la costruzione dell'ipotetica sequenza proprio dai numeri che hanno esattamente due collegamenti. Ad esempio il 30 e' collegato solo al 6 e al 19 quindi nella sequenza circolare dovremo avere un blocco 6,30,19 (o anche 19,30,6, ma siccome la sequenza dovra' essere circolare l'orientazione e' indifferente). Notiamo che anche il 17 ha solo due collegamenti ossia l'8 e il 19 e quindi ci sara' anche un blocco 19,17,8 che e' unito al blocco precedente ottenendo 6,30,19,17,8. Con lo stesso ragionamento, siccome il 28 e' unito solo al 8 e al 21, possiamo ancora prolungare il blocco fino a 6,30,19,17,8,28,21. Qui la costruzione si interrompe perche' le estremita' 6 e 21 sono unite a numeri che hanno piu' di due collegamenti. In questo modo si possono individuare vari blocchi forzati fino ad arrivare al seguente diagramma:
Non possiamo ancora concludere che la sequenza circolare non e' realizzabile, ma abbiamo diminuito drasticamente le combinazioni da controllare!
La dimostrazione prosegue nel seguente modo: facciamo vedere che l'1 e il 15 devono essere necessariamente adiacenti. Se cosi' non fosse dal diagramma si deduce che l'1 deve essere tra il 24 e il 3 mentre il 15 deve stare tra il 21 e il 20:
(11,25,24),1,(3,13,12) e (6,30,19,17,8,28,21),15,(10,26,23,2,14) l'estremita' 6 e' collegabile solo con il 3 e il 10 che pero' nella sequenza hanno gia' due numeri adiacenti! Quindi l'1 e il 15 devono stare necessariamente vicini. Con un po' di pazienza si puo' continuare in questo modo fino ad escludere tutte le possibilita'.

La costruzione della sequenza circolare per n=32 si puo' facilitare ragionando in modo molto simile Ecco la sequenza con i blocchi e il diagramma con il percorso evidenziato in blu: (1,8,28,21),(4,32,17,19,30,6),(3,13,12),(24,25,11),(5,31,18,7,29,20,16,9,27,22),(14,2,23,26,10),(15)
Q.E.D.

Secondo una congettura (qui c'e' la verifica fino a n=150)) pare che per ogni n>=32 sia sempre possibile costruire una sequenza circolare. Qui ci accontentiamo di dare un'idea di come puo' funzionare un programma che in tempi ragionevoli trovi una sequenza per un n "piccolo". Le sequenze piu' lunghe che sono state trovate da voi sono le seguenti:

64	09/01/06 11:20:23	Raffaele Rossi	1,3,6,10,15,21,4,5,11,14,50,31,18,7,2,23,13,12,24,25,39,42,58,63,37, 44,56,8,41,40,60,61,20,29,52,48,33,16,9,55,26,38,43,57,64,17,32,49, 51,30,34,47,53,28,36,45,19,62,59,22,27,54,46,35
59	07/01/06 11:02:32	Riccardo Paolillo	1,3,6,10,15,21,4,5,11,14,50,31,18,7,2,23,58,42,39,25,56,8,17,32,49,51, 13,36,28,53,47,34,30,19,45,55,26,38,43,57,24,12,37,44,20,29,52,48,33,16, 9,40,41,59,22,27,54,46,35

Per ottenere delle sequenze di questo tipo si puo' scrivere un programma che attraverso il backtracking effettua una ricerca esaustiva. Il programma per n<32 non trova nessuna sequenza circolare e dato che durante la ricerca vengono esplorate tutte le possibilita' il programma puo' essere accettato a pieno diritto come un'altra dimostrazione che 32 e' il minimo (cosi' ha fatto Paolillo). Ma la ricerca esaustiva diventa molto dispendiosa al crescere di n perche' il numero di combinazioni da controllare cresce molto velocemente! Questo tipo di problema e' ben noto nella teoria dei grafi come ricerca di un ciclo hamiltoniano che e' risaputo essere un compito intrinsecamente complesso dal punto di vista computazionale. Una strategia alternativa alla ricerca esaustiva puo' essere quella di effettuare una passeggiata casuale lungo il grafo: si parte da un numero e ad ogni passo si scegli a caso uno dei collegamenti possibili. Quando la costruzione si blocca si verifica se la sequenza e' completa altrimenti si ricomincia da capo. Ad esempio un algoritmo di questo genere potrebbe generare questa sequenza:
17
17,8
17,8,1
17,8,1,15
17,8,1,15,21
17,8,1,15,21,28
bloccandosi a 28 perche' i possibili collegamenti 8 e 21 sono gia' impiegati. Ogni "passeggiata" ha un basso costo computazionale e quindi l'algoritmo puo' provare anche decine di migliaia di tentativi in poco tempo (Ramondino ha trovato cosi' la sequenza per n=32).
L'algoritmo si puo' migliorare implementando un accorgimento per prolungare le sequenze bloccate. Vediamo di cosa si tratta partendo dalla sequenza di prima: 17,8,1,15,21,28. Dato che il 28 e' collegato con l'8, si taglia la sequenza tra 8 e 1, si inverte il blocco (1,15,21,28) ottenendo (28,21,15,1) e si unisce l'estremita' 28 all'8. Ora l'estremita' 1 e' libera e la sequenza puo' essere allungata:
17,8,28,21,15,1
17,8,28,21,15,1,3
17,8,28,21,15,1,3,6
17,8,28,21,15,1,3,6,30
17,8,28,21,15,1,3,6,30,19
Il seguente generatore "random" di sequenze circolari utilizza proprio questa tecnica e pur essendo scritto in javascript, per n<100 e' piuttosto veloce (se si toglie il prolungamento i tempi si allungano!!). Se n>=100 e' consigliabile un algoritmo piu' raffinato scritto in qualche linguaggio compilabile. In rete ci sono diversi programmi dedicati alla ricerca in un grafo di circuiti hamiltoniani. Vi segnalo la pagina di Ashay Dharwadker da dove potete scaricare il programma con il quale e' stata determinata la sequenza circolare per n=2006.

n=, numero massimo di tentativi= , con prolungamento:

Si noti che come documentato nella On-Line Encyclopedia of Integer Sequences si conosce anche il numero di sequenze circolari (non equivalenti a meno di traslazioni o di cambio dell'orientazione) per n<=47:

n	nr. di sequenze
32	1
33	1
34	11
35	57
36	31
37	20
38	25
39	50
40	64
41	464
42	1062
43	4337
44	10091
45	21931
46	69623
47	115913

Fino a n=34 il numero di sequenze e' stato trovato anche dall'algoritmo esaustivo di Paolillo.