A007600 -id:A007600 - 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

A005245 The (Mahler-Popken) complexity of n: minimal number of 1's required to build n using + and *.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications and parentheses. This does not allow juxtaposition of 1's to form larger integers, so for example, 2 = 1+1 has complexity 2, but 11 does not ("pasting together" two 1's is not an allowed operation).
The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.
Guy asks if a(p) = a(p-1) + 1 for prime p. Martin Fuller found the least counterexample p = 353942783 in 2008, see Fuller link. - Charles R Greathouse IV, Oct 04 2012
It appears that this sequence is lower than A348262 {1,+,^} only a finite number of times. - Gordon Hamilton and Brad Ballinger, May 23 2022
The second Altman links proves that {a(n) - 3*log_3(n)} is a well-ordered subset of the reals whose intersection with [0,k) has order type omega^k for each positive integer k, so this set itself has order type omega^omega. - Jianing Song, Apr 13 2024

			From _Lekraj Beedassy_, Jul 04 2009: (Start)
   n.........minimal expression........ a(n) = number of 1's
   1..................1...................1
   2.................1+1..................2
   3................1+1+1.................3
   4.............(1+1)*(1+1)..............4
   5............(1+1)*(1+1)+1.............5
   6............(1+1)*(1+1+1).............5
   7...........(1+1)*(1+1+1)+1............6
   8..........(1+1)*(1+1)*(1+1)...........6
   9...........(1+1+1)*(1+1+1)............6
  10..........(1+1+1)*(1+1+1)+1...........7
  11.........(1+1+1)*(1+1+1)+1+1..........8
  12.........(1+1)*(1+1)*(1+1+1)..........7
  13........(1+1)*(1+1)*(1+1+1)+1.........8
  14.......{(1+1)*(1+1+1)+1}*(1+1)........8
  15.......{(1+1)*(1+1)+1}*(1+1+1)........8
  16.......(1+1)*(1+1)*(1+1)*(1+1)........8
  17......(1+1)*(1+1)*(1+1)*(1+1)+1.......9
  18........(1+1)*(1+1+1)*(1+1+1).........8
  19.......(1+1)*(1+1+1)*(1+1+1)+1........9
  20......{(1+1+1)*(1+1+1)+1}*(1+1).......9
  21......{(1+1)*(1+1+1)+1}*(1+1+1).......9
  22.....{(1+1)*(1+1+1)+1}*(1+1+1)+1.....10
  23....{(1+1)*(1+1+1)+1}*(1+1+1)+1+1....11
  24......(1+1)*(1+1)*(1+1)*(1+1+1).......9
  25.....(1+1)*(1+1)*(1+1)*(1+1+1)+1.....10
  26....{(1+1)*(1+1)*(1+1+1)+1}*(1+1)....10
  27.......(1+1+1)*(1+1+1)*(1+1+1)........9
  28......(1+1+1)*(1+1+1)*(1+1+1)+1......10
  29.....(1+1+1)*(1+1+1)*(1+1+1)+1+1.....11
  30.....{(1+1+1)*(1+1+1)+1}*(1+1+1).....10
  31....{(1+1+1)*(1+1+1)+1}*(1+1+1)+1....11
  32....(1+1)*(1+1)*(1+1)*(1+1)*(1+1)....10
  33...(1+1)*(1+1)*(1+1)*(1+1)*(1+1)+1...11
  34..{(1+1)*(1+1)*(1+1)*(1+1)+1}*(1+1)..11
  .........................................
(End)

M. Criton, "Les uns de Germain", Problem No. 4, pp. 13 ; 68 in '7 x 7 Enigmes Et Défis Mathématiques pour tous', vol. 25, Editions POLE, Paris 2001.
R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.
K. Mahler and J. Popken, Over een Maximumprobleem uit de Rekenkunde (Dutch: On a maximum problem in arithmetic), Nieuw Arch. Wiskunde, (3) 1 (1953), pp. 1-15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. F. Hasler, Table of n, a(n) for n = 1..10000
Harry Altman, Highest few sums and products of ones, Preprint, undated but before 2013.
Harry Altman, Integer Complexity and Well-Ordering, arXiv:1310.2894v1 [math.NT] , Oct 10, 2013.
Harry Altman and Joshua Zelinsky, Numbers with integer complexity close to the lower bound, arXiv:1207.4841 [math.NT], 2012.
J. Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250.
J. Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250. [Cached copy, with permission]
J. Arias de Reyna, Complexity of natural numbers, arXiv:2111.03345 [math.NT], 2021.
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.
J. Arias de Reyna and J. van de Lune, Algorithms for determining integer complexity, arXiv preprint arXiv:1404.2183 [math.NT], 2014.
Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis and Karlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arxiv:1409.0446 [math.NT], 2014.
Katherine Cordwell, Alyssa Epstein, Anand Hemmady, Steven J. Miller, Eyvindur A. Palsson, Aaditya Sharma, Stefan Steinerberger and Yen Nhi Truong Vu, On algorithms to calculate integer complexity, arXiv:1706.08424 [math.NT], 2017.
Martin N. Fuller, C program
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Qizheng He, Improved Algorithms for Integer Complexity, arXiv:2308.10301 [cs.DS], 2023.
Janis Iraids, Online calculator of a(n) for n < 10^12
Jānis Iraids, Kaspars Balodis, Juris Čerņenoks, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, Integer complexity: experimental and analytical results, arXiv:1203.6462 [math.NT], 2012.
Daniel A. Rawsthorne, How many 1's are needed?, Fibonacci Quarterly 27 (1989), pp. 14-17.
Srinivas, Vivek V. and Shankar, B. R., Integer Complexity: Breaking the Theta(n^2) barrier, World Academy of Science 41 (2008), pp. 690-691.
Stefan Steinerberger, A Short Note on Integer Complexity, Contributions to Discrete Mathematics, Vol. 9.1 (2014).
Stefan Steinerberger, A short note on integer complexity, Contributions to Discrete Mathematics, Vol. 9.1 (2014). [Cached copy, with permission.]
Joshua Zelinsky, Upper Bounds on Integer Complexity, arXiv preprint (2022). arXiv:2211.02995 [math.NT]
Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, YouTube video, 2012.
Venecia Wang, A counterexample to the prime conjecture of expressing numbers using just ones, Journal of Number Theory, Volume 133, Issue 2, February 2013, Pages 391-397.
Eric Weisstein's World of Mathematics, Integer Complexity
Dimitri Zucker, The Most Underrated Concept in Number Theory, Combo Class Youtube video that mentions this sequence.
Index to sequences related to the complexity of n

Cf. A025280 (variant using +, *, and ^), A091333 (using +, -, and *), A091334 (using +, -, *, and ^), A348089 (using +, -, *, / and ^), A348262 (using + and ^).

Cf. A000792 (largest integer of given complexity), A003313, A076142, A076091, A061373, A005421, A064097, A005520, A003037, A161906, A161908, A244743.

import Data.List (genericIndex)
a005245 n = a005245_list `genericIndex` (n-1)
a005245_list = 1 : f 2 [1] where
   f x ys = y : f (x + 1) (y : ys) where
     y = minimum $
         (zipWith (+) (take (x `div` 2) ys) (reverse ys)) ++
         (zipWith (+) (map a005245 $ tail $ a161906_row x)
                      (map a005245 $ reverse $ init $ a161908_row x))
-- Reinhard Zumkeller, Mar 08 2013

with(numtheory):
a:= proc(n) option remember;
      `if`(n=1, 1, min(seq(a(i)+a(n-i), i=1..n/2),
       seq(a(d)+a(n/d), d=divisors(n) minus {1, n})))
    end:
seq(a(n), n=1..100); # Alois P. Heinz, Apr 18 2012

a[n_] := a[n] = If[n == 1, 1,
   Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~
   Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}]]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Dec 12 2013, after Alois P. Heinz *)

A005245(n /* start by calling this with the largest needed n */, lim/* see below */) = { local(d); n<6 && return(n);
if(n<=#A005245, A005245[n]&return(A005245[n]) /* return memoized result if available */,
A005245=vector(n) /* create vector if needed - should better reuse existing data if available */);
for(i=1, n-1, A005245[i] || A005245[i]=A005245(i,lim)); /* compute all previous elements */
A005245[n]=min( vecmin(vector(min(n\2,if(lim>0,lim,n)), k, A005245[k]+A005245[n-k])) /* additive possibilities - if lim>0 is given, consider a(k)+a(n-k) only for k<=lim - we know it is save to use lim=1 up to n=2e7 */, if( isprime(n), n, vecmin(vector((-1+#d=divisors(n))\2, i, A005245[d[i+1]]+A005245[d[ #d-i]]))/* multiplicative possibilities */))}
\\ See also the Python program by Tim Peters at A005421.
\\ M. F. Hasler, Jan 30 2008

from functools import lru_cache
from itertools import takewhile
from sympy import divisors
@lru_cache(maxsize=None)
def A005245(n): return min(min(A005245(a)+A005245(n-a) for a in range(1,(n>>1)+1)),min((A005245(d)+A005245(n//d) for d in takewhile(lambda d:d*d<=n,divisors(n)) if d>1),default=n)) if n>1 else 1 # Chai Wah Wu, Apr 29 2023

It is known that a(n) <= A061373(n) but I think 0 <= A061373(n) - a(n) <= 1 also holds. - Benoit Cloitre, Nov 23 2003 [That's false: the numbers {46, 235, 649, 1081, 7849, 31669, 61993} require {1, 2, 3, 4, 5, 6, 7} fewer 1's in A005245 than in A061373. - Ed Pegg Jr, Apr 13 2004]
It is known from the work of Selfridge and Coppersmith that 3 log_3 n <= a(n) <= 3 log_2 n = 4.754... log_3 n for all n > 1. [Guy, Unsolved Problems in Number Theory, Sect. F26.] - Charles R Greathouse IV, Apr 19 2012 [Comment revised by N. J. A. Sloane, Jul 17 2016]
Zelinsky (2022) improves the upper bound to a(n) <= A*log n where A = 41/log(55296) = 3.754422.... This compares to the constant 2.7307176... of the lower bound. - Charles R Greathouse IV, Dec 11 2022
a(n) >= A007600(n) is a very accurate lower bound. - Mehmet Sarraç, Dec 18 2022

More terms from David W. Wilson, May 15 1997

cp's OEIS Frontend

A007601 Positions where A007600 increases.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A005245 The (Mahler-Popken) complexity of n: minimal number of 1's required to build n using + and *.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A350723 Integer defect of n: a(n) = A005245(n) - A349983(n).

Views

Author

Keywords

References

Links

Crossrefs

A349983 a(n) is the largest k such A000792(k) <= n.

Views

Author

Keywords

References

Links

Crossrefs

Formula