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

 

Logo


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

An easy lower bound is a(n) >= A002110(max{ m | A007504(m) <= n}), with strict inequality if n is not in A007504 (sum of the first m primes). Indeed, if A007504(m) <= n, the partition of n into the first m primes and maybe one additional term will have an LCM greater than or equal to primorial(m). If n > A007504(m) then a(n) >= 3/2 A002110(m) by replacing the initial 2 by 3. But even for n = A007504(m), one has a(n) > A002110(m) for m > 8, since replacing 2+23 in 2+3+5+7+11+13+17+19+23 by 16+9, one has an LCM of 8*3*primorial(8) > primorial(9) because 24 > 23. - M. F. Hasler, Mar 29 2015

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)

Massias, Jean-Pierre; Nicolas, Jean-Louis; Robin, Guy. Effective bounds for the maximal order of an element in the symmetric group. Math. Comp. 53 (1989), no. 188, 665--678. MR0979940 (90e:11139)

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 Deléglise, Jean-Louis Nicolas, and Paul Zimmermann, Landau's function for one million billions, arXiv:0803.2160 [math.NT], 2008.

Marc Deléglise and Jean-Louis Nicolas, On the Largest Product of Primes with Bounded Sum, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.8.

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

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

A. Wechsler, Re: Question (A000793(A007504(n)) =? A002110(n)), SeqFan mailing list, Mar 29 2015.

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

G.f. = 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.

(Haskell)

a000793 = maximum . map (foldl lcm 1) . partitions where

   partitions n = ps 1 n where

      ps x 0 = [[]]

      ps x y = [t:ts | t <- [x..y], ts <- ps t (y - t)]

-- Reinhard Zumkeller, Mar 29 2015

(PARI) c=0; A793=apply(t->eval(concat(Vec(t)[#Str(c++) .. -1])), select(t->#t, readstr("/tmp/b000793.txt"))); A000793(n)=A793[n+1] \\ Assumes the b-file in the /tmp (or C:\tmp) folder. - M. F. Hasler, Mar 29 2015

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 * A252650 A062163 A002729

Adjacent sequences:  A000790 A000791 A000792 * A000794 A000795 A000796

KEYWORD

nonn,core,easy,nice,changed

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 April 25 01:02 EDT 2015. Contains 257065 sequences.