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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000793 Landau's function g(n): largest order of permutation of n elements. Equivalently, largest LCM of partitions of n.
(Formerly M0537 N0190)
56
1, 1, 2, 3, 4, 6, 6, 12, 15, 20, 30, 30, 60, 60, 84, 105, 140, 210, 210, 420, 420, 420, 420, 840, 840, 1260, 1260, 1540, 2310, 2520, 4620, 4620, 5460, 5460, 9240, 9240, 13860, 13860, 16380, 16380, 27720, 30030, 32760, 60060, 60060, 60060, 60060, 120120 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also the largest orbit size (cycle length) for the permutation A057511 acting on Catalan objects (e.g. planar rooted trees, parenthesizations) - Antti Karttunen, Sep 07 2000

Grantham mentions that he computed a(n) for n <= 500000.

REFERENCES

J. Haack, "The Mathematics of Steve Reich's Clapping Music," in Bridges: Mathematical Connections in Art, Music and Science: Conference Proceedings, 1998, Reza Sarhangi (ed.), 87-92.

J. Kuzmanovich and A. Pavlichenkov, Finite groups of matrices whose entries are integers, Amer. Math. Monthly, 109 (2002), 173-186.

Edmund Georg Hermann Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea Publishing, NY 1953, p. 223.

Massias, Jean-Pierre. Majoration explicite de l'ordre maximum d'un élément du groupe symétrique. (French) [Explicit upper bound on the maximum order of an element of the symmetric group] Ann. Fac. Sci. Toulouse Math. (5) 6 (1984), no. 3-4, 269--281 (1985). MR0799599 (87a:11093)

W. Miller, The Maximum Order of an Element of Finite Symmetric Group, Am. Math. Monthly, Jun-Jul 1987, pp. 497-506.

J.-L. Nicolas, Sur l'ordre maximum d'un e'le'ment dans le groupe S_n des permutations, Acta Arith., 14 (1968), 315-332.

J.-L. Nicolas, Ordre maximum d'un e'le'ment du groupe de permutations et highly composite numbers, Bull. Math. Soc. France, 97 (1969), 129-191.

J.-L. Nicolas, On Landau's function g(n), pp. 228-240 of R. L. Graham et al., eds., Mathematics of Paul Erdos I.

S. M. Shah, An inequality for the arithmetical function g(x), J. Indian Math. Soc., 3 (1939), 316-318. [See below for a scan of the first page.]

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).

LINKS

David Wasserman and Alois P. Heinz, Table of n, a(n) for n = 0..10000 (terms n = 0..814 from David Wasserman)

Marc Deleglise, Jean-Louis Nicolas, and Paul Zimmermann, Landau’s function for one million billions

FindStat - Combinatorial Statistic Finder, The order of a permutation

Jon Grantham, The largest prime dividing the maximal order of an element of S_n, Math. Comput. 64, No. 209, 407-410 (1995).

J.-L. Nicolas, Sur l'ordre maximum d'un element dans le groupe Sn des permutations, Acta Arith. 14, 315-332 (1968).

J.-L. Nicolas, Ordre maximal d'un element du groupe S_n des permutations et 'highly composite numbers', Bull. Soc. Math. France 97 (1969), 129-191.

Nussbaum, Roger D.; Verduyn Lunel, Sjoerd M., Asymptotic estimates for the periods of periodic points of non-expansive maps, Ergodic Theory Dynam. Systems 23 (2003), no. 4, 1199--1226. MR1997973 (2004m:37033).

S. M. Shah, An inequality for the arithmetical function g(x) (scan of first page)

Eric Weisstein's World of Mathematics, Landau's Function

Index entries for sequences related to lcm's

Index entries for "core" sequences

FORMULA

Landau: lim_{n->infinity} (log a(n)) / sqrt(n log n) = 1.

For bounds, see the Shah and Massias references.

EXAMPLE

1 + x + 2*x^2 + 3*x^3 + 4*x^4 + 6*x^5 + 6*x^6 + 12*x^7 + 15*x^8 + ...

From Joerg Arndt, Feb 15 2013: (Start)

The 15 partitions of 7 are the following:

[ #]  [ partition ]   LCM( parts )

[ 1]  [ 1 1 1 1 1 1 1 ]   1

[ 2]  [ 1 1 1 1 1 2 ]   2

[ 3]  [ 1 1 1 1 3 ]   3

[ 4]  [ 1 1 1 2 2 ]   2

[ 5]  [ 1 1 1 4 ]   4

[ 6]  [ 1 1 2 3 ]   6

[ 7]  [ 1 1 5 ]   5

[ 8]  [ 1 2 2 2 ]   2

[ 9]  [ 1 2 4 ]   4

[10]  [ 1 3 3 ]   3

[11]  [ 1 6 ]   6

[12]  [ 2 2 3 ]   6

[13]  [ 2 5 ]  10

[14]  [ 3 4 ]  12  (max)

[15]  [ 7 ]   7

The maximum (LCM) value attained is 12, so a(7) = 12.

(End)

MAPLE

with(combinat): for n from 0 to 30 do l := 1: p := partition(n): for i from 1 to numbpart(n) do if ilcm( p[i][j] $ j=1..nops(p[i])) > l then l := ilcm( p[i][j] $ j=1..nops(p[i])) fi: od: printf(`%d, `, l): od: # James A. Sellers, Dec 07 2000

seq( max( op( map( x->ilcm(op(x)), combinat[partition](n)))), n=0..30); # David Radcliffe, Feb 28 2006

# third Maple program:

b:= proc(n, i) option remember; local p;

      p:= `if`(i<1, 1, ithprime(i));

      `if`(n=0 or i<1, 1, max(b(n, i-1),

           seq(p^j*b(n-p^j, i-1), j=1..ilog[p](n))))

    end:

a:=n->b(n, `if`(n<8, 3, numtheory[pi](ceil(1.328*isqrt(n*ilog(n)))))):

seq(a(n), n=0..60);  # Alois P. Heinz, Feb 16 2013

MATHEMATICA

f[n_] := Max@ Apply[LCM, IntegerPartitions@ n, 1]; Array[f, 47] (* Robert G. Wilson v, Oct 23 2011 *)

b[n_, i_] := b[n, i] = Module[{p}, p = If[i<1, 1, Prime[i]]; If[n == 0 || i<1, 1, Max[b[n, i-1], Table[p^j*b[n-p^j, i-1], {j, 1, Log[p, n] // Floor}]]]]; a[n_] := b[n, If[n<8, 3, PrimePi[Ceiling[1.328*Sqrt[n*Log[n] // Floor]]]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Mar 07 2014, after Alois P. Heinz *)

PROG

(PARI) {a(n) = local(m, t, j, u); if( n<2, n>=0, m = ceil(n / exp(1)); t = ceil( (n/m)^m ); j=1; for( i=2, t, u = factor(i); u = sum( k=1, matsize(u)[1], u[k, 1]^u[k, 2]); if( u<=n, j=i)); j)} /* Michael Somos, Oct 20 2004 */

(Scheme) ;; A naive algorithm searching through all partitions of n:

(define (A000793 n) (let ((maxlcm (list 0))) (fold_over_partitions_of n 1 lcm (lambda (p) (set-car! maxlcm (max (car maxlcm) p)))) (car maxlcm)))

(define (fold_over_partitions_of m initval addpartfun colfun) (let recurse ((m m) (b m) (n 0) (partition initval)) (cond ((zero? m) (colfun partition)) (else (let loop ((i 1)) (recurse (- m i) i (+ 1 n) (addpartfun i partition)) (if (< i (min b m)) (loop (+ 1 i))))))))

;; From Antti Karttunen, May 17 2013.

CROSSREFS

Cf. A000792, A009490, A034891, A074859, A128305, A129759, A225655.

Row 1 of A225630. Cf. also A225648-A225650, A225651, A225636, A225558.

Sequence in context: A064764 A123131 A206398 * A062163 A002729 A030209

Adjacent sequences:  A000790 A000791 A000792 * A000794 A000795 A000796

KEYWORD

nonn,core,easy,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from David W. Wilson.

Removed erroneous comment about a(16) which probably originated from misreading a(15)=105 as a(16) because of offset=0: a(16)=4*5*7=140 is correct as it stands. - M. F. Hasler, Feb 02 2009

STATUS

approved

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

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

Last modified December 18 04:21 EST 2014. Contains 252079 sequences.