login
a(n) = max{(n - i)*a(i) : i < n}; a(0) = 1.
(Formerly M0568 N0205)
87

%I M0568 N0205 #282 Aug 10 2024 01:33:24

%S 1,1,2,3,4,6,9,12,18,27,36,54,81,108,162,243,324,486,729,972,1458,

%T 2187,2916,4374,6561,8748,13122,19683,26244,39366,59049,78732,118098,

%U 177147,236196,354294,531441,708588,1062882,1594323,2125764,3188646,4782969,6377292

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

%C Numbers of the form 3^k, 2*3^k, 4*3^k with a(0) = 1 prepended.

%C If a set of positive numbers has sum n, this is the largest value of their product.

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

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

%C 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]

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

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

%C Maximal number of divisors that are possible among numbers m such that A080256(m) = n. - _Lekraj Beedassy_, Oct 13 2003

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

%C a(n) is the largest number of complexity n in the sense of A005520 (A005245). - _David W. Wilson_, Oct 03 2005

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

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

%C a(n) = largest term of n-th row in A212721. - _Reinhard Zumkeller_, Jun 14 2012

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

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

%D B. R. Barwell, Cutting String and Arranging Counters, J. Rec. Math., 4 (1971), 164-168.

%D B. R. Barwell, Journal of Recreational Mathematics, "Maximum Product": Solution to Prob. 2004;25(4) 1993, Baywood, NY.

%D M. Capobianco and J. C. Molluzzo, Examples and Counterexamples in Graph Theory, p. 207. North-Holland: 1978.

%D S. L. Greitzer, International Mathematical Olympiads 1959-1977, Prob. 1976/4 pp. 18;182-3 NML vol. 27 MAA 1978

%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 396.

%D P. R. Halmos, Problems for Mathematicians Young and Old, Math. Assoc. Amer., 1991, pp. 30-31 and 188.

%D L. C. Larson, Problem-Solving Through Problems. Problem 1.1.4 pp. 7. Springer-Verlag 1983.

%D D. J. Newman, A Problem Seminar. Problem 15 pp. 5;15. Springer-Verlag 1982.

%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 T. D. Noe, <a href="/A000792/b000792.txt">Table of n, a(n) for n = 0..500</a>

%H R. Bercov and L. Moser, <a href="http://dx.doi.org/10.4153/CMB-1965-045-6">On Abelian permutation groups</a>, Canad. Math. Bull. 8 (1965) 627-630.

%H Walter Bridges and William Craig, <a href="https://arxiv.org/abs/2308.00123">On the distribution of the norm of partitions</a>, arXiv:2308.00123 [math.CO], 2023.

%H J. Arias de Reyna and J. van de Lune, <a href="http://arxiv.org/abs/1404.1850">The question "How many 1's are needed?" revisited</a>, arXiv preprint arXiv:1404.1850 [math.NT], 2014. See M_n.

%H J. Arias de Reyna and J. van de Lune, <a href="http://arxiv.org/abs/1404.2183">Algorithms for determining integer complexity</a>, arXiv preprint arXiv:1404.2183 [math.NT], 2014.

%H Nigel Derby, <a href="http://dx.doi.org/10.1017/S0025557200004216">96.21 The MaxProduct partition</a>, The Mathematical Gazette 96:535 (2012), pp. 148-151.

%H Tomislav Doslic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Doslic/doslic15.html">Maximum Product Over Partitions Into Distinct Parts</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.8.

%H Hans Havermann, <a href="http://chesswanks.com/seq/sopfr/">Tables of sum-of-prime-factors sequences (overview with links to the first 50000 sums)</a>.

%H J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, <a href="http://arxiv.org/abs/1203.6462">Integer Complexity: Experimental and Analytical Results</a>, arXiv preprint arXiv:1203.6462 [math.NT], 2012.

%H Andrew Kenney and Caroline Shapcott, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Shapcott/shapcott3.html">Maximum Part-Products of Odd Palindromic Compositions</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.6.

%H E. F. Krause, <a href="http://www.jstor.org/stable/2690532">Maximizing The Product of Summands</a>, Mathematics Magazine, MAA Oct 1996, Vol. 69, no. 5 pp. 270-271.

%H MathPro, 20000 Problems Under the Sea, <a href="http://web.archive.org/web/20170201082758/http://nt3.ftm.ks.edu.tw/alzing/10000/14851-14900.htm">Problem 14856.Putnam 1979/A1</a>.

%H J. W. Moon and L. Moser, <a href="http://dx.doi.org/10.1007/BF02760024">On cliques in graphs</a>, Israel J. Math. 3 (1965), 23-28.

%H Natasha Morrison and Alex Scott, <a href="https://people.maths.ox.ac.uk/scott/Papers/maxinduced.pdf">Maximizing the number of induced cycles in a graph</a>, Preprint, 2016. See f_2(n).

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.

%H F. Pluvinage, <a href="https://doi.org/10.54870/1551-3440.1266">Developing problem solving experiences in practical action projects</a>, The Mathematics Enthusiast, ISSN 1551-3440, Vol. 10, nos. 1 & 2, pp. 219-244.

%H D. A. Rawsthorne, <a href="http://www.fq.math.ca/Scanned/27-1/rawsthorne.pdf">How many 1's are needed?</a>, Fib. Quart. 27 (1989), 14-17.

%H J. T. Rowell, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Rowell/rowell3.html">Solution Sequences for the Keyboard Problem and its Generalizations</a>, Journal of Integer Sequences, 18 (2015), #15.10.7.

%H Robert Schneider and Andrew V. Sills, <a href="http://math.colgate.edu/~integers/u8/u8.Abstract.html">The Product of Parts or "Norm" of a Partition</a>, Integers (2020) Vol. 20A, Article #A13.

%H J. Scholes, <a href="https://mks.mff.cuni.cz/kalva/putnam/psoln/psol791.html">40th Putnam 1979 Problem A1</a>.

%H J. Scholes, <a href="https://mks.mff.cuni.cz/kalva/imo/isoln/isoln764.html">18th IMO 1976 Problem 4</a>.

%H Andrew V. Sills and Robert Schneider, <a href="https://arxiv.org/abs/1904.08004">The product of parts or "norm" of a partition</a>, arXiv:1904.08004 [math.NT], 2019.

%H V. Vatter, <a href="http://arxiv.org/abs/0911.4204">Maximal independent sets and separating covers</a>, Amer. Math. Monthly, 118 (2011), 418-423.

%H Robert G. Wilson v, <a href="/A000792/a000792.pdf">Letter to N. J. Sloane, circa 1991</a>.

%H A. C.-C. Yao, <a href="http://dx.doi.org/10.1016/0012-365X(76)90085-6">On a problem of Katona on minimal separating systems</a>, Discrete Math., 15 (1976), 193-199.

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,3).

%F G.f.: (1 + x + 2*x^2 + x^4)/(1 - 3*x^3). - _Simon Plouffe_ in his 1992 dissertation.

%F a(3n) = 3^n; a(3*n+1) = 4*3^(n-1) for n > 0; a(3*n+2) = 2*3^n.

%F a(n) = 3*a(n-3) if n > 4. - _Henry Bottomley_, Nov 29 2001

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

%F A007600(a(n)) = n; Andrew Chi-Chih Yao attributes this observation to D. E. Muller. - _Vincent Vatter_, Apr 24 2006

%F a(n) = 3^(n - 2 - 2*floor((n - 1)/3))*2^(2 - (n - 1) mod 3) for n > 1. - _Hieronymus Fischer_, Nov 11 2007

%F From Kiyoshi Akima (k_akima(AT)hotmail.com), Aug 31 2009: (Start)

%F a(n) = 3^floor(n/3)/(1 - (n mod 3)/4), n > 1.

%F a(n) = 3^(floor((n - 2)/3))*(2 + ((n - 2) mod 3)), n > 1. (End)

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

%F G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 - x / (1 + x / (1 + x^2 / (1 + x))))))). - _Michael Somos_, May 12 2012

%F 3*a(n) = 2*a(n+1) if n > 1 and n is not divisible by 3. - _Michael Somos_, Jan 23 2014

%F a(n) = a(n-1) + largest proper divisor of a(n-1), n > 2. - _Ivan Neretin_, Apr 13 2015

%F a(n) = max{a(i)*a(n-i) : 0 < i < n} for n >= 4. - _Jianing Song_, Feb 15 2020

%F a(n+1) = a(n) + A038754(floor( (2*(n-1) + 1)/3 )), for n > 1. - _Thomas Scheuerle_, Oct 27 2022

%e a{8} = 18 because we have 18 = (8-5)*a(5) = 3*6 and one can verify that this is the maximum.

%e 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.

%e 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 + ...

%p A000792 := proc(n)

%p m := floor(n/3) ;

%p if n mod 3 = 0 then

%p 3^m ;

%p elif n mod 3 = 1 then

%p 4*3^(m-1) ;

%p else

%p 2*3^m ;

%p end if;

%p floor(%) ;

%p end proc: # _R. J. Mathar_, May 26 2013

%t 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}]

%t CoefficientList[Series[(1 + x + 2x^2 + x^4)/(1 - 3x^3), {x, 0, 50}], x] (* _Harvey P. Dale_, May 01 2011 *)

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

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

%t Join[{1, 1}, LinearRecurrence[{0, 0, 3}, {2, 3, 4}, 50]] (* _Jean-François Alcover_, Jan 08 2019 *)

%t Join[{1,1},NestList[#+Divisors[#][[-2]]&,2,41]] (* _James C. McMahon_, Aug 09 2024 *)

%o (PARI) {a(n) = floor( 3^(n - 4 - (n - 4) \ 3 * 2) * 2^( -n%3))}; /* _Michael Somos_, Jul 23 2002 */

%o (PARI) lista(nn) = {print1("1, 1, "); print1(a=2, ", "); for (n=1, nn, a += a/divisors(a)[2]; print1(a, ", "););} \\ _Michel Marcus_, Apr 14 2015

%o (PARI) A000792(n)=if(n>1,3^((n-2)\3)*(2+(n-2)%3),1) \\ _M. F. Hasler_, Jan 19 2019

%o (Haskell)

%o a000792 n = a000792_list !! n

%o a000792_list = 1 : f [1] where

%o f xs = y : f (y:xs) where y = maximum $ zipWith (*) [1..] xs

%o -- _Reinhard Zumkeller_, Dec 17 2011

%o (Magma) 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

%Y See A007600 for a left inverse.

%Y Cf. A000793, A009490, A034891, A062943, A007601, A062723, A069188, A087902.

%Y Cf. array A064364, rightmost (nonvanishing) numbers in row n >= 2.

%Y See A056240 and A288814 for the minimal numbers whose prime factors sums up to n.

%Y A000792, A178715, A193286, A193455, A193456, and A193457 are closely related as paradigm shift sequences for (p = 0, ..., 5 respectively).

%Y Cf. A202337 (subsequence).

%Y Cf. A038754, A005245, A005520.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

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