|
%I #50 Aug 04 2019 11:40:46
%S 1,0,0,1,0,1,1,1,9,14,32,184,123,696,935,6554,21105,60756,241780,
%T 517970,1835109,5741024,16091004,63590090,285113492,1098219807
%N 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.
%C 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.
%C Proof: By examples, the result holds for n = 6, ..., 11. Below we assume n > 11 and exhibit a circular permutation meeting the requirement.
%C 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).
%C If n == 3 (mod 6), then we may take the circular permutation
%C (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).
%C If n == 1 (mod 6), then we may take the circular permutation
%C (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).
%C 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).
%C 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).
%C If n == 5 (mod 6), then we may take the circular permutation
%C (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).
%C 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.
%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1309.1679">Some new problems in additive combinatorics</a>, preprint, arXiv:1309.1679 [math.NT], 2013-2014.
%e a(1) = 1 due to the circular permutation (0,1).
%e a(4) = 1 due to the circular permutation (0,1,2,3,4).
%e a(6) = 1 due to the circular permutation (0,1,5,6,2,3,4).
%e a(7) = 1 due to the circular permutation (0,1,2,3,7,6,5,4).
%e a(8) = 1 due to the circular permutation (0,1,5,6,2,3,7,8,4).
%e a(9) = 9 due to the circular permutations
%e (0,1,2,3,4,5,6,7,8,9), (0,1,2,3,4,8,7,6,5,9),
%e (0,1,2,3,7,6,5,4,8,9), (0,1,2,3,7,6,5,9,8,4),
%e (0,1,2,6,5,4,3,7,8,9), (0,1,2,6,5,9,8,7,3,4),
%e (0,1,5,4,3,2,6,7,8,9), (0,1,5,9,8,7,6,2,3,4),
%e (0,4,3,2,1,5,6,7,8,9).
%e a(10) > 0 due to the permutation (0,1,2,3,7,8,9,10,6,5,4).
%e a(11) > 0 due to the permutation (0,1,5,9,8,7,11,10,6,2,3,4).
%t (* 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. *)
%t SQ[n_]:=SQ[n]=IntegerQ[Sqrt[n]]
%t f[i_,j_]:=f[i,j]=SQ[Abs[i-j]]
%t V[i_]:=V[i]=Part[Permutations[{1,2,3,4,5,6,7,8}],i]
%t m=0
%t 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!}]
%Y Cf. A000290, A185645, A228626, A228728, A228956, A229005.
%K nonn,more,hard
%O 1,9
%A _Zhi-Wei Sun_, Sep 25 2013
%E a(10)-a(24) from _Alois P. Heinz_, Sep 26 2013
%E a(25)-a(26) from _Max Alekseyev_, Jan 08 2015
|
