login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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,...,(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.

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

Zhi-Wei Sun, Sep 05 2013

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 15 22:19 EDT 2019. Contains 324145 sequences. (Running on oeis4.)