|
|
A071984
|
|
Square loops: the number of circular permutations (reversals not counted as different) of the numbers 1 to n such that the sum of any two consecutive numbers is a square.
|
|
11
|
|
|
1, 1, 11, 57, 31, 20, 25, 50, 64, 464, 1062, 4337, 10091, 21931, 69623, 115913, 227893, 457707, 297126, 1051583, 3377189, 7618873, 12476654, 25832098, 55792448, 75126741, 129180538, 357114149, 823402071, 3902161448, 20043267339, 131420398568
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
32,3
|
|
COMMENTS
|
It is unknown whether a circular permutation of the numbers 1 to n exists such that the sum of any two consecutive numbers is a cube.
According to Rivera's Puzzle 311, the smallest n for which a cubic loop exists is 473. - T. D. Noe, Nov 26 2007
It is easy to see that no solutions for n <= 30 can exist: for each value of n <= 30 at least one number exists that can only be paired with at most one other number to form a square (e.g., 18 for n=30 can only be paired with 7). No Hamiltonian cycle can exist if the graph contains a vertex of degree less than 2.
For the case n=31, the nonexistence of a Hamiltonian cycle is less trivial but can be shown by hand.
(End)
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
There is only one possible square loop of minimum length, which is (32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17) so a(32)=1.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nice,nonn,more,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|