A005421 -id:A005421 - cp's OEIS frontend

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

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

A005520 Smallest number of complexity n: smallest number requiring n 1's to build using + and *.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, 59, 89, 107, 167, 179, 263, 347, 467, 683, 719, 1223, 1438, 1439, 2879, 3767, 4283, 6299, 10079, 11807, 15287, 21599, 33599, 45197, 56039, 81647, 98999, 163259, 203999, 241883, 371447, 540539, 590399, 907199

Offset: 1

N. J. A. Sloane

Ed Pegg Jr, www.mathpuzzle.com, Apr 10 2001, notes that all the new terms are -1 mod 120. - That is, this holds at least for all terms from a(45) = 590399 up to the highest known term a(89) given in the b-file at the end of 2015. Comment clarified by Antti Karttunen, Dec 14 2015
Largest number of complexity n is given by A000792. - David W. Wilson, Oct 03 2005
After 1438 = 2 * 719, all elements through 8206559 are primes. Equivalently, except for a(4) = 4, a(7) = 10, a(10) = 22 and a(25) = 1438, we have a(1) through a(53) are all primes. - Jonathan Vos Post, Apr 07 2006
a(54)-a(89) are all primes. - Janis Iraids, Apr 21 2011
Previous observations (primes with property -1 mod 120) still hold. - Martins Opmanis, Oct 16 2009
The prime 353942783 = A189125(1) = 2*3 + (1 + 2^2*3^2)*(2 + 3^4(1 + 2*3^10)) is the smallest counterexample to Guy's first hypothesis on integer complexity. - Jonathan Vos Post, Mar 30 2012
The sequence A265360 (second smallest number of complexity n) seems to have similar properties. - Janis Iraids via Antti Karttunen, Dec 15 2015

			Examples from Piotr Fabian:
1 = 1, 1 "one": first 1, a(1) = 1
2 = 1+1, 2 "ones": first 2, a(2) = 2
3 = 1+1+1, 3 "ones": first 3, a(3) = 3
4 = 1+1+1+1, 4 "ones": first 4, a(4) = 4
5 = 1+1+1+1+1, 5 "ones": first 5, a(5) = 5
6 = (1+1)*(1+1+1), 5 "ones"
7 = 1+((1+1)*(1+1+1)), 6 "ones": first 6, a(6) = 7
8 = (1+1)*(1+1+1+1), 6 "ones"
9 = (1+1+1)*(1+1+1), 6 "ones"
10 = 1+((1+1+1)*(1+1+1)), 7 "ones": first 7, a(7) = 10
11 = 1+(1+(1+1+1)*(1+1+1)), 8 "ones": first 8, a(8) = 11
12 = (1+1)*((1+1)*(1+1+1)), 7 "ones"

R. K. Guy, Unsolved Problems in Number Theory, Sec. F26 (related material).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Janis Iraids, Table of n, a(n) for n = 1..89
Kazuyuki Amano, Integer Complexity and Mixed Binary-Ternary Representation, 33rd Int'l Symp. Alg. Comp. (ISAAC 2022) Leibniz Int'l Proc. Informatics (LIPIcs) Vol. 248.
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. See also Integers (2024) Vol. 24, A19, p. 6.
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ā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.
Ed Pegg Jr., Math Games: Integer Complexity, www.mathpuzzle.com, April 12, 2004.
D. A. Rawsthorne, How many 1's are needed?, Fib. Quart. 27 (1989), 14-17.
Eric Weisstein's World of Mathematics, Integer Complexity
Index to sequences related to the complexity of n

Cf. A005245, A025280, A003037, A005421, A048183, A181898, A182061, A265360.

N = 10^6;
fact = cell(1,N);
for n = 2:sqrt(N)
  for m = [n^2:n:N]
    fact{m} = [fact{m},n];
  end
end
R = zeros(1,N);
R(1) = 1;
A(1) = 1;
mmax = 1;
for n = 2:N
  m = min(R(1:floor(n/2)) + R([n-1:-1:ceil(n/2)]));
  if numel(fact{n}) > 0
    m = min(m, min(R(fact{n}) + R(n ./ fact{n})));
  end
  R(n) = m;
  if m > mmax
    A(m) = n;
    mmax = m;
  elseif A(m) == 0
    A(m) = n;
  end
end
A % Robert Israel, Dec 14 2015

N:= 100000: # to get all terms <= N
R:= Vector(N):
R[1]:= 1: A[1]:= 1:
for n from 2 to N do
  inds:= [seq(n-i,i=1..floor(n/2))];
  m:= min(R[1..floor(n/2)] + R[inds]);
  for d in select(`<=`,numtheory:-divisors(n),floor(sqrt(n))) minus {1} do
    m:= min(m, R[d]+R[n/d])
  od;
  R[n]:= m;
  if not assigned(A[m]) then A[m]:= n fi;
od:
seq(A[m],m=1..max(R)); # Robert Israel, Dec 14 2015

nn = 10000;
R = Table[0, nn];
R[[1]] = 1; Clear[A]; A[1] = 1;
For[n = 2, n <= nn, n++,
  inds = Table[n-i, {i, 1, n/2}];
  m = Min[R[[1 ;; Floor[n/2]]] + R[[inds]]];
  Do[
    m = Min[m, R[[d]] + R[[n/d]]], {d,
    Select[Rest[Divisors[n]], # <= Sqrt[n]&]}
  ];
  R[[n]] = m;
  If[!IntegerQ[A[m]], A[m] = n];
];
Table[A[m], {m, 1, Max[R]}] (* Jean-François Alcover, Aug 05 2018, after Robert Israel *)

def aupton(nn):
  alst, R = [1], {0: {1}} # R[n] is set reachable using n+1 1's (n ops)
  for n in range(1, nn):
    R[n]  = set(a+b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
    R[n] |= set(a*b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
    alst.append(min(R[n] - R[n-1]))
  return alst
print(aupton(35)) # Michael S. Branicky, Jun 08 2021

Corrected and extended by David W. Wilson, May 1997
Extended to terms a(40)=163259 and a(41)=203999 by John W. Layman, Nov 03 1999
Further terms from Piotr Fabian (PCF(AT)who.net), Mar 30 2001
a(68)-a(89) from Janis Iraids, Apr 20 2011

A048249 Number of distinct values produced from sums and products of n unity arguments.

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 11, 17, 23, 30, 44, 60, 80, 114, 156, 212, 296, 404, 556, 770, 1065, 1463, 2032, 2795, 3889, 5364, 7422, 10300, 14229, 19722, 27391, 37892, 52599, 73075, 101301, 140588, 195405, 271024, 376608, 523518, 726812, 1010576, 1405013, 1952498

Offset: 1

Tony Bartoletti

Values listed calculated by exhaustive search algorithm.
For n+1 operands (n operations) there are (2n)!/((n!)((n+1)!)) possible postfix forms over a single operator. For each such form, there are 2^n ways to assign 2 operators (here, sum and product). Calculate results and eliminate duplicates.
Number of distinct positive integers that can be obtained by iteratively adding or multiplying together parts of an integer partition until only one part remains, starting with 1^n. - Gus Wiseman, Sep 29 2018

			a(3)=3 since (in postfix): 111** = 11*1* = 1, 111*+ = 11*1+ = 111+* = 11+1* = 2 and 111++ = 11+1+ = 3. Note that at n=7, the 11 possible values produced are the set {1,2,3,4,5,6,7,8,9,10,12}. This is the first n for which there are "skipped" values in the set.

Cf. A000792, A005520, A066739, A070960, A201163, A319850, A318949, A319855, A319856, A319909, A319910, A319911.

b:= proc(n) option remember; `if`(n=1, {1}, {seq(seq(seq(
     [f+g, f*g][], g=b(n-i)), f=b(i)), i=1..iquo(n, 2))})
    end:
a:= n-> nops(b(n)):
seq(a(n), n=1..35);  # Alois P. Heinz, May 05 2019

ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
Table[Length[Select[ReplaceListRepeated[{Array[1&,n]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]],{n,10}] (* Gus Wiseman, Sep 29 2018 *)

from functools import cache
@cache
def f(m):
    if m == 1: return {1}
    out = set()
    for j in range(1, m//2+1):
        for x in f(j):
            for y in f(m-j):
                out.update([x + y, x * y])
    return out
def a(n): return len(f(n))
print([a(n) for n in range(1, 40)]) # Michael S. Branicky, Aug 03 2022

Equals partial sum of "number of numbers of complexity n" (A005421). - Jonathan Vos Post, Apr 07 2006

More terms from David W. Wilson, Oct 10 2001

a(43)-a(44) from Alois P. Heinz, May 05 2019

A003037 Smallest number of complexity n: smallest number requiring n 1's to build using +, * and ^.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 11, 13, 21, 23, 41, 43, 71, 94, 139, 211, 215, 431, 863, 1437, 1868, 2855, 5737, 8935, 15838, 15839, 54357, 95597, 139117, 233195, 470399, 1228247, 2183791, 4388063, 6945587, 13431919, 32329439, 46551023

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, exponentiation 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 (concatenating 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. - Jonathan Vos Post, Oct 20 2007

			An example (usually nonunique) of the derivation of the first 10 values.
a(1) = 1, the number of 1's in "1."
a(2) = 2, the number of 1's in "1+1 = 2."
a(3) = 3, the number of 1's in "1+1+1 = 3."
a(4) = 4, the number of 1's in "1+1+1+1 = 4."
a(5) = 5, the number of 1's in "1+1+1+1+1 = 5."
a(6) = 7, since there are 6 1's in "((1+1)*(1+1+1))+1 = 7."
a(7) = 11, since there are 7 1's in "((1+1+1)^(1+1))+1+1 = 11."
a(8) = 13, since there are 8 1's in "((1+1+1)*(1+1+1+1))+1 = 13."
a(9) = 21, since there are 9 1's in "(1+1+1)*(((1+1)*(1+1+1))+1) = 21."
a(10) = 23, since there are 10 1's in "1+((1+1)*(((1+1+1)^(1+1))+1+1)) = 23."

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

W. A. Beyer, Letter to N. J. A. Sloane, 1980
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
Index to sequences related to the complexity of n

Cf. A025280, A005520, A005245, A005421, A117618.

xmax:= 5:  # get terms <= 10^xmax
C[1]:= {1}: A[1]:= 1: CU[1]:= {1}:
for n from 2 do
   C[n]:= {seq(seq(seq(op(select(`<=`,
[a+b,a*b,`if`(b*ilog10(a) <= xmax,a^b,NULL),`if`(a*ilog10(b) <= xmax,b^a,NULL)]
         ,10^xmax)),b=C[n-k]),a=C[k]),k=1..floor(n/2))}
         minus CU[n-1];
   if C[n] = {} then break fi;
   A[n]:= min(C[n]);
   CU[n]:= CU[n-1] union C[n];
od:
seq(A[i],i=1..n-1); # Robert Israel, Jan 08 2015

More terms from David W. Wilson, May 15 1997

More terms from Sean A. Irvine, Jan 07 2015

A182002 Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.

Original entry on oeis.org

2, 2, 1, 10, 13, 22, 38, 91, 195, 443, 634, 1121, 3448, 6793, 17692

Offset: 1

Ali Dasdan, Apr 05 2012

			a(2) = 2 because two 2's can produce 0 = 2-2, 1 = 2/2, 4 = 2+2 = 2*2, so the smallest positive integer that cannot be computed is 2.
a(3) = 1 because no expression with three 3's gives 1.

Cf. A005245, A005520, A003313, A076142, A076091, A061373, A005421, A064097, A025280, A003037, A117618.

Cf. A171826, A171827, A171828, A171829, A258068, A258069, A258070, A258071.

f:= proc(n,b) option remember;
      `if`(n=1, {b}, {seq(seq(seq([k+m, k-m, k*m,
      `if`(m=0, NULL, k/m)][], m=f(n-i, b)), k=f(i, b)), i=1..n-1)})
    end:
a:= proc(n) local i, l;
      l:= sort([infinity, select(x-> is(x, integer) and x>0, f(n, n))[]]);
      for i do if l[i]<>i then return i fi od
    end:
seq(a(n), n=1..8); # Alois P. Heinz, Apr 13 2012

from fractions import Fraction
from functools import lru_cache
def a(n):
    @lru_cache()
    def f(m):
        if m == 1: return {Fraction(n, 1)}
        out = set()
        for j in range(1, m//2+1):
            for x in f(j):
                for y in f(m-j):
                    out.update([x + y, x - y, y - x, x * y])
                    if y: out.add(Fraction(x, y))
                    if x: out.add(Fraction(y, x))
        return out
    k, s = 1, f(n)
    while k in s: k += 1
    return k
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Jul 29 2022

a(11)-a(12) from Alois P. Heinz, Apr 22 2012
a(13)-a(14) from Michael S. Branicky, Jul 29 2022
a(15) from Michael S. Branicky, Jul 27 2023

A133344 Complexity of the number n, counting 1's and built using +, *, ^ and # representing concatenation.

Original entry on oeis.org

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

Offset: 1

Jonathan Vos Post, Oct 20 2007

The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications, exponentiation and parentheses. This allows juxtaposition of numbers to form larger integers, so for example, 2 = 1+1 has complexity 2, but unlike A003037, so does 11 = 1#1 (concatenating two numbers is an allowed operation). Similarly a(111) = 3. The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.

			An example (usually nonunique) of the derivation of the first 22 values.
a(1) = 1, the number of 1's in "1."
a(2) = 2, the number of 1's in "1+1 = 2."
a(3) = 3, the number of 1's in "1+1+1 = 3."
a(4) = 4, the number of 1's in "1+1+1+1 = 4."
a(5) = 5, the number of 1's in "1+1+1+1+1 = 5."
a(6) = 5, since there are 5 1's in "((1+1)*(1+1+1)) = 6."
a(7) = 6, since there are 6 1's in "1+(((1+1)*(1+1+1))) = 7."
a(8) = 5, since there are 5 1's in "(1+1)^(1+1+1) = 8."
a(9) = 5, since there are 5 1's in "(1+1+1)^(1+1) = 9."
a(10) = 6 since there are 6 1's in "1+((1+1+1)^(1+1)) = ten.
a(11) = 2 since there are 2 1's in "1#1 = eleven."
a(12) = 3 since there are 3 1's in "1+(1#1) = twelve."
a(13) = 4 since there are 4 1's in "1+1+(1#1) = thirteen."
a(14) = 5 since there are 5 1's in "1+1+1+(1#1) = fourteen."
a(16) = 6 since there are 6 1's in "(1+1+1+1)^(1+1)."
a(17) = 7 since there are 7 1's in "1+((1+1+1+1)^(1+1))."
a(18) = 6 since there are 6 1's in "1#((1+1)^(1+1+1))."
a(19) = 6 since there are 6 1's in "1#((1+1+1)^(1+1))."
a(20) = 7 since there are 7 1's in "(1#1)+((1+1+1)^(1+1))."
a(21) = 3 since there are 3 1's in "(1+1)#1."
a(22) = 4 since 22 = (1+1)*(1#1) = (1#1)+(1#1) = (1+1)#(1+1).

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Index to sequences related to the complexity of n

Cf. A003037, A025280, A005520, A005245, A005421, A117618.

with(numtheory):
a:= proc(n) option remember; local r; `if`(n=1, 1, min(
       seq(a(i)+a(n-i), i=1..n-1),
       seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
       seq(`if`(cat("", n)[i+1]<>"0", a(iquo(n, 10^(length(n)-i),
           'r'))+a(r), NULL), i=1..length(n)-1),
       seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
           i=ifactors(n)[2]))) minus {0, 1})))
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Nov 06 2013

A117618 Least number with complexity height of n, under integer complexity A005245.

Original entry on oeis.org

1, 6, 7, 10, 22, 683

Offset: 1

Jonathan Vos Post, Apr 07 2006

Consider the recursion: A005245(n), A005245(A005245(n)), A005245(A005245(A005245(n))), ... which we know is finite before reaching a fixed point, as A005245(n) <= n. The number of steps needed to reach such a fixed point is the complexity height of n (with respect to the A005245 measure of complexity, there being others in the OEIS).

a(7) >= 872573642639 = A005520(89). - David A. Corneth, May 06 2024

			a(1) = 1 because the A005245 complexity of 1 is 1, already giving a fixed point.
a(2) = 6 because it is the smallest x such that A005245(x) =/= x and A005245(x) = A005245(A005245(x)).
a(3) = 7 because 7 is the least number x with complexity 6, thus taking a further step of recursion to reach a fixed point.
a(4) = 10 because 10 is the least number with complexity 7.
a(5) = 22 because 22 is the least number with complexity 10.
a(6) = 683 because 683 is the least number with complexity 22.
a(7) = the least number with complexity 683.

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971.
R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
E. Pegg, Jr., Integer Complexity.
Eric Weisstein's World of Mathematics, Integer Complexity.
Index to sequences related to the complexity of n

Cf. A003037, A003313, A005245, A005421, A005520, A025280, A061373, A064097, A076091, A076142.

a(n) = least k such that A005245^(n)(k) = A005245^(n-1)(k) but (if n>1) A005245^(n-1)(k) != A005245^(n-2)(k), where ^ denotes repeated application.

For n >= 3, a(n) = A005520(a(n-1)). - Max Alekseyev, May 06 2024

a(2)=6 inserted by Giovanni Resta, Jun 15 2016

Edited by Max Alekseyev, May 06 2024

A265360 Second smallest number of complexity n: second smallest number requiring n 1's to build using + and *.

Original entry on oeis.org

6, 8, 12, 13, 19, 25, 29, 43, 53, 67, 94, 131, 173, 214, 269, 359, 479, 713, 863, 1277, 1499, 2099, 3019, 3833, 5639, 7103, 10463, 12527, 18899, 22643, 33647, 45989, 60443, 88379, 103319, 166319, 206639, 280223, 384479, 543659, 755663, 1020599, 1316699, 1856159, 2556839, 3346559, 4895963, 6649199, 8666783

Offset: 5

Antti Karttunen, with terms computed by Janis Iraids, Dec 15 2015

nonn

As the first term of A005421 > 1 is A005421(5), the starting offset of this sequence is 5.

Only composites seem to be 6, 8, 12, 25, 94, 214, 713 and in many ways the sequence seems to have similar properties with A005520, the smallest number of complexity n.

Jānis Iraids, Table of n, a(n) for n = 5..89

Cf. A005245, A005421, A005520.

def aupton(nn):
  alst, R = [], {0: {1}} # R[n] is set reachable using n+1 1's (n ops)
  for n in range(1, nn):
    R[n]  = set(a+b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
    R[n] |= set(a*b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
    new = R[n] - R[n-1]
    if n >= 4: alst.append(min(new - {min(new)}))
  return alst
print(aupton(35)) # Michael S. Branicky, Jun 08 2021

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Original entry on oeis.org

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

Offset: 1

Jonathan Vos Post, Apr 08 2006

nonn

This problem has the optimal substructure property.

			a(1) = 1 because "1" has a single 1.
a(2) = 2 because "1+1" has two 1's.
a(3) = 2 because 3 = T(1+1) has two 1's.
a(6) = 2 because 6 = T(T(1+1)).
a(10) = 3 because 10 = T(T(1+1)+1).
a(12) = 4 because 12 = T(T(1+1)) + T(T(1+1)).
a(15) = 4 because 15 = T(T(1+1)+1+1).
a(21) = 2 because 21 = T(T(T(1+1))).
a(28) = 3 because 28 = T(T(T(1+1))+1).
a(55) = 3 because 55 = T(T(T(1+1)+1)).

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, 1971.
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Ed Pegg, Jr., Integer Complexity.
Eric Weisstein's World of Mathematics, Integer Complexity.
Wikipedia, Optimal substructure.

See also A023361 = number of compositions into sums of triangular numbers, A053614 = numbers that are not the sum of triangular numbers. Iterated triangular numbers: A050536, A050542, A050548, A050909, A007501.

Cf. A000217, A005245, A005520, A003313, A076142, A076091, A061373, A005421, A023361, A053614, A064097, A025280, A003037, A099129, A050536, A050542, A050548, A050909, A007501.

a:= proc(n) option remember; local m; m:= floor (sqrt (n*2));
      if n<3 then n
    elif n=m*(m+1)/2 then a(m)
    else min (seq (a(i)+a(n-i), i=1..floor(n/2)))
      fi
    end:
seq (a(n), n=1..110);  # Alois P. Heinz, Jan 05 2011

a[n_] := a[n] = Module[{m = Floor[Sqrt[n*2]]}, If[n < 3, n, If[n == m*(m + 1)/2, a[m], Min[Table[a[i] + a[n - i], {i, 1, Floor[n/2]}]]]]];
Array[a, 110] (* Jean-François Alcover, Jun 02 2018, from Maple *)

I do not know how many of these entries have been proved to be minimal. - N. J. A. Sloane, Apr 15 2006

Corrected and extended by Alois P. Heinz, Jan 05 2011

A348083 Number of positive numbers that can be built with n ones using +, -, and *, and require at least n ones.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 2, 6, 6, 8, 13, 18, 21, 35, 45, 61, 90, 121, 162, 241, 323, 450, 638, 865, 1233, 1698, 2349, 3315, 4592, 6382, 8970, 12421, 17351, 24320, 33714, 47218, 65978, 91784, 128177, 179807, 249689, 349549, 489341, 681468, 953769, 1334490, 1860641, 2606043, 3643618, 5086481, 7124229, 9960420

Offset: 1

Glen Whitney, Sep 27 2021

nonn

a(n+1)/a(n) appears from the values through n=63 to be oscillating in a narrowing range around 7/5.

			For n=5, there are two numbers whose minimal expression using 1,+,-, and * uses five ones: 5 = 1+1+1+1+1 and 6 = (1+1)*(1+1+1), so a(5) = 2.
For n=10, there are eight numbers whose minimal expression uses ten ones: 22 = 3(2*3+1)+1, 23 = 2*2*2*3-1, 25 = 5*5, 26 = 3*3*3-1, 28 = 3*3*3+1, 30 = 2*3*5, 32 = 2*2*2*2*2, and 36 = 2*2*3*3. We use numbers k=1..5 in these expressions because each takes k ones to express. Note that n=10 is also the least n for which a(n) differs from A005421(n), which counts the solutions to A005245(k) = n.

Glen Whitney, Table of n, a(n) for n = 1..64 (This file produced with the same C code that generated A348069, simply with division eliminated from the loop over operators.)

Cf. A005421, A091333, A005245.

from functools import cache
@cache
def f(m):
    if m == 0: return set()
    if m == 1: return {1}
    out = set()
    for j in range(1, m//2+1):
        for x in f(j):
            for y in f(m-j):
                out.update([x + y, x * y])
                if x != y: out.add(abs(x-y))
    return list(out)
def a(n): return len(f(n)) - len(f(n-1))
print([a(n) for n in range(1, 33)]) # Michael S. Branicky, Sep 27 2021

a(n) = |{k : A091333(k) = n}|.

cp's OEIS Frontend

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

A005520 Smallest number of complexity n: smallest number requiring n 1's to build using + and *.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

MATLAB

Maple

Mathematica

Python

Extensions

A048249 Number of distinct values produced from sums and products of n unity arguments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A003037 Smallest number of complexity n: smallest number requiring n 1's to build using +, * and ^.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Extensions

A182002 Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Python

Extensions

A133344 Complexity of the number n, counting 1's and built using +, *, ^ and # representing concatenation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A117618 Least number with complexity height of n, under integer complexity A005245.