A034891 -id:A034891 - cp's OEIS frontend

A000792 a(n) = max{(n - i)*a(i) : i < n}; a(0) = 1.

1, 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324, 486, 729, 972, 1458, 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244, 39366, 59049, 78732, 118098, 177147, 236196, 354294, 531441, 708588, 1062882, 1594323, 2125764, 3188646, 4782969, 6377292

Offset: 0

N. J. A. Sloane

Numbers of the form 3^k, 2*3^k, 4*3^k with a(0) = 1 prepended.
If a set of positive numbers has sum n, this is the largest value of their product.
In other words, maximum of products of partitions of n: maximal value of Product k_i for any way of writing n = Sum k_i. To find the answer, take as many of the k_i's as possible to be 3 and then use one or two 2's (see formula lines below).
a(n) is also the maximal size of an Abelian subgroup of the symmetric group S_n. For example, when n = 6, one of the Abelian subgroups with maximal size is the subgroup generated by (123) and (456), which has order 9. [Bercov and Moser] - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 19 2001
Also the maximum number of maximal cliques possible in a graph with n vertices (cf. Capobianco and Molluzzo). - Felix Goldberg (felixg(AT)tx.technion.ac.il), Jul 15 2001 [Corrected by Jim Nastos and Tanya Khovanova, Mar 11 2009]
Every triple of alternate terms {3*k, 3*k+2, 3*k+4} in the sequence forms a geometric progression with first term 3^k and common ratio 2. - Lekraj Beedassy, Mar 28 2002
For n > 4, a(n) is the least multiple m of 3 not divisible by 8 for which omega(m) <= 2 and sopfr(m) = n. - Lekraj Beedassy, Apr 24 2003
Maximal number of divisors that are possible among numbers m such that A080256(m) = n. - Lekraj Beedassy, Oct 13 2003
Or, numbers of the form 2^p*3^q with p <= 2, q >= 0 and 2p + 3q = n. Largest number obtained using only the operations +,* and () on the parts 1 and 2 of any partition of n into these two summands where the former exceeds the latter. - Lekraj Beedassy, Jan 07 2005
a(n) is the largest number of complexity n in the sense of A005520 (A005245). - David W. Wilson, Oct 03 2005
a(n) corresponds also to the ultimate occurrence of n in A001414 and thus stands for the highest number m such that sopfr(m) = n, for n >= 2. - Lekraj Beedassy, Apr 29 2002
a(n) for n >= 1 is a paradigm shift sequence with procedural length p = 0, in the sense of A193455. - Jonathan T. Rowell, Jul 26 2011
a(n) = largest term of n-th row in A212721. - Reinhard Zumkeller, Jun 14 2012
For n >= 2, a(n) is the largest number whose prime divisors (with multiplicity) add to n, whereas the smallest such number (resp. smallest composite number) is A056240(n) (resp. A288814(n)). - David James Sycamore, Nov 23 2017
For n >= 3, a(n+1) = a(n)*(1 + 1/s), where s is the smallest prime factor of a(n). - David James Sycamore, Apr 10 2018

			a{8} = 18 because we have 18 = (8-5)*a(5) = 3*6 and one can verify that this is the maximum.
a(5) = 6: the 7 partitions of 5 are (5), (4, 1), (3, 2), (3, 1, 1), (2, 2, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1) and the corresponding products are 5, 4, 6, 3, 4, 2 and 1; 6 is the largest.
G.f. = 1 + x + 2*x^2 + 3*x^3 + 4*x^4 + 6*x^5 + 9*x^6 + 12*x^7 + 18*x^8 + ...

B. R. Barwell, Cutting String and Arranging Counters, J. Rec. Math., 4 (1971), 164-168.
B. R. Barwell, Journal of Recreational Mathematics, "Maximum Product": Solution to Prob. 2004;25(4) 1993, Baywood, NY.
M. Capobianco and J. C. Molluzzo, Examples and Counterexamples in Graph Theory, p. 207. North-Holland: 1978.
S. L. Greitzer, International Mathematical Olympiads 1959-1977, Prob. 1976/4 pp. 18;182-3 NML vol. 27 MAA 1978
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 396.
P. R. Halmos, Problems for Mathematicians Young and Old, Math. Assoc. Amer., 1991, pp. 30-31 and 188.
L. C. Larson, Problem-Solving Through Problems. Problem 1.1.4 pp. 7. Springer-Verlag 1983.
D. J. Newman, A Problem Seminar. Problem 15 pp. 5;15. Springer-Verlag 1982.
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).

T. D. Noe, Table of n, a(n) for n = 0..500
R. Bercov and L. Moser, On Abelian permutation groups, Canad. Math. Bull. 8 (1965) 627-630.
Walter Bridges and William Craig, On the distribution of the norm of partitions, arXiv:2308.00123 [math.CO], 2023.
J. Arias de Reyna and J. van de Lune, The question "How many 1's are needed?" revisited, arXiv preprint arXiv:1404.1850 [math.NT], 2014. See M_n.
J. Arias de Reyna and J. van de Lune, Algorithms for determining integer complexity, arXiv preprint arXiv:1404.2183 [math.NT], 2014.
Nigel Derby, 96.21 The MaxProduct partition, The Mathematical Gazette 96:535 (2012), pp. 148-151.
Tomislav Doslic, Maximum Product Over Partitions Into Distinct Parts, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.8.
Hans Havermann, Tables of sum-of-prime-factors sequences (overview with links to the first 50000 sums).
J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results, arXiv preprint arXiv:1203.6462 [math.NT], 2012.
Andrew Kenney and Caroline Shapcott, Maximum Part-Products of Odd Palindromic Compositions, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.6.
E. F. Krause, Maximizing The Product of Summands, Mathematics Magazine, MAA Oct 1996, Vol. 69, no. 5 pp. 270-271.
MathPro, 20000 Problems Under the Sea, Problem 14856.Putnam 1979/A1.
J. W. Moon and L. Moser, On cliques in graphs, Israel J. Math. 3 (1965), 23-28.
Natasha Morrison and Alex Scott, Maximizing the number of induced cycles in a graph, Preprint, 2016. See f_2(n).
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
F. Pluvinage, Developing problem solving experiences in practical action projects, The Mathematics Enthusiast, ISSN 1551-3440, Vol. 10, nos. 1 & 2, pp. 219-244.
D. A. Rawsthorne, How many 1's are needed?, Fib. Quart. 27 (1989), 14-17.
J. T. Rowell, Solution Sequences for the Keyboard Problem and its Generalizations, Journal of Integer Sequences, 18 (2015), #15.10.7.
Robert Schneider and Andrew V. Sills, The Product of Parts or "Norm" of a Partition, Integers (2020) Vol. 20A, Article #A13.
J. Scholes, 40th Putnam 1979 Problem A1.
J. Scholes, 18th IMO 1976 Problem 4.
Andrew V. Sills and Robert Schneider, The product of parts or "norm" of a partition, arXiv:1904.08004 [math.NT], 2019.
V. Vatter, Maximal independent sets and separating covers, Amer. Math. Monthly, 118 (2011), 418-423.
Robert G. Wilson v, Letter to N. J. Sloane, circa 1991.
A. C.-C. Yao, On a problem of Katona on minimal separating systems, Discrete Math., 15 (1976), 193-199.
Index to sequences related to the complexity of n
Index entries for linear recurrences with constant coefficients, signature (0,0,3).

See A007600 for a left inverse.
Cf. A000793, A009490, A034891, A062943, A007601, A062723, A069188, A087902.
Cf. array A064364, rightmost (nonvanishing) numbers in row n >= 2.
See A056240 and A288814 for the minimal numbers whose prime factors sums up to n.
A000792, A178715, A193286, A193455, A193456, and A193457 are closely related as paradigm shift sequences for (p = 0, ..., 5 respectively).
Cf. A202337 (subsequence).
Cf. A038754, A005245, A005520.

a000792 n = a000792_list !! n
a000792_list = 1 : f [1] where
   f xs = y : f (y:xs) where y = maximum $ zipWith (*) [1..] xs
-- Reinhard Zumkeller, Dec 17 2011

I:=[1,1,2,3,4]; [n le 5 select I[n] else 3*Self(n-3): n in [1..45]]; // Vincenzo Librandi, Apr 14 2015

A000792 := proc(n)
    m := floor(n/3) ;
    if n mod 3 = 0 then
        3^m ;
    elif n mod 3 = 1 then
        4*3^(m-1) ;
    else
        2*3^m ;
    end if;
    floor(%) ;
end proc: # R. J. Mathar, May 26 2013

a[1] = 1; a[n_] := 4* 3^(1/3 *(n - 1) - 1) /; (Mod[n, 3] == 1 && n > 1); a[n_] := 2*3^(1/3*(n - 2)) /; Mod[n, 3] == 2; a[n_] := 3^(n/3) /; Mod[n, 3] == 0; Table[a[n], {n, 0, 40}]
CoefficientList[Series[(1 + x + 2x^2 + x^4)/(1 - 3x^3), {x, 0, 50}], x] (* Harvey P. Dale, May 01 2011 *)
f[n_] := Max[ Times @@@ IntegerPartitions[n, All, Prime@ Range@ PrimePi@ n]]; f[1] = 1; Array[f, 43, 0] (* Robert G. Wilson v, Jul 31 2012 *)
a[ n_] := If[ n < 2, Boole[ n > -1], 2^Mod[-n, 3] 3^(Quotient[ n - 1, 3] + Mod[n - 1, 3] - 1)]; (* Michael Somos, Jan 23 2014 *)
Join[{1, 1}, LinearRecurrence[{0, 0, 3}, {2, 3, 4}, 50]] (* Jean-François Alcover, Jan 08 2019 *)
Join[{1,1},NestList[#+Divisors[#][[-2]]&,2,41]] (* James C. McMahon, Aug 09 2024 *)

{a(n) = floor( 3^(n - 4 - (n - 4) \ 3 * 2) * 2^( -n%3))}; /* Michael Somos, Jul 23 2002 */

lista(nn) = {print1("1, 1, "); print1(a=2, ", "); for (n=1, nn, a += a/divisors(a)[2]; print1(a, ", "););} \\ Michel Marcus, Apr 14 2015

A000792(n)=if(n>1,3^((n-2)\3)*(2+(n-2)%3),1) \\ M. F. Hasler, Jan 19 2019

G.f.: (1 + x + 2*x^2 + x^4)/(1 - 3*x^3). - Simon Plouffe in his 1992 dissertation.
a(3n) = 3^n; a(3*n+1) = 4*3^(n-1) for n > 0; a(3*n+2) = 2*3^n.
a(n) = 3*a(n-3) if n > 4. - Henry Bottomley, Nov 29 2001
a(n) = n if n <= 2, otherwise a(n-1) + Max{gcd(a(i), a(j)) | 0 < i < j < n}. - Reinhard Zumkeller, Feb 08 2002
A007600(a(n)) = n; Andrew Chi-Chih Yao attributes this observation to D. E. Muller. - Vincent Vatter, Apr 24 2006
a(n) = 3^(n - 2 - 2*floor((n - 1)/3))*2^(2 - (n - 1) mod 3) for n > 1. - Hieronymus Fischer, Nov 11 2007
From Kiyoshi Akima (k_akima(AT)hotmail.com), Aug 31 2009: (Start)
a(n) = 3^floor(n/3)/(1 - (n mod 3)/4), n > 1.
a(n) = 3^(floor((n - 2)/3))*(2 + ((n - 2) mod 3)), n > 1. (End)
a(n) = (2^b)*3^(C - (b + d))*(4^d), n > 1, where C = floor((n + 1)/3), b = max(0, ((n + 1) mod 3) - 1), d = max(0, 1 - ((n + 1) mod 3)). - Jonathan T. Rowell, Jul 26 2011
G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 - x / (1 + x / (1 + x^2 / (1 + x))))))). - Michael Somos, May 12 2012
3*a(n) = 2*a(n+1) if n > 1 and n is not divisible by 3. - Michael Somos, Jan 23 2014
a(n) = a(n-1) + largest proper divisor of a(n-1), n > 2. - Ivan Neretin, Apr 13 2015
a(n) = max{a(i)*a(n-i) : 0 < i < n} for n >= 4. - Jianing Song, Feb 15 2020
a(n+1) = a(n) + A038754(floor( (2*(n-1) + 1)/3 )), for n > 1. - Thomas Scheuerle, Oct 27 2022

More terms and better description from Therese Biedl (biedl(AT)uwaterloo.ca), Jan 19 2000

A000793 Landau's function g(n): largest order of permutation of n elements. Equivalently, largest LCM of partitions of n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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

			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)

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

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (terms n = 0..814 from David Wasserman)
Giedrius Alkauskas, Colouring monohedral tilings: defects and grain boundaries, 2024.
Joerg Arndt, Table of n, a(n) for n = 0..65536 (xz compressed).
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.
Jan Elmar Krauskopf, Andreas Rauh, and Andreas Hein, Discrete simulation of maypole braiding machines to create collision-free braiding programmes, Heliyon (2025), Art. No. e42917.
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.
Index entries for sequences related to lcm's
Index entries for "core" sequences

Cf. A000792, A009490, A034891, A057731, A074859, A128305, A129759, A225655, A225648-A225650, A225651, A225636, A225558.

Row 1 of A225630.

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

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

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

{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 */

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

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

{ \\ 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

{a(n) = my(m=1); if( n<0, 0, forpart(v=n, m = max(m, lcm(Vec(v)))); m)}; /* Michael Somos, Sep 04 2017 */

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

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

def a(n):
  return max([lcm(l) for l in Partitions(n)])
# Philip Turecek, Mar 28 2023

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

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

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

A023893 Number of partitions of n into prime power parts (1 included); number of nonisomorphic Abelian subgroups of symmetric group S_n.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 10, 14, 20, 27, 36, 48, 63, 82, 105, 134, 171, 215, 269, 335, 415, 511, 626, 764, 929, 1125, 1356, 1631, 1953, 2333, 2776, 3296, 3903, 4608, 5427, 6377, 7476, 8744, 10205, 11886, 13818, 16032, 18565, 21463, 24768, 28536

Offset: 0

Olivier Gérard

nonn

			From _Gus Wiseman_, Jul 28 2022: (Start)
The a(0) = 1 through a(6) = 10 partitions:
  ()  (1)  (2)   (3)    (4)     (5)      (33)
           (11)  (21)   (22)    (32)     (42)
                 (111)  (31)    (41)     (51)
                        (211)   (221)    (222)
                        (1111)  (311)    (321)
                                (2111)   (411)
                                (11111)  (2211)
                                         (3111)
                                         (21111)
                                         (111111)
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000
Index entries for sequences related to groups

Cf. A009490, A023894 (first differences), A062297 (number of Abelian subgroups).
Cf. A018819, A062051, A131995.
The multiplicative version (factorizations) is A000688.
Not allowing 1's gives A023894, strict A054685, ranked by A355743.
The version for just primes (not prime-powers) is A034891, strict A036497.
The strict version is A106244.
These partitions are ranked by A302492.
A000041 counts partitions, strict A000009.
A001222 counts prime-power divisors.
A072233 counts partitions by sum and length.
A246655 lists the prime-powers (A000961 includes 1), towers A164336.
Cf. A001970, A055887, A063834, A085970, A279784, A295935, A356065.

Table[Length[Select[IntegerPartitions[n],Count[Map[Length,FactorInteger[#]], 1] == Length[#] &]], {n, 0, 35}] (* Geoffrey Critzer, Oct 25 2015 *)
nmax = 50; Clear[P]; P[m_] := P[m] = Product[Product[1/(1-x^(p^k)), {k, 1, m}], {p, Prime[Range[PrimePi[nmax]]]}]/(1-x)+O[x]^nmax // CoefficientList[ #, x]&; P[1]; P[m=2]; While[P[m] != P[m-1], m++]; P[m] (* Jean-François Alcover, Aug 31 2016 *)

lista(m) = {x = t + t*O(t^m); gf = prod(k=1, m, if (isprimepower(k), 1/(1-x^k), 1))/(1-x); for (n=0, m, print1(polcoeff(gf, n, t), ", "));} \\ Michel Marcus, Mar 09 2013

from functools import lru_cache
from sympy import factorint
@lru_cache(maxsize=None)
def A023893(n):
    @lru_cache(maxsize=None)
    def c(n): return sum((p**(e+1)-p)//(p-1) for p,e in factorint(n).items())+1
    return (c(n)+sum(c(k)*A023893(n-k) for k in range(1,n)))//n if n else 1 # Chai Wah Wu, Jul 15 2024

G.f.: (Product_{p prime} Product_{k>=1} 1/(1-x^(p^k))) / (1-x).

A069016 Look at all the different ways to factorize n as a product of numbers bigger than 1, and for each factorization write down the sum of the factors; a(n) = number of different sums.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 4, 1, 3, 2, 2, 1, 5, 2, 2, 3, 3, 1, 5, 1, 4, 2, 2, 2, 7, 1, 2, 2, 5, 1, 5, 1, 3, 4, 2, 1, 8, 2, 4, 2, 3, 1, 7, 2, 5, 2, 2, 1, 9, 1, 2, 4, 6, 2, 5, 1, 3, 2, 5, 1, 10, 1, 2, 4, 3, 2, 5, 1, 8, 5, 2, 1, 8, 2, 2, 2, 5, 1, 10, 2, 3, 2, 2, 2, 12, 1, 4, 4, 7, 1, 5, 1

Offset: 1

Amarnath Murthy, Apr 01 2002

nonn

			The factorizations of 12 are (2,2,3), (2,6), (3,4), and (12), which have three distinct sums 7, 8, and 12. Hence a(12) = 3. - _Antti Karttunen_, Oct 21 2017
The factorizations of 30 are (2,3,5), (2,15), (3,10), (5,6) and (30), which have the 5 distinct sums 10, 17, 13, 11 and 30. Hence a(30) = 5.

Amarnath Murthy, Generalization of Partition Function and Introducing Smarandache Factor Partitions, Smarandache Notions Journal, Vol. 11, 1-2-3. Spring 2000.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Antti Karttunen, Scheme-program for computing this sequence

Cf. A001055, A034891.

a(n) <= A001055(n). - David A. Corneth, Oct 21 2017

Edited by David W. Wilson, May 27 2002

Edited by N. J. A. Sloane, Apr 28 2013

A280917 Expansion of 1/(1 - x - Sum_{k>=1} x^prime(k)).

Original entry on oeis.org

1, 1, 2, 4, 7, 14, 26, 50, 95, 180, 343, 652, 1240, 2359, 4486, 8532, 16227, 30862, 58697, 111636, 212321, 403814, 768015, 1460691, 2778094, 5283667, 10049027, 19112282, 36349721, 69133673, 131485594, 250072951, 475614693, 904573387, 1720411555, 3272057256, 6223138101, 11835809946, 22510571803, 42812941849

Offset: 0

Ilya Gutkovskiy, Jan 10 2017

nonn

Number of compositions (ordered partitions) of n into prime parts (1 included) (A008578).

			a(4) = 7 because we have [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2] and [1, 1, 1, 1].

Indranil Ghosh, Table of n, a(n) for n = 0..99
Index entries for sequences related to compositions

Cf. A000607, A002124, A008578, A023360, A034891, A036497.

nmax = 39; CoefficientList[Series[1/(1 - x - Sum[x^Prime[k], {k, 1, nmax}]), {x, 0, nmax}], x]

Vec(1 / (1 - x - sum(k=1, 100,  x^prime(k))) + O(x^100)) \\ Indranil Ghosh, Mar 09 2017

G.f.: 1/(1 - x - Sum_{k>=1} x^prime(k)).

A379315 Number of strict integer partitions of n with a unique 1 or prime part.

Original entry on oeis.org

0, 1, 1, 1, 0, 2, 1, 3, 1, 3, 2, 7, 3, 7, 4, 10, 7, 15, 7, 17, 13, 23, 16, 31, 20, 37, 31, 48, 38, 62, 48, 76, 68, 93, 80, 119, 105, 147, 137, 175, 166, 226, 208, 267, 263, 326, 322, 407, 391, 481, 492, 586, 591, 714, 714, 849, 884, 1020, 1050, 1232, 1263

Offset: 0

Gus Wiseman, Dec 28 2024

nonn

The "old" primes are listed by A008578.

			The a(10) = 2 through a(15) = 10 partitions:
  (8,2)  (11)     (9,3)    (13)     (9,5)    (8,7)
  (9,1)  (6,5)    (10,2)   (7,6)    (12,2)   (10,5)
         (7,4)    (6,4,2)  (8,5)    (8,4,2)  (11,4)
         (8,3)             (10,3)   (9,4,1)  (12,3)
         (9,2)             (12,1)            (14,1)
         (10,1)            (6,4,3)           (6,5,4)
         (6,4,1)           (8,4,1)           (8,4,3)
                                             (8,6,1)
                                             (9,4,2)
                                             (10,4,1)

Andrew Howroyd, Table of n, a(n) for n = 0..1000

For all prime parts we have A000586, non-strict A000607 (ranks A076610).
For no prime parts we have A096258, non-strict A002095 (ranks A320628).
For a unique composite part we have A379303, non-strict A379302 (ranks A379301).
Considering 1 nonprime gives A379305, non-strict A379304 (ranks A331915).
For squarefree instead of old prime we have A379309, non-strict A379308 (ranks A379316).
Ranked by A379312 /\ A005117 = squarefree positions of 1 in A379311.
The non-strict version is A379314.
A000040 lists the prime numbers, differences A001223.
A000041 counts integer partitions, strict A000009.
A002808 lists the composite numbers, nonprimes A018252, differences A073783 or A065310.
A376682 gives k-th differences of old primes.
Cf. A000070, A023895, A034891, A036497, A038348, A095195, A175804, A204389, A257994, A302540.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Count[#,_?(#==1||PrimeQ[#]&)]==1&]],{n,0,30}]

seq(n)={Vec(sum(k=1, n, if(isprime(k) || k==1, x^k)) * prod(k=4, n, 1 + if(!isprime(k), x^k), 1 + O(x^n)), -n-1)} \\ Andrew Howroyd, Dec 28 2024

A379301 Positive integers whose prime indices include a unique composite number.

Original entry on oeis.org

7, 13, 14, 19, 21, 23, 26, 28, 29, 35, 37, 38, 39, 42, 43, 46, 47, 52, 53, 56, 57, 58, 61, 63, 65, 69, 70, 71, 73, 74, 76, 77, 78, 79, 84, 86, 87, 89, 92, 94, 95, 97, 101, 103, 104, 105, 106, 107, 111, 112, 113, 114, 115, 116, 117, 119, 122, 126, 129, 130, 131

Offset: 1

Gus Wiseman, Dec 25 2024

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The prime indices of 70 are {1,3,4}, so 70 is in the sequence.
The prime indices of 98 are {1,4,4}, so 98 is not in the sequence.

For no composite parts we have A302540, counted by A034891 (strict A036497).
For all composite parts we have A320629, counted by A023895 (strict A204389).
For a unique prime part we have A331915, counted by A379304 (strict A379305).
Positions of one in A379300.
Partitions of this type are counted by A379302 (strict A379303).
A000040 lists the prime numbers, differences A001223.
A002808 lists the composite numbers, nonprimes A018252, differences A073783 or A065310.
A055396 gives least prime index, greatest A061395.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A066247 is the characteristic function for the composite numbers.
A377033 gives k-th differences of composite numbers, see A073445, A377034-A377037.
Other counts of prime indices:
- A087436 postpositive, see A038550.
- A257991 odd, see A000041, A000070, A066207, A349158.
- A257992 even, see A000009, A038348, A066208, A379317.
- A257994 prime, see A000586, A000607, A076610, A331386.
- A330944 nonprime, see A002095, A096258, A320628, A330945.
- A379306 squarefree, see A302478, A379308, A379309, A379316.
- A379310 nonsquarefree, see A114374, A256012, A379307.
- A379311 old prime, see A379312-A379315.
Cf. A113646, A376680.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Length[Select[prix[#],CompositeQ]]==1&]

A379304 Number of integer partitions of n with a unique prime part.

Original entry on oeis.org

0, 0, 1, 2, 2, 3, 4, 6, 7, 9, 11, 17, 20, 26, 31, 41, 47, 62, 72, 93, 108, 136, 156, 199, 226, 279, 321, 398, 452, 555, 630, 767, 873, 1051, 1188, 1433, 1618, 1930, 2185, 2595, 2921, 3458, 3891, 4580, 5155, 6036, 6776, 7926, 8883, 10324, 11577, 13421, 15014

Offset: 0

Gus Wiseman, Dec 27 2024

nonn

			The a(2) = 1 through a(9) = 9 partitions:
  (2)  (3)   (31)   (5)     (42)     (7)       (62)       (54)
       (21)  (211)  (311)   (51)     (43)      (71)       (63)
                    (2111)  (3111)   (421)     (431)      (621)
                            (21111)  (511)     (4211)     (711)
                                     (31111)   (5111)     (4311)
                                     (211111)  (311111)   (42111)
                                               (2111111)  (51111)
                                                          (3111111)
                                                          (21111111)

For all prime parts we have A000607 (strict A000586), ranks A076610.
For no prime parts we have A002095 (strict A096258), ranks A320628.
Ranked by A331915 = positions of one in A257994.
For a unique composite part we have A379302 (strict A379303), ranks A379301.
The strict case is A379305.
For squarefree instead of prime we have A379308 (strict A379309), ranks A379316.
Considering 1 prime gives A379314 (strict A379315), ranks A379312.
A000040 lists the prime numbers, differences A001223.
A000041 counts integer partitions, strict A000009.
A002808 lists the composite numbers, nonprimes A018252, differences A073783 or A065310.
A095195 gives k-th differences of prime numbers.
Cf. A000070, A023895, A034891, A036497, A204389, A302540, A330944.

Table[Length[Select[IntegerPartitions[n],Count[#,_?PrimeQ]==1&]],{n,0,30}]

A379305 Number of strict integer partitions of n with a unique prime part.

Original entry on oeis.org

0, 0, 1, 2, 1, 1, 2, 3, 3, 3, 3, 6, 8, 8, 8, 10, 12, 17, 18, 18, 22, 28, 30, 36, 40, 44, 52, 62, 67, 78, 87, 97, 113, 129, 137, 156, 177, 200, 227, 251, 271, 312, 350, 382, 425, 475, 521, 588, 648, 705, 785, 876, 957, 1061, 1164, 1272, 1411, 1558, 1693, 1866

Offset: 0

Gus Wiseman, Dec 27 2024

nonn

			The a(2) = 1 through a(12) = 8 partitions (A=10, B=11):
  (2)  (3)   (31)  (5)  (42)  (7)    (62)   (54)   (82)   (B)    (93)
       (21)             (51)  (43)   (71)   (63)   (541)  (65)   (A2)
                              (421)  (431)  (621)  (631)  (74)   (B1)
                                                          (83)   (642)
                                                          (92)   (651)
                                                          (821)  (741)
                                                                 (831)
                                                                 (921)

For all prime parts we have A000586, non-strict A000607 (ranks A076610).
For no prime parts we have A096258, non-strict A002095 (ranks A320628).
Ranked by A331915 /\ A005117 = squarefree positions of one in A257994.
For a composite instead of prime we have A379303, non-strict A379302 (ranks A379301).
The non-strict version is A379304.
For squarefree instead of prime we have A379309, non-strict A379308 (ranks A379316).
Considering 1 prime gives A379315, non-strict A379314 (ranks A379312).
A000040 lists the prime numbers, differences A001223.
A000041 counts integer partitions, strict A000009.
A002808 lists the composite numbers, nonprimes A018252, differences A073783 or A065310.
A095195 gives k-th differences of prime numbers.
Cf. A000070, A023895, A034891, A036497, A038348, A204389, A302540, A320629, A330944.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Count[#,_?PrimeQ]==1&]],{n,0,30}]

A379308 Number of integer partitions of n with a unique squarefree part.

Original entry on oeis.org

0, 1, 1, 1, 0, 2, 2, 2, 0, 3, 5, 5, 1, 6, 9, 9, 2, 10, 14, 18, 6, 18, 24, 30, 11, 28, 39, 47, 24, 48, 63, 76, 41, 74, 95, 118, 65, 120, 149, 181, 107, 181, 221, 266, 169, 266, 335, 398, 262, 394, 487, 578, 391, 578, 697, 844, 592, 834, 997, 1198, 867

Offset: 0

Gus Wiseman, Dec 26 2024

nonn

			The a(1) = 1 through a(11) = 5 partitions:
  (1)  (2)  (3)  .  (5)    (6)    (7)    .  (5,4)    (10)     (11)
                    (4,1)  (4,2)  (4,3)     (8,1)    (6,4)    (7,4)
                                            (4,4,1)  (8,2)    (8,3)
                                                     (9,1)    (9,2)
                                                     (4,4,2)  (4,4,3)

If all parts are squarefree we have A073576 (strict A087188), ranks A302478.
If no parts are squarefree we have A114374 (strict A256012), ranks A379307.
For composite instead of squarefree we have A379302 (strict A379303), ranks A379301.
For prime instead of squarefree we have A379304, (strict A379305), ranks A331915.
The strict case is A379309.
For old prime instead of squarefree we have A379314, (strict A379315), ranks A379312.
Ranked by A379316, positions of 1 in A379306.
A000041 counts integer partitions, strict A000009.
A005117 lists the squarefree numbers, differences A076259.
A013929 lists the nonsquarefree numbers, differences A078147.
A377038 gives k-th differences of squarefree numbers.
A379310 counts nonsquarefree prime indices.
Cf. A000586, A000607, A002095, A013928, A023895, A034891, A072284, A073247, A120327, A175804, A376657, A377430.

Table[Length[Select[IntegerPartitions[n],Count[#,_?SquareFreeQ]==1&]],{n,0,30}]

cp's OEIS Frontend

A000792 a(n) = max{(n - i)*a(i) : i < n}; a(0) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A000793 Landau's function g(n): largest order of permutation of n elements. Equivalently, largest LCM of partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Python

Sage

Scheme

Formula

Extensions

A023893 Number of partitions of n into prime power parts (1 included); number of nonisomorphic Abelian subgroups of symmetric group S_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A069016 Look at all the different ways to factorize n as a product of numbers bigger than 1, and for each factorization write down the sum of the factors; a(n) = number of different sums.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A280917 Expansion of 1/(1 - x - Sum_{k>=1} x^prime(k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A379315 Number of strict integer partitions of n with a unique 1 or prime part.

Views