A228886 - OEIS

%I #53 Aug 04 2019 05:53:31

%S 1,0,1,0,1,8,3,24,78,1164,34,4021156,400,87180,2499480,7509358,

%T 1700352,39982182134232,1427688,212987263960,9533487948,

%U 36638961135462,29317847040,30258969747586970112,1655088666624

%N Number of permutations i_0,i_1,...,i_n of 0,1,...,n with i_0 = 0 and i_n = n, and with i_0+i_1, i_1+i_2, ..., i_{n-1}+i_n, i_n+i_0 all coprime to both n-1 and n+1.

%C Conjecture: a(n) > 0 except for n = 2, 4.

%C Note that this conjecture is stronger than the one stated in the comments in A228860. Also, there is no permutation i_0, ..., i_7 of 0, ..., 7 with i_0+i_1, i_1+i_2, ..., i_6+i_7, i_7+i_0 all coprime to 7*13 - 1 = 90.

%C For n > 1 let S(n) be an undirected simple graph with vertices 0, 1, ..., n which has an edge connecting two distinct vertices i and j if and only if i + j is relatively prime to both n-1 and n+1. Then a(n) is just the number of those Hamiltonian cycles in S(n) on which the vertices 0 and n are adjacent.

%C We have some other similar conjectures. For example, for any positive integer n there is a permutation i_0,i_1,...,i_n of 0,1,...,n with i_0 = 0 and i_n = n such that i_0 + i_1, i_1 + i_2, ..., i_{n-1} + i_n, i_n + i_0 are all relatively prime to both 2*n-1 and 2*n+1.

%C On Sep 10 2013, Zhi-Wei Sun proved the conjecture for any positive odd integer n. In fact, if n == 1 or 3 (mod 6) then we may take the permutation 0,n-2,2,n-4,4,...,1,n-1,n which meets the requirement; if n == 3 or 5 (mod 6) then the permutation 0,1,n-1,3,n-3,...,n-2,2,n suffices for our purpose.

%H Zhi-Wei Sun, <a href="/A228886/a228886.txt">List of required permutations for n = 1..10</a>

%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(2) = 0 since 1+2 = 2^2-1.

%e a(3) = 1 due to the identical permutation (0,1,2,3).

%e a(4) = 0 since 1+2 divides 4^2-1.

%e a(5) = 1 due to the permutation (0,1,4,3,2,5).

%e a(6) = 8 due to the permutations

%e   (0,1,2,4,5,3,6), (0,1,3,5,4,2,6),

%e   (0,2,4,5,1,3,6), (0,3,1,2,4,5,6),

%e   (0,3,1,5,4,2,6), (0,4,2,1,3,5,6),

%e   (0,4,2,1,5,3,6), (0,4,5,3,1,2,6).

%e a(7) = 3 due to the permutations(0,1,4,3,2,5,6,7), (0,1,6,5,2,3,4,7), (0,5,2,3,4,1,6,7).

%e a(8) > 0 due to the permutation (0,1,4,7,3,2,6,5,8).

%e a(9) > 0 due to the permutation (0,1,2,5,4,7,6,3,8,9).

%e a(10) > 0 due to the permutation (0,1,3,2,5,8,6,4,9,7,10).

%t (*A program to compute the required permutations for n = 8.*)

%t V[i_]:=Part[Permutations[{1,2,3,4,5,6,7}],i]

%t m=0

%t Do[Do[If[GCD[If[j==0,0,Part[V[i],j]]+If[j<7,Part[V[i],j+1],8],8^2-1]>1,Goto[aa]],{j,0,7}]; 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]," ",8];Label[aa];Continue,{i,1,7!}]

%Y Cf. A228860, A228917, A228956.

%K nonn,more,hard

%O 1,6

%A _Zhi-Wei Sun_, Sep 07 2013

%E a(11)-a(25) from _Max Alekseyev_, Sep 13 2013