|
| |
|
|
A000792
|
|
a(n) = max{ (n-i)*a(i) : i<n}; a(0) = 1.
(Formerly M0568 N0205)
|
|
44
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Numbers of the form 3^n, 2*3^n, 4*3^n 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 teo 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. - 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 G.P. 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 amongst numbers m such that A080256(m)=n. - Lekraj Beedassy, Oct 13 2003
Or, numbers of 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 largest number of complexity n in sense of A005520. - 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
A007600(A000792(n)) = n; Andrew Chi-Chih Yao attributes this observation to D. E. Muller. - Vincent Vatter, Apr 24 2006
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
|
|
|
REFERENCES
|
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.
R. Bercov and L. Moser, On Abelian permutation groups, Canad. Math. Bull., 8 (1965), 627-630.
M. Capobianco and J. C. Molluzzo, Examples and Counterexamples in Graph Theory, p. 207. North-Holland: 1978.
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.
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.
J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results. Arxiv preprint arXiv: #, 2012. - From N. J. A. Sloane, Sep 22 2012
E. F. Krause, "Maximizing The Product of Summands", Mathematics Magazine, MAA Oct 1996, Vol. 69, no. 5 pp. 270-271.
L. C. Larson, Problem-Solving Through Problems. Problem 1.1.4 pp. 7. Sprnger-Verlag 1983.
J. W. Moon and L. Moser, On cliques in graphs, Israel J. Math. 3 (1965), 23-28.
D. J. Newman, A Problem Seminar. Problem 15 pp. 5;15. Spinger-Verlag 1982.
F. Pluvinage, Developing problem solving experiences in practical action projects, The Mathematics Enthusiast, ISSN 1551-3440, Vol. 10, nos.1&2, pp. 219-244; http://www.math.umt.edu/tmme/vol10no1and2/9-Pluvinage_pp219_244.pdf. - From N. J. A. Sloane, Feb 07 2013
D. A. Rawsthorne, How many 1's are needed?, Fib. Quart. 27 (1989), 14-17.
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).
V. Vatter, Maximal independent sets and separating covers, Amer. Math. Monthly, 118 (2011), 418-423.
A. C.-C. Yao, On a problem of Katona on minimal separating systems, Discrete Math., 15 (1976), 193-199.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 0..500
H. Havermann: Tables of sum-of-prime-factors sequences (overview with links to the first 50000 sums).
MathPro, 20000 Problems Under the Sea, Problem 14856.Putnam 1979/A1
_Simon Plouffe_, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
J. Scholes, 40th Putnam 1979 Problem A1
J. Scholes, 18th IMO 1976 Problem 4
Index to sequences related to the complexity of n
Index entries for sequences related to linear recurrences with constant coefficients
|
|
|
FORMULA
|
a(n) = 3*a(n-3) if n>4. G.f.: (1+x+2*x^2+x^4)/(1-3*x^3). - Henry Bottomley, Nov 29 2001
a(3n) = 3^n; a(3*n+1) = 4*3^(n-1) for n>0; a(3*n+2) = 2*3^n.
a(n) = if n<=2 then n else a(n-1)+Max{GCD(a(i), a(j))| 0<i<j<n}. - Reinhard Zumkeller, Feb 08 2002
a(n)=3^(n-2-2*floor((n-1)/3))*2^(2-(n-1)mod 3) for n>1. - Hieronymus Fischer, Nov 11 2007
a(n)=3^floor(n/3)/(1-(n mod 3)/4), n>1 [From Kiyoshi Akima (k_akima(AT)hotmail.com), Aug 31 2009]
a(n)=3^(floor((n-2)/3))*(2+((n-2) mod 3))), n>1 [From Kiyoshi Akima (k_akima(AT)hotmail.com), Aug 31 2009]
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
|
|
|
EXAMPLE
|
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.
1 + x + 2*x^2 + 3*x^3 + 4*x^4 + 6*x^5 + 9*x^6 + 12*x^7 + 18*x^8 + ...
|
|
|
MAPLE
|
A000792:=-(1+2*z+3*z**2+z**3)/(-1+3*z**3); [Conjectured (correctly) by Simon Plouffe in his 1992 dissertation.]
|
|
|
MATHEMATICA
|
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] (* From 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 *)
|
|
|
PROG
|
(PARI) {a(n) = floor( 3^(n - 4 - (n - 4) \3 *2) * 2^( -n%3))} /* Michael Somos, Jul 23 2002 */
(Haskell)
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
|
|
|
CROSSREFS
|
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 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).
Sequence in context: A018130 A160993 A171826 * A018752 A018393 A018287
Adjacent sequences: A000789 A000790 A000791 * A000793 A000794 A000795
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms and better description from Therese Biedl (biedl(AT)uwaterloo.ca), Jan 19 2000
|
|
|
STATUS
|
approved
|
| |
|
|
