|
%I M0537 N0190 #209 Mar 21 2024 15:33:59
%S 1,1,2,3,4,6,6,12,15,20,30,30,60,60,84,105,140,210,210,420,420,420,
%T 420,840,840,1260,1260,1540,2310,2520,4620,4620,5460,5460,9240,9240,
%U 13860,13860,16380,16380,27720,30030,32760,60060,60060,60060,60060,120120
%N Landau's function g(n): largest order of permutation of n elements. Equivalently, largest LCM of partitions of n.
%C 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
%C Grantham mentions that he computed a(n) for n <= 500000.
%C 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
%C 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
%C Maximum order of the elements in the symmetric group S_n. - _Jianing Song_, Dec 12 2021
%D 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.
%D Edmund Georg Hermann Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea Publishing, NY 1953, p. 223.
%D 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.
%D 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.]
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A000793/b000793.txt">Table of n, a(n) for n = 0..10000</a> (terms n = 0..814 from David Wasserman)
%H Giedrius Alkauskas, <a href="https://www.researchgate.net/publication/367461888_Colouring_monohedral_tilings_defects_and_grain_boundaries">Colouring monohedral tilings: defects and grain boundaries</a>, 2024.
%H Joerg Arndt, <a href="/A000793/b000793.txt.xz">Table of n, a(n) for n = 0..65536 (xz compressed)</a>.
%H Jan Brandts and A. Cihangir, <a href="http://arxiv.org/abs/1512.03044">Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group</a>, arXiv preprint arXiv:1512.03044 [math.CO], 2015.
%H Marc Deléglise, Jean-Louis Nicolas, and Paul Zimmermann, <a href="http://arxiv.org/abs/0803.2160">Landau's function for one million billions</a>, arXiv:0803.2160 [math.NT], 2008.
%H Marc Deléglise and Jean-Louis Nicolas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Deleglise/deleglise3.html">On the Largest Product of Primes with Bounded Sum</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.8.
%H Marc Deléglise and Jean-Louis Nicolas, <a href="https://hal.archives-ouvertes.fr/hal-02177338/">The Landau function and the Riemann hypothesis</a>, Univ. Lyon (France, 2019).
%H John D. Dixon and Daniel Panario, <a href="https://doi.org/10.37236/1823">The Degree of the Splitting Field of a Random Polynomial over a Finite Field</a>, The Electronic Journal of Combinatorics 11:1 (2004).
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000058/">The order of a permutation</a>
%H Jon Grantham, <a href="http://dx.doi.org/10.1090/S0025-5718-1995-1270619-3">The largest prime dividing the maximal order of an element of S_n</a>, Math. Comput. 64, No. 209, 407-410 (1995).
%H Joel K. Haack, <a href="http://archive.bridgesmathart.org/1998/bridges1998-87.pdf">The Mathematics of Steve Reich's Clapping Music</a>,in Bridges: Mathematical Connections in Art, Music and Science: Conference Proceedings, 1998, Reza Sarhangi (ed.), 87-92.
%H J. Kuzmanovich and A. Pavlichenkov, <a href="http://www.jstor.org/stable/2695329">Finite groups of matrices whose entries are integers</a>, Amer. Math. Monthly, 109 (2002), 173-186.
%H Jean-Pierre Massias, <a href="http://www.numdam.org/item/AFST_1984_5_6_3-4_269_0/">Majoration explicite de l'ordre maximum d'un élément du groupe symétrique</a>, (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).
%H Jean-Pierre Massias, Jean-Louis Nicolas, and Guy Robin, <a href="https://doi.org/10.1090/S0025-5718-1989-0979940-4">Effective bounds for the maximal order of an element in the symmetric group</a>, Math. Comp. 53 (1989), no. 188, 665--678. MR0979940 (90e:11139).
%H W. Miller, <a href="http://www.jstor.org/stable/2322839">The Maximum Order of an Element of Finite Symmetric Group</a>, Am. Math. Monthly, Jun-Jul 1987, pp. 497-506.
%H Jean-Louis Nicolas, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa14/aa1420.pdf">Sur l'ordre maximum d'un élément dans le groupe Sn des permutations</a>, Acta Arith. 14, 315-332 (1968).
%H Jean-Louis Nicolas, <a href="https://doi.org/10.24033/bsmf.1676">Ordre maximal d'un élément du groupe S_n des permutations et 'highly composite numbers'</a>, Bull. Soc. Math. France 97 (1969), 129-191.
%H Jean-Louis Nicolas, <a href="http://archive.numdam.org/item/M2AN_1969__3_2_43_0/">Calcul de l'ordre maximum d'un élément du groupe symétrique S_n</a> Revue française d'informatique et de recherche opérationnelle, série rouge 3.2 (1969): 43-50.
%H Jean-Louis Nicolas, <a href="/A000793/a000793.pdf">Ordre maximal d'un e'le'ment du'un groupe de permutations</a>, C. R. Acad. Sci. Paris, A, 270 (1970), 1-4. [Annotated scanned copy]
%H Roger D. Nussbaum, Lunel Verduyn, and M. Sjoerd, <a href="http://www.math.rutgers.edu/~nussbaum/Pubs/nusslunel2003.pdf">Asymptotic estimates for the periods of periodic points of non-expansive maps</a>, Ergodic Theory Dynam. Systems 23 (2003), no. 4, pp. 1199-1226. MR1997973 (2004m:37033).
%H S. M. Shah, <a href="/A000793/a000793.jpg">An inequality for the arithmetical function g(x)</a> (scan of first page).
%H A. Wechsler, <a href="http://list.seqfan.eu/oldermail/seqfan/2015-March/014635.html">Re: Question (A000793(A007504(n)) =? A002110(n))</a>, SeqFan mailing list, Mar 29 2015.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LandausFunction.html">Landau's Function</a>
%H Herbert S. Wilf, <a href="https://doi.org/10.1090/S0273-0979-1986-15486-8">The asymptotics of e^P(z) and the number of elements of each order in S_n</a>, Bull. Amer. Math. Soc., 15.2 (1986), 225-232.
%H <a href="/index/Lc#lcm">Index entries for sequences related to lcm's</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F Landau: lim_{n->oo} (log a(n)) / sqrt(n log n) = 1.
%F For bounds, see the Shah and Massias references.
%F For n >= 2, a(n) = max_{k} A008475(k) <= n. - _Joerg Arndt_, Nov 13 2016
%e 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 + ...
%e From _Joerg Arndt_, Feb 15 2013: (Start)
%e The 15 partitions of 7 are the following:
%e [ #] [ partition ] lcm( parts )
%e [ 1] [ 1 1 1 1 1 1 1 ] 1
%e [ 2] [ 1 1 1 1 1 2 ] 2
%e [ 3] [ 1 1 1 1 3 ] 3
%e [ 4] [ 1 1 1 2 2 ] 2
%e [ 5] [ 1 1 1 4 ] 4
%e [ 6] [ 1 1 2 3 ] 6
%e [ 7] [ 1 1 5 ] 5
%e [ 8] [ 1 2 2 2 ] 2
%e [ 9] [ 1 2 4 ] 4
%e [10] [ 1 3 3 ] 3
%e [11] [ 1 6 ] 6
%e [12] [ 2 2 3 ] 6
%e [13] [ 2 5 ] 10
%e [14] [ 3 4 ] 12 (max)
%e [15] [ 7 ] 7
%e The maximum (LCM) value attained is 12, so a(7) = 12.
%e (End)
%p A000793 := proc(n)
%p l := 1:
%p p := combinat[partition](n):
%p for i from 1 to combinat[numbpart](n) do
%p if ilcm( p[i][j] $ j=1..nops(p[i])) > l then
%p l := ilcm( p[i][j] $ j=1..nops(p[i]))
%p end if:
%p end do:
%p l ;
%p end proc:
%p seq(A000793(n),n=0..30) ; # _James A. Sellers_, Dec 07 2000
%p seq( max( op( map( x->ilcm(op(x)), combinat[partition](n)))), n=0..30); # _David Radcliffe_, Feb 28 2006
%p # third Maple program:
%p b:= proc(n, i) option remember; local p;
%p p:= `if`(i<1, 1, ithprime(i));
%p `if`(n=0 or i<1, 1, max(b(n, i-1),
%p seq(p^j*b(n-p^j, i-1), j=1..ilog[p](n))))
%p end:
%p a:=n->b(n, `if`(n<8, 3, numtheory[pi](ceil(1.328*isqrt(n*ilog(n)))))):
%p seq(a(n), n=0..60); # _Alois P. Heinz_, Feb 16 2013
%t f[n_] := Max@ Apply[LCM, IntegerPartitions@ n, 1]; Array[f, 47] (* _Robert G. Wilson v_, Oct 23 2011 *)
%t 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_ *)
%o (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 */
%o (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
%o (PARI) A008475(n)=my(f=factor(n)); sum(i=1,#f~,f[i,1]^f[i,2]);
%o a(n)=
%o {
%o if(n<2, return(1));
%o forstep(i=ceil(exp(1.05315*sqrt(log(n)*n))), 2, -1,
%o if(A008475(i)<=n, return(i))
%o );
%o 1;
%o } \\ _Charles R Greathouse IV_, Apr 28 2015
%o (PARI)
%o { \\ translated from code given by Tomas Rokicki
%o my( N = 100 );
%o my( V = vector(N,j,1) );
%o forprime (i=2, N, \\ primes i
%o forstep (j=N, i, -1,
%o my( hi = V[j] );
%o my( pp = i ); \\ powers of prime i
%o while ( pp<=j, \\ V[] is 1-based
%o hi = max(if(j==pp, pp, V[j-pp]*pp), hi);
%o pp *= i;
%o );
%o V[j] = hi;
%o );
%o );
%o print( V ); \\ all values
%o \\ print( V[N] ); \\ just a(N)
%o \\ print("0 1"); for (n=1, N, print(n, " ", V[n]) ); \\ b-file
%o } \\ _Joerg Arndt_, Nov 14 2016
%o (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 */
%o (Scheme) ;; A naive algorithm searching through all partitions of n:
%o (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)))
%o (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))))))))
%o ;; From _Antti Karttunen_, May 17 2013.
%o (Haskell)
%o a000793 = maximum . map (foldl lcm 1) . partitions where
%o partitions n = ps 1 n where
%o ps x 0 = [[]]
%o ps x y = [t:ts | t <- [x..y], ts <- ps t (y - t)]
%o -- _Reinhard Zumkeller_, Mar 29 2015
%o (Python)
%o from sympy import primerange
%o def aupton(N): # compute terms a(0)..a(N)
%o V = [1 for j in range(N+1)]
%o for i in primerange(2, N+1):
%o for j in range(N, i-1, -1):
%o hi = V[j]
%o pp = i
%o while pp <= j:
%o hi = max((pp if j==pp else V[j-pp]*pp), hi)
%o pp *= i
%o V[j] = hi
%o return V
%o print(aupton(47)) # _Michael S. Branicky_, Oct 09 2022 after _Joerg Arndt_
%o (Python)
%o from sympy import primerange,sqrt,log,Rational
%o def f(N): # compute terms a(0)..a(N)
%o V = [1 for j in range(N+1)]
%o if N < 4:
%o C = 2
%o else:
%o C = Rational(166,125)
%o for i in primerange(C*sqrt(N*log(N))):
%o for j in range(N, i-1, -1):
%o hi = V[j]
%o pp = i
%o while pp <= j:
%o hi = max(V[j-pp]*pp, hi)
%o pp *= i
%o V[j] = hi
%o return V
%o # _Philip Turecek_, Mar 31 2023
%o (Sage)
%o def a(n):
%o return max([lcm(l) for l in Partitions(n)])
%o # _Philip Turecek_, Mar 28 2023
%Y Cf. A000792, A009490, A034891, A057731, A074859, A128305, A129759, A225655, A225648-A225650, A225651, A225636, A225558.
%Y Row 1 of A225630.
%K nonn,core,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _David W. Wilson_
%E 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
| 