A000793 -id:A000793 - cp's OEIS frontend

A289386 Number of rounds of 'deal one, skip one' shuffling required to return a deck of n cards to its original order.

1, 2, 3, 2, 5, 6, 5, 4, 6, 6, 15, 12, 12, 30, 15, 4, 17, 18, 10, 20, 21, 14, 24, 90, 63, 26, 27, 18, 66, 12, 210, 12, 33, 90, 35, 30, 110, 120, 120, 26, 41, 42, 105, 30, 45, 30, 60, 48, 120, 50, 42, 510, 53, 1680, 120, 1584, 57, 336, 276, 60, 2665, 720, 8415

Offset: 1

Andrew Warren, Jul 04 2017

Origin unknown. First encountered by this author as part of an employment-interview question at Apple Inc, in early 2016.
While holding a deck of n cards:
1. Deal the top card from the deck onto the table ('deal one').
2. Move the next card from the top of the deck to the bottom of the deck ('skip one').
3. Repeat steps 1 and 2 until all cards are on the table. This is a round.
4. Pick up the deck from the table and repeat steps 1 through 3 until the deck is in its original order.
From Robert Israel, Jul 06 2017: (Start)
a(n) <= A000793(n).
a(n) divides n!.
Conjecture: a(n) < n for infinitely many n.
Conjecture: the set of n for which the permutation is a single n-cycle, and thus a(n) = n, has nonzero density. (End)
It appears that for n = 2^k and all m > n, a(n) <= a(m). - Andrew Warren, Jul 15 2017
a(2^(k+1)) / a(2^k) = A020513(k+2) at least for 1 <= k <= 30, according to the values computed by Andrew Warren. - Andrey Zabolotskiy, Apr 02 2018

			Cards are labeled 'A', 'B', 'C', etc. 'ABCD' is a deck with 'A' on top, 'D' on the bottom.
For n = 4:
Round 1:
Hand: ABCD    Table: [empty] - initial state of Round 1
Hand: BCD     Table: A       - Deal one
Hand: CDB     Table: A       - Skip one
Hand: DB      Table: CA      - Deal one
Hand: BD      Table: CA      - Skip one
Hand: D       Table: BCA     - Deal one
Hand: D       Table: BCA     - Skip one
Hand: [empty] Table: DBCA    - Deal one, end of Round 1
Round 2:
Hand: DBCA    Table: [empty] - Initial state of Round 2
Hand: BCA     Table: D       - Deal one
Hand: CAB     Table: D       - Skip one
Hand: AB      Table: CD      - Deal one
Hand: BA      Table: CD      - Skip one
Hand: A       Table: BCD     - Deal one
Hand: A       Table: BCD     - Skip one
Hand [empty]  Table: ABCD    - Deal one, end of Round 2
The deck of 4 cards is in its original order ('ABCD') after 2 rounds, so a(4) = 2.

Robert Israel, Table of n, a(n) for n = 1..4000
Andrew Warren, C program to generate a(n)

Cf. A000793, A051732 (variation with cards dealt face up), A020513, A051168.

C
```
// see link
```

F:= proc(n)
local deck, table, i;
deck:= [$1..n];
table:= NULL;
for i from 1 to n-1 do
  table:= deck[1],table;
  deck:= deck[[$3..nops(deck),2]];
od:
ilcm(op(map(nops,convert([deck[1],table],'disjcyc'))));
end proc:
map(F, [$1..100]); # Robert Israel, Jul 06 2017

P[n_, i_] := Module[{d = 2i - 1}, While[d < n, d *= 2]; 2n - d];
Follow[s_, f_] := Module[{t = f[s], k = 1}, While[t > s, k++; t = f[t]]; If[s == t, k, 0]];
CyclePoly[n_, x_] := Module[{q = 0}, For[i = 1, i <= n, i++, l = Follow[i, P[n, #]&]; If[l != 0, q += x^l]]; q];
a[n_] := Module[{q = CyclePoly[n, x], m = 1}, For[i = 1, i <= Exponent[q, x], i++, If[Coefficient[q, x, i] != 0, m = LCM[m, i]]]; m];
Array[a, 60] (* Jean-François Alcover, Apr 09 2020, after Andrew Howroyd *)

deal(v)=my(deck=List(v),new=List(),cutoff=4000+#v,i=1); while(#deck>=i, listput(new,deck[i]); if(i++>#deck, break); listput(deck, deck[i]); if(#deck>cutoff, deck=List(deck[i+1..#deck]); i=0); i++); Vecrev(new)
ordered(v)=for(i=1,#v, if(v[i]!=i, return(0))); 1
a(n)=my(v=[1..n],t=1); while(!ordered(v=deal(v)), t++); t \\ Charles R Greathouse IV, Jul 06 2017

\\ alternative for larger n such as 2^n.
P(n,i)=my(d=2*i-1); while(ds, k++; t=f(t)); if(s==t, k, 0)}
CyclePoly(n, x)={my(q=0); for(i=1, n, my(l=Follow(i, j->P(n, j))); if(l, q+=x^l)); q}
a(n)={my(q=CyclePoly(n, x), m=1); for(i=1, poldegree(q), if(polcoeff(q, i), m=lcm(m, i))); m} \\ Andrew Howroyd, Nov 11 2017

A074103 a(n) = n!/A074859(n).

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 3, 12, 15, 20, 30, 15, 60, 60, 84, 105, 140, 210, 105, 420, 420, 420, 315, 840, 840, 1260, 1260, 1540, 2310, 2520, 4620, 4620, 5460, 5460, 9240, 9240, 13860, 13860, 16380, 16380, 27720, 30030, 32760, 60060, 60060, 60060, 45045, 120120

Offset: 0

Vladeta Jovovic, Sep 15 2002

nonn

1/a(n) is probability that a random degree-n permutation has the maximum possible order.

Alois P. Heinz, Table of n, a(n) for n = 0..175

Cf. A074859, A000793.

g[n_] := g[n] = Max[LCM @@@ IntegerPartitions[n]];
f[x_, n_] := Total[(MoebiusMu[g[n]/#]*Exp[Total[(x^#/#&) /@ Divisors[#]]]&) /@ Divisors[g[n]]];
a[0] = 1; a[n_] := 1/SeriesCoefficient[f[x, n], {x, 0, n}];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 24 2019 *)

More terms from Max Alekseyev, Jun 13 2011

A074260 Number of labeled cyclic subgroups of S_n having the maximum possible order.

Original entry on oeis.org

1, 1, 1, 1, 3, 10, 120, 105, 336, 2268, 15120, 332640, 498960, 6486480, 43243200, 259459200, 3113510400, 35286451200, 1270312243200, 3016991577600, 60339831552000, 1267136462592000, 37169336236032000, 160292762517888000

Offset: 0

Vladeta Jovovic, Sep 20 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..100

Cf. A051625, A074064.

a(n) = A074859(n)/A000010(A000793(n)).

A181949 Weighted sum of all cyclic subgroups of the Symmetric Group.

Original entry on oeis.org

1, 3, 10, 43, 231, 1531, 11068, 89895, 820543, 8484871, 95647476, 1186289083, 15648402355, 221728356123, 3354790995676, 53999879550991, 936289020367263, 17163114699673615, 328827078340587148, 6630244432204704771, 139769193881466850051, 3092293682224076627683

Offset: 1

Olivier Gérard, Apr 03 2012

Sum of the orders of all cyclic subgroups of the Sym_n.
The identity permutation is counted for each subgroup, i.e. A051625(n) times.
Each permutation is counted several times according to its conjugacy class.

			a(4) = 1*1 + 2*3 + 2*6 + 3*4 + 4*3 = 1+6+12+12+12 = 43.

Cf. A000793, A051625, A074881.

a(n) = Sum_{k=1..A000793(n)} k*A074881(n, k). - Andrew Howroyd, Jul 02 2018

a(9)-a(22) from Andrew Howroyd, Jul 02 2018

A225725 Triangle of transformation semigroup sizes generated by a single element.

Original entry on oeis.org

1, 1, 3, 1, 10, 15, 2, 41, 129, 80, 6, 196, 1115, 1260, 510, 24, 20, 1057, 10395, 17780, 12840, 3744, 840, 6322, 105315, 258510, 264810, 135492, 47250, 4920, 0, 0, 504, 0, 420, 41393, 1160635, 4018000, 5318180, 3788400, 1837024, 513120, 38640, 0, 32256, 0, 26880, 0, 0, 2688

Offset: 0

Chad Brewbaker, May 14 2013

If you take the powers of a finite function you generate a lollipop graph. A222029 organizes the lollipops by cycle size. The table organized by total lollipop size with the tail included is this triangle.

			T(1,1) = #{[0]} = 1.
T(2,1) = #{[0,1], [0,0], [1,1]} = 3.
T(2,2) = #{[1,0]} = 1.
Triangle begins:
:    1;
:    1;
:    3,      1;
:   10,     15,      2;
:   41,    129,     80,      6;
:  196,   1115,   1260,    510,     24,    20;
: 1057,  10395,  17780,  12840,   3744,   840;
: 6322, 105315, 258510, 264810, 135492, 47250, 4920, 0, 0, 504, 0, 420;

Chad Brewbaker, Ruby program for A225725

First column is A000248.
Row sums are: A000312.
Row lengths are A000793.
Number of nonzero elements of rows give A009490.
Cf. A222029.

Ruby
```
# See Brewbaker link.
```

More terms, some terms corrected by Alois P. Heinz, Aug 17 2017

A382780 Sum of the orders of all permutations of [n] with distinct cycle lengths.

Original entry on oeis.org

1, 1, 2, 12, 48, 360, 2520, 22680, 221760, 2298240, 28425600, 385862400, 5269017600, 80951270400, 1347631084800, 21565729785600, 413922526617600, 8409043612569600, 172028224598630400, 3765253760710041600, 84080417596471296000, 1935910813364656128000

Offset: 0

Alois P. Heinz, May 11 2025

nonn

			a(3) = 12 = 2+2+2+3+3: (1)(23), (13)(2), (12)(3), (123), (132).

Alois P. Heinz, Table of n, a(n) for n = 0..170
Wikipedia, Permutation

Cf. A000142, A000793, A007838, A060014, A382781.

b:= proc(n, i, m) option remember; `if`(i*(i+1)/2 b(n$2, 1):
seq(a(n), n=0..22);

A002497 Numbers N in A002809 such that there is rho > 0 such that for all A > 0, A008475(A)-A008475(N) >= rho*log(A/N).

Original entry on oeis.org

3, 12, 60, 420, 4620, 60060, 180180, 360360, 6126120, 116396280, 2677114440, 77636318760, 2406725881560, 89048857617720, 3651003162326520, 156993135980040360, 313986271960080720, 14757354782123793840, 14757354782123793840, 782139803452561073520, 46146248403701103337680

Offset: 1

N. J. A. Sloane

The numbers contain the starred entries on pp. 187-190 of Nicolas. It is a subsequence of A002809 by selecting only elements of a set/property "G" (page 150). G contains all N such that a real, strictly positive rho exists such that for all strictly positive integers A we have l(A)-l(N) >= rho*log(A/N). The function l()=A008475() is defined on page 139. - R. J. Mathar, Mar 23 2012

These numbers were named superior l-composite numbers (nombres l-composes superieurs, the function l(n) is A002809) by Massias, in analogy to Ramanujan's superior highly composite numbers (A002201). Deléglise and Nicolas named these numbers l-superchampion numbers. They are used by Deléglise et al. in calculating values of Landau's function g(n) (A000793). - Amiram Eldar, Aug 23 2019

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Marc Deléglise and Jean-Louis Nicolas, The Landau function and the Riemann hypothesis, arXiv preprint, arXiv:1907.07664 [math.NT] (2019).
Marc Deléglise, Jean-Louis Nicolas, and Paul Zimmermann, Landau's function for one million billions, Journal de théorie des nombres de Bordeaux, Vol. 20. No. 3 (2008), pp. 625-671.
Jean-Pierre Massias, Majoration explicite de l'ordre maximum d'un élément du groupe symétrique, Annales de la Faculté des Sciences de Toulouse: Mathématiques, Vol. 6, No. 3-4 (1984), pp. 269-281.
Jean-Louis Nicolas, Ordre maximum d'un élément du groupe S(n) des permutations et "highly composite numbers", Bull. Soc. Math. Française 97 (1969), 129-191.

Cf. A000793, A002201, A002498, A002809, A008475.

Edited by M. F. Hasler, Mar 29 2015

a(16)-a(21) from the paper by Massias added by Amiram Eldar, Aug 23 2019

A005417 Maximal period of an n-stage shift register.

Original entry on oeis.org

2, 6, 12, 30, 60, 120, 210, 420, 840, 1260, 2520, 2520, 5040, 9240, 13860, 27720, 32760, 55440, 65520, 120120, 180180, 360360, 360360, 720720, 720720, 942480, 1113840

Offset: 0

N. J. A. Sloane

Maximal order of an element of finite order in GL(2n, Z) or GL(2n+1, Z).

a(n) is the max of the first n numbers in A080742.

H. Lüneburg, Galoisfelder, Kreisteilungskörper und Schieberegisterfolgen. B. I. Wissenschaftsverlag, Mannheim, 1979.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Benjamin Grossmann, What is the largest (finite) order of an element of GL(10,Q)?
J. Kuzmanovich and A. Pavlichenkov, Finite groups of matrices whose entries are integers, Amer. Math. Monthly, 109 (2002), 173-186.

Cf. A000793, A080742, A080743.

(* b,c = a080737 *)
nmax = 26;
kmax = 1200000; (* kmax increased by 100000 until results do not change *)
b[1] = b[2] = 0; b[p_?PrimeQ] := b[p] = p-1; b[k_] := b[k] = If[Length[f = FactorInteger[k]]==1, EulerPhi[k], Total[b /@ (f[[All, 1]]^f[[All, 2]])] ];
orders = Table[{k, b[k]}, {k, 1, kmax}];
c[0] = 2; c[n_] := c[n] = Select[orders, 2n-1 <= #[[2]] <= 2n&][[-1, 1]];
a[n_] := Table[c[m], {m, 0, n}] // Max;
Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Dec 17 2017 *)

a(n) = max m such that A067240(m) <= 2n + 1. E.g., a(2) = 12 since 12 is largest m such that A067240(m) <= 5.

Entry revised by N. J. A. Sloane, Mar 10 2002

A213206 Largest order of permutation without a 2-cycle of n elements. Equivalently, largest LCM of partitions of n without parts =2.

Original entry on oeis.org

1, 1, 1, 3, 4, 5, 6, 12, 15, 20, 21, 30, 60, 60, 84, 105, 140, 140, 210, 420, 420, 420, 420, 840, 840, 1260, 1260, 1540, 1540, 2520, 4620, 4620, 5460, 5460, 9240, 9240, 13860, 13860, 16380, 16380, 27720, 27720, 32760, 60060, 60060, 60060, 60060, 120120, 120120, 180180, 180180, 180180

Offset: 0

Joerg Arndt, Feb 15 2013

nonn

			The 11 partitions (including those with parts =2) of 6 are the following:
[ #]  [ partition ]   LCM( parts )
[ 1]  [ 1 1 1 1 1 1 ]   1
[ 2]  [ 1 1 1 1 2 ]   2
[ 3]  [ 1 1 1 3 ]   3
[ 4]  [ 1 1 2 2 ]   2
[ 5]  [ 1 1 4 ]   4
[ 6]  [ 1 2 3 ]   6  (max, with a part =2)
[ 7]  [ 1 5 ]   5
[ 8]  [ 2 2 2 ]   2
[ 9]  [ 2 4 ]   4
[10]  [ 3 3 ]   3
[11]  [ 6 ]   6  (max, without a part =2)
The largest order 6 is obtained twice, the first such partition is forbidden for this sequence, but not the second, so a(6) = A000793(6) = 6.
The 7 partitions (including those with parts =2) of 5 are the following:
[ #]  [ partition ]   LCM( parts )
[ 1]  [ 1 1 1 1 1 ]   1
[ 2]  [ 1 1 1 2 ]   2
[ 3]  [ 1 1 3 ]   3
[ 4]  [ 1 2 2 ]   2
[ 5]  [ 1 4 ]   4
[ 6]  [ 2 3 ]   6 (max with a part =2)
[ 7]  [ 5 ]   5  (max, without a part =2)
The largest order (A000793(5)=6) with a part =2 is obtained with the partition into distinct primes; the largest order without a part =2 is a(5)=5.

Joerg Arndt, Table of n, a(n) for n = 0..101

a(n) = A000793(n) unless n is a term of A007504 (sum of first primes).

A217990 Size of largest semigroup generated by one Boolean n X n matrix.

Original entry on oeis.org

1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145, 170, 197, 226, 257, 290, 420

Offset: 1

Jeffrey Shallit, Oct 17 2012

			a(4) = 10: the matrix [[0,0,0,1], [0,0,1,0], [1,0,0,0], [0,1,1,0]] generates a semigroup of order 10 under Boolean matrix multiplication.

J. Denes, K. H. Kim, and F. W. Roush, Automata on one symbol, in Studies in Pure Mathematics: To the Memory of Paul Turan, Birkhäuser, 1983, pp. 127-134.

George Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum 13 (1977), 253-259.

Cf. A000793, A202140.

For n < 19, a(n) = n^2 - 2n + 2. For large n, l(n) <= a(n) < n^2 - 2n + 2 + l(n), where l(n) is Landau's function (A000793). It seems the exact value is still unknown.

cp's OEIS Frontend

A289386 Number of rounds of 'deal one, skip one' shuffling required to return a deck of n cards to its original order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Maple

Mathematica

PARI

PARI

A074103 a(n) = n!/A074859(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A074260 Number of labeled cyclic subgroups of S_n having the maximum possible order.

Views

Author

Keywords

Links

Crossrefs

Formula

A181949 Weighted sum of all cyclic subgroups of the Symmetric Group.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A225725 Triangle of transformation semigroup sizes generated by a single element.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Ruby

Extensions

A382780 Sum of the orders of all permutations of [n] with distinct cycle lengths.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A002497 Numbers N in A002809 such that there is rho > 0 such that for all A > 0, A008475(A)-A008475(N) >= rho*log(A/N).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A005417 Maximal period of an n-stage shift register.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica