A229543 Number of undirected circular permutations 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 perfect squares.

1, 0, 0, 1, 0, 1, 1, 1, 9, 14, 32, 184, 123, 696, 935, 6554, 21105, 60756, 241780, 517970, 1835109, 5741024, 16091004, 63590090, 285113492, 1098219807

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

Table of n, a(n) for n=1..26.

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

Cf. A000290, A185645, A228626, A228728, A228956, A229005.

Sequence in context: A093021 A360406 A272781 * A175201 A066793 A275508

Adjacent sequences: A229540 A229541 A229542 * A229544 A229545 A229546

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