

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_{n1}+i_n, i_n+i_1 all coprime to n.


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


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,...,(p1)/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_1i_2, i_2i_3, ..., i_{n1}i_n, i_ni_1 all coprime to n.
On Sep 06 2013, the author's two former PhD students HuiQin Cao (from Nanjing Audit Univ.) and Hao Pan (from Nanjing Univ.) proved the conjecture fully.


LINKS

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


EXAMPLE

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.


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!}]


CROSSREFS

Cf. A051252, A185645, A228626, A228728, A228762, A228766.
Sequence in context: A173838 A038021 A127609 * A271204 A275706 A260884
Adjacent sequences: A228857 A228858 A228859 * A228861 A228862 A228863


KEYWORD

nonn,hard


AUTHOR

ZhiWei Sun, Sep 05 2013


EXTENSIONS

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


STATUS

approved



