cp's OEIS Frontend

A228860 Number of permutations i_1,...,i_n of 1,...,n with i_1 = 1 and i_n = n, and with the n adjacent sums i_1+i_2, i_2+i_3, ..., i_{n-1}+i_n, i_n+i_1 all coprime to n.

%I A228860 #38 Jan 01 2019 06:31:06
%S A228860 1,1,0,1,2,1,40,36,144,78,126336,176,14035200,69480,779436,25401600,
%T A228860 465334732800,1700352,127064889262080,1888106496,1479065243520,
%U A228860 1774752094080,18353630943019008000,144127475712,116009818818379776000,30959322906758400,373881853408444416000
%N A228860 Number of permutations i_1,...,i_n of 1,...,n with i_1 = 1 and i_n = n, and with the n adjacent sums i_1+i_2, i_2+i_3, ..., i_{n-1}+i_n, i_n+i_1 all coprime to n.
%C A228860 Conjecture: a(n) > 0 except for n = 3.
%C A228860 If n is a power of two, then a(n) > 0 since the identical permutation 1,2,3,...,n meets the requirement. For any prime p > 3, we have a(p) > 0 since the permutation 1,...,(p-1)/2, (p+3)/2,(p+1)/2,(p+5)/2,...,p meets our purpose.
%C A228860 Let G(n) be the undirected simple graph with vertices 1,...,n which has an edge connecting two distinct vertices i and j if and only if i + j is relatively prime to n. Then, for any n > 2, the number a(n) is just the number of those Hamiltonian cycles in G(n) on which the vertices 1 and n are adjacent.
%C A228860 Let m be any integer relatively prime to n, and let i_k be the smallest positive residue of k*m modulo n. Then i_1, i_2, ..., i_n is a permutation of 1, ..., n with the n adjacent differences i_1-i_2, i_2-i_3, ..., i_{n-1}-i_n, i_n-i_1 all coprime to n.
%C A228860 On Sep 06 2013, the author's two former PhD students Hui-Qin Cao (from Nanjing Audit Univ.) and Hao Pan (from Nanjing Univ.) proved the conjecture fully.
%e A228860 a(4) = 1 due to the permutation 1,2,3,4.
%e A228860 a(5) = 2 due to the permutations 1,2,4,3,5 and 1,3,4,2,5.
%e A228860 a(6) = 1 due to the permutation 1,4,3,2,5,6.
%e A228860 a(7) > 0 due to the permutation 1,2,3,5,4,6,7.
%e A228860 a(8) > 0 due to the permutation 1,2,3,4,5,6,7,8.
%e A228860 a(9) > 0 due to the permutation 1,3,2,5,8,6,4,7,9.
%e A228860 a(10) > 0 due to the permutation 1,2,5,4,7,6,3,8,9,10.
%e A228860 a(11) > 0 due to the permutation 1,2,3,4,5,7,6,8,9,10,11.
%e A228860 a(12) > 0 due to the permutation 1,4,9,2,5,8,3,10,7,6,11,12.
%t A228860 (*A program to compute the required permutations for n = 9.*)
%t A228860 V[i_]:=Part[Permutations[{2,3,4,5,6,7,8}],i]
%t A228860 m=0
%t A228860 Do[Do[If[GCD[If[j==0,1,Part[V[i],j]]+If[j<7,Part[V[i],j+1],9],9]>1,Goto[aa]],{j,0,7}];
%t A228860 m=m+1;Print[m,":"," ",1," ",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]," ",9];Label[aa];Continue,{i,1,7!}]
%Y A228860 Cf. A051252, A185645, A228626, A228728, A228762, A228766.
%K A228860 nonn,hard
%O A228860 1,5
%A A228860 _Zhi-Wei Sun_, Sep 05 2013
%E A228860 a(12)-a(27) from _Max Alekseyev_, Sep 13 2013