login
The OEIS is supported by the many generous donors 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)
78
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
Maximum degree of the splitting field of a polynomial of degree n over a finite field, since over a finite field the degree of the splitting field is the least common multiple of the degrees of the irreducible polynomial factors of the polynomial. - Charles R Greathouse IV, Apr 27 2015
Maximum order of the elements in the symmetric group S_n. - Jianing Song, Dec 12 2021
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.
Edmund Georg Hermann Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea Publishing, NY 1953, p. 223.
J.-L. Nicolas, On Landau's function g(n), pp. 228-240 of R. L. Graham et al., eds., Mathematics of Paul Erdős 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
Alois P. Heinz, Table of n, a(n) for n = 0..10000 (terms n = 0..814 from David Wasserman)
Jan Brandts and A. Cihangir, Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group, arXiv preprint arXiv:1512.03044 [math.CO], 2015.
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.
Marc Deléglise and Jean-Louis Nicolas, The Landau function and the Riemann hypothesis, Univ. Lyon (France, 2019).
John D. Dixon and Daniel Panario, The Degree of the Splitting Field of a Random Polynomial over a Finite Field, The Electronic Journal of Combinatorics 11:1 (2004).
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. Kuzmanovich and A. Pavlichenkov, Finite groups of matrices whose entries are integers, Amer. Math. Monthly, 109 (2002), 173-186.
Jean-Pierre Massias, 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).
Jean-Pierre Massias, Jean-Louis Nicolas, and Guy Robin, 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.
Jean-Louis Nicolas, Sur l'ordre maximum d'un élément dans le groupe Sn des permutations, Acta Arith. 14, 315-332 (1968).
Jean-Louis Nicolas, Ordre maximal d'un élément du groupe S_n des permutations et 'highly composite numbers', Bull. Soc. Math. France 97 (1969), 129-191.
Jean-Louis Nicolas, Calcul de l'ordre maximum d'un élément du groupe symétrique S_n Revue française d'informatique et de recherche opérationnelle, série rouge 3.2 (1969): 43-50.
Jean-Louis Nicolas, Ordre maximal d'un e'le'ment du'un groupe de permutations, C. R. Acad. Sci. Paris, A, 270 (1970), 1-4. [Annotated scanned copy]
Roger D. Nussbaum, Lunel Verduyn, and M. Sjoerd, Asymptotic estimates for the periods of periodic points of non-expansive maps, Ergodic Theory Dynam. Systems 23 (2003), no. 4, pp. 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
Herbert S. Wilf, The asymptotics of e^P(z) and the number of elements of each order in S_n, Bull. Amer. Math. Soc., 15.2 (1986), 225-232.
FORMULA
Landau: lim_{n->oo} (log a(n)) / sqrt(n log n) = 1.
For bounds, see the Shah and Massias references.
For n >= 2, a(n) = max_{k} A008475(k) <= n. - Joerg Arndt, Nov 13 2016
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
A000793 := proc(n)
l := 1:
p := combinat[partition](n):
for i from 1 to combinat[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]))
end if:
end do:
l ;
end proc:
seq(A000793(n), n=0..30) ; # 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) = my(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 */
(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
(PARI) A008475(n)=my(f=factor(n)); sum(i=1, #f~, f[i, 1]^f[i, 2]);
a(n)=
{
if(n<2, return(1));
forstep(i=ceil(exp(1.05315*sqrt(log(n)*n))), 2, -1,
if(A008475(i)<=n, return(i))
);
1;
} \\ Charles R Greathouse IV, Apr 28 2015
(PARI)
{ \\ translated from code given by Tomas Rokicki
my( N = 100 );
my( V = vector(N, j, 1) );
forprime (i=2, N, \\ primes i
forstep (j=N, i, -1,
my( hi = V[j] );
my( pp = i ); \\ powers of prime i
while ( pp<=j, \\ V[] is 1-based
hi = max(if(j==pp, pp, V[j-pp]*pp), hi);
pp *= i;
);
V[j] = hi;
);
);
print( V ); \\ all values
\\ print( V[N] ); \\ just a(N)
\\ print("0 1"); for (n=1, N, print(n, " ", V[n]) ); \\ b-file
} \\ Joerg Arndt, Nov 14 2016
(PARI) {a(n) = my(m=1); if( n<0, 0, forpart(v=n, m = max(m, lcm(Vec(v)))); m)}; /* Michael Somos, Sep 04 2017 */
(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
(Python)
from sympy import primerange
def aupton(N): # compute terms a(0)..a(N)
V = [1 for j in range(N+1)]
for i in primerange(2, N+1):
for j in range(N, i-1, -1):
hi = V[j]
pp = i
while pp <= j:
hi = max((pp if j==pp else V[j-pp]*pp), hi)
pp *= i
V[j] = hi
return V
print(aupton(47)) # Michael S. Branicky, Oct 09 2022 after Joerg Arndt
(Python)
from sympy import primerange, sqrt, log, Rational
def f(N): # compute terms a(0)..a(N)
V = [1 for j in range(N+1)]
if N < 4:
C = 2
else:
C = Rational(166, 125)
for i in primerange(C*sqrt(N*log(N))):
for j in range(N, i-1, -1):
hi = V[j]
pp = i
while pp <= j:
hi = max(V[j-pp]*pp, hi)
pp *= i
V[j] = hi
return V
# Philip Turecek, Mar 31 2023
(Sage)
def a(n):
return max([lcm(l) for l in Partitions(n)])
# Philip Turecek, Mar 28 2023
CROSSREFS
Row 1 of A225630.
Sequence in context: A340267 A123131 A206398 * A252650 A265548 A062163
KEYWORD
nonn,core,easy,nice
AUTHOR
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 | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)