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.

1, 1, 0, 1, 2, 1, 40, 36, 144, 78, 126336, 176, 14035200, 69480, 779436, 25401600, 465334732800, 1700352, 127064889262080, 1888106496, 1479065243520, 1774752094080, 18353630943019008000, 144127475712, 116009818818379776000, 30959322906758400, 373881853408444416000

Offset: 1

Author

Zhi-Wei Sun, Sep 05 2013

Keywords

• nonn
• hard

Comments

Conjecture: a(n) > 0 except for n = 3.

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.

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.

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.

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.

Examples

			a(4) = 1 due to the permutation 1,2,3,4.
a(5) = 2 due to the permutations 1,2,4,3,5 and 1,3,4,2,5.
a(6) = 1 due to the permutation 1,4,3,2,5,6.
a(7) > 0 due to the permutation 1,2,3,5,4,6,7.
a(8) > 0 due to the permutation 1,2,3,4,5,6,7,8.
a(9) > 0 due to the permutation 1,3,2,5,8,6,4,7,9.
a(10) > 0 due to the permutation 1,2,5,4,7,6,3,8,9,10.
a(11) > 0 due to the permutation 1,2,3,4,5,7,6,8,9,10,11.
a(12) > 0 due to the permutation 1,4,9,2,5,8,3,10,7,6,11,12.
		

Crossrefs

Cf. A051252, A185645, A228626, A228728, A228762, A228766.

Programs

Mathematica

(*A program to compute the required permutations for n = 9.*)
V[i_]:=Part[Permutations[{2,3,4,5,6,7,8}],i]
m=0
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}];
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!}]

Extensions

a(12)-a(27) from Max Alekseyev, Sep 13 2013