|
|
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
|
|
|
FORMULA
|
Landau: lim_{n->oo} (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 + ...
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
|
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( 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)))))):
|
|
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,
);
1;
(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
(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))))))))
(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)]
(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
(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
(Sage)
def a(n):
return max([lcm(l) for l in Partitions(n)])
|
|
CROSSREFS
|
Cf. A000792, A009490, A034891, A057731, A074859, A128305, A129759, A225655, A225648-A225650, A225651, A225636, A225558.
|
|
KEYWORD
|
nonn,core,easy,nice,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
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
|
|
|
|