OFFSET
1,9
COMMENTS
Theorem: For any integer n > 5, there is a circular permutation i_0, i_1, ..., i_n of 0, 1, ..., n with both 1 and 4 adjacent to 0 such that all the n+1 adjacent distances |i_0-i_1|, |i_1-i_2|, ..., |i_{n-1}-i_n|, |i_n-i_0| are perfect squares.
Proof: By examples, the result holds for n = 6, ..., 11. Below we assume n > 11 and exhibit a circular permutation meeting the requirement.
If n == 0 (mod 6), then we may take the circular permutation (n,n-4,n-5,n-6,n-10,n-11,n-12,...,8,7,6,2,3,4,0,1,5,9,10,11,...,n-9,n-8,n-7,n-3,n-2,n-1).
If n == 3 (mod 6), then we may take the circular permutation
(n,n-4,n-5,n-6,n-10,n-11,n-12,...,11,10,9,5,1,0,4,3,2,6,7,8,...,n-9,n-8,n-7,n-3,n-2,n-1).
If n == 1 (mod 6), then we may take the circular permutation
(n,n-4,n-5,n-6,n-10,n-11,n-12,...,9,8,7,3,2,1,0,4,5,6,10,11,12,...,n-9,n-8,n-7,n-3,n-2,n-1).
If n == 4 (mod 6), then we may take the circular permutation (n,n-4,n-5,n-6,n-10,n-11,n-12,...,12,11,10,6,5,4,0,1,2,3,7,8,9,...,n-9,n-8,n-7,n-3,n-2,n-1).
If n == 2 (mod 6), then we may take the circular permutation (n,n-4,n-5,n-6,n-10,n-11,n-12,...,10,9,8,4,0,1,5,6,2,3,7,11,12,13,...,n-9,n-8,n-7,n-3,n-2,n-1).
If n == 5 (mod 6), then we may take the circular permutation
(n,n-4,n-5,n-6,n-10,n-11,n-12,...,13,12,11,7,3,2,6,5,1,0,4,8,9,10,...,n-9,n-8,n-7,n-3,n-2,n-1).
Zhi-Wei Sun also used a similar method to show that for any positive integer n not equal to 2 or 4 there is a circular permutation i_0, i_1, ..., i_n of 0, 1, ..., n such that all the n+1 adjacent distances |i_0-i_1|, |i_1-i_2|, ..., |i_{n-1}-i_n|, |i_n-i_0| are triangular numbers.
LINKS
Zhi-Wei Sun, Some new problems in additive combinatorics, preprint, arXiv:1309.1679 [math.NT], 2013-2014.
EXAMPLE
a(1) = 1 due to the circular permutation (0,1).
a(4) = 1 due to the circular permutation (0,1,2,3,4).
a(6) = 1 due to the circular permutation (0,1,5,6,2,3,4).
a(7) = 1 due to the circular permutation (0,1,2,3,7,6,5,4).
a(8) = 1 due to the circular permutation (0,1,5,6,2,3,7,8,4).
a(9) = 9 due to the circular permutations
(0,1,2,3,4,5,6,7,8,9), (0,1,2,3,4,8,7,6,5,9),
(0,1,2,3,7,6,5,4,8,9), (0,1,2,3,7,6,5,9,8,4),
(0,1,2,6,5,4,3,7,8,9), (0,1,2,6,5,9,8,7,3,4),
(0,1,5,4,3,2,6,7,8,9), (0,1,5,9,8,7,6,2,3,4),
(0,4,3,2,1,5,6,7,8,9).
a(10) > 0 due to the permutation (0,1,2,3,7,8,9,10,6,5,4).
a(11) > 0 due to the permutation (0,1,5,9,8,7,11,10,6,2,3,4).
MATHEMATICA
(* A program to compute required circular permutations for n = 8. To get "undirected" circular permutations, we should identify a circular permutation with the one of the opposite direction. Thus a(8) is half of the number of circular permutations yielded by this program. *)
SQ[n_]:=SQ[n]=IntegerQ[Sqrt[n]]
f[i_, j_]:=f[i, j]=SQ[Abs[i-j]]
V[i_]:=V[i]=Part[Permutations[{1, 2, 3, 4, 5, 6, 7, 8}], i]
m=0
Do[Do[If[f[If[j==0, 0, Part[V[i], j]], If[j<8, Part[V[i], j+1], 0]]==False, Goto[aa]], {j, 0, 8}]; m=m+1; Print[m, ":", " ", 0, " ", Part[V[i], 1], " ", Part[V[i], 2], " ", Part[V[i], 3], " ", Part[V[i], 4], " ", Part[V[i], 5], " ", Part[V[i], 6], " ", Part[V[i], 7], " ", Part[V[i], 8]]; Label[aa]; Continue, {i, 1, 8!}]
CROSSREFS
KEYWORD
nonn,more,hard
AUTHOR
Zhi-Wei Sun, Sep 25 2013
EXTENSIONS
a(10)-a(24) from Alois P. Heinz, Sep 26 2013
a(25)-a(26) from Max Alekseyev, Jan 08 2015
STATUS
approved