|
| |
|
|
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
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 *)
|
|
|
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 A206398 A123131 * 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
|
| |
|
|
