cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

A228766 Number of undirected circular permutations i_1,...,i_{n-1} of 1,...,n-1 with i_1 + i_2, i_2 + i_3, ..., i_{n-2} + i_{n-1}, i_{n-1} + i_1 pairwise distinct modulo n.

Original entry on oeis.org

0, 1, 1, 1, 1, 12, 21, 74, 309, 1376, 5016, 27198, 138592, 928544, 4735266, 31263708, 206761952, 1677199872, 11111483094
Offset: 3

Views

Author

Zhi-Wei Sun, Sep 03 2013

Keywords

Comments

Conjecture: a(n) > 0 for all n > 3. In general, if a_1,...,a_n are n > 2 distinct elements of a finite additive abelian group G with n odd or |G| not divisible by n, then there exists a circular permutation b_1,...,b_n of a_1,...,a_n such that b_1+b_2, b_2+b_3, ..., b_{n-1}+b_n, b_n+b_1 are pairwise distinct.
Note that if g is a primitive root modulo a prime p > 3 then 1+g, g+g^2, ..., g^{p-3}+g^{p-2}, g^{p-2}+1 are pairwise distinct modulo p. So a(p) > 0 for any prime p > 3.
If n > 2 is odd, then 0+1, 1+2, ..., (n-2)+(n-1), (n-1)+0 are pairwise distinct modulo n, and hence the conjecture holds in the case {a_1,...,a_n} = G = Z/nZ.

Examples

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

Links

Crossrefs

Cf. A228762, A228772, A185645, A228728.

Programs

  • Mathematica
    (* A program to compute required circular permutations for n = 9. To get "undirected" circular permutations, we should identify a circular permutation with the one of the opposite direction; for example, (1,7,8,5,6,4,3,2) is identitical to (1,2,3,4,6,5,8,7) if we ignore direction. *)
V[i_]:=Part[Permutations[{2,3,4,5,6,7,8}],i]
m=0
Do[If[Length[Union[{Mod[1+Part[V[i],1],9]},Table[Mod[Part[V[i],j]+If[j<7,Part[V[i],j+1],1],9],{j,1,7}]]]<8,Goto[aa]];
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]];Label[aa];Continue,{i,1,7!}]
  • Sage
    import itertools
def a(n):
    ans = 0
    for p in itertools.permutations([i for i in range(1, n)]):
        if len(set((p[i]+p[(i+1)%(n-1)])%n for i in range(n-1))) == n-1: ans += 1
    return ans/(2*n-2)  # Robin Visser, Sep 27 2023

Extensions

a(12)-a(19) from Bert Dobbelaere, Sep 08 2019
a(20)-a(21) from Robin Visser, Sep 27 2023

A227399 Number of permutations i_1, ..., i_n of 1, ..., n with i_1 = 1 and i_n = n such that i_1+2*i_2, i_2+2*i_3, ..., i_{n-1}+2*i_n, i_n+2*i_1 are pairwise distinct modulo n.

Original entry on oeis.org

1, 1, 0, 1, 1, 2, 8, 20, 18, 166, 397, 2788, 5448, 78102, 149562, 2576896, 6003432, 91012592, 257246112, 5272355344, 12450552690
Offset: 1

Views

Author

Zhi-Wei Sun, Sep 20 2013

Keywords

Comments

If n is not divisible by 3 then a(n) > 0 since the identical permutation of 1 ,..., n works for the purpose. If n is even, then a(n) > 0 since the permutation 1, 2, n-1, 4, n-3, 6, n-5, ..., n-2, 3, n meets the requirement. We guess that a(n) > 0 in the remaining case n = 6q+3 with q > 0. If n = 2k+1 == 3 (mod 6) with n > 3, then, for the permutation (i_1,...,i_n) = (1,2k,k,2k-1,k-1,2k-2,...,3,k+2,2,k+1,2k+1), all the n sums i_1+2*i_2, i_2+2*i_3, ..., i_{n-1}+2*i_n, i_n+2*i_1 are pairwise distinct (but they are not pairwise incongruent modulo n = 2k+1 when n > 9).
Zhi-Wei Sun also made the following general conjecture:
(i) (Weak version) Let a_1,...,a_n be n distinct elements of an additive abelian group G. Then, there is a permutation b_1,...,b_n of a_1,...,a_n such that a_1+2*b_1, a_2+2*b_2, ..., a_n+2*b_n are pairwise distinct. (The author has proved this for n up to 4 in any abelian group G.)
(ii) (Strong version) Let A be any subset of an additive abelian group G with |A| = n > 4. Then there is a numbering a_1, ..., a_n of all the elements of A such that a_1+2*a_2, a_2+2*a_3, ..., a_{n-1}+2*a_n, a_n+2*a_1 are pairwise distinct. (The author has proved this for any torsion-free abelian group G.)
Recall that a conjecture of Snevily proved by Arsovski states that for any two n-subsets A and B of an additive abelian group of odd order there is a numbering a_1,...,a_n of all the elements of A and a numbering b_1, ..., b_n of all the elements of B such that the n sums a_1+b_1, ..., a_n+b_n are pairwise distinct.

Examples

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

Links

Crossrefs

Cf. A228772, A228766.

Programs

  • Mathematica
    (* A program to compute desired permutations for n = 9. *)
V[i_]:=Part[Permutations[{2,3,4,5,6,7,8}],i]
m=0
Do[If[Length[Union[{2},Table[Mod[If[j==0,1,Part[V[i],j]]+2*If[j<7,Part[V[i],j+1],9],9],{j,0,7}]]]<9,Goto[aa]];
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(21) from Robin Visser, Aug 21 2023
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.