A005520 -id:A005520 - cp's OEIS frontend

A319909 Number of distinct positive integers that can be obtained by iteratively adding any two or multiplying any two non-1 parts of an integer partition until only one part remains, starting with 1^n.

0, 1, 1, 1, 1, 2, 4, 5, 10, 15, 21, 34, 49, 68, 101, 142, 197, 280, 387, 538, 751, 1045, 1442, 2010, 2772, 3865, 5339, 7396, 10273, 14201, 19693

Offset: 0

Gus Wiseman, Oct 01 2018

			We have
   7 = 1+1+1+1+1+1+1,
   8 = (1+1)*(1+1+1)+1+1,
   9 = (1+1)*(1+1)*(1+1)+1,
  10 = (1+1+1+1+1)*(1+1),
  12 = (1+1+1)*(1+1+1+1),
so a(7) = 5.

Cf. A000792, A001970, A005520, A048249, A066739, A066815, A070960, A201163, A275870, A319850, A318948, A318949, A319912, A319913.

ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
mexos[ptn_]:=If[Length[ptn]==0,{0},Union@@Select[ReplaceListRepeated[{Sort[ptn]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_?(#>1&),mie___,y_?(#>1&),afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]];
Table[Length[mexos[Table[1,{n}]]],{n,30}]

A319912 Number of distinct pairs (m, y), where m >= 1 and y is an integer partition of n, such that m can be obtained by iteratively adding any two or multiplying any two non-1 parts of y until only one part (equal to m) remains.

Original entry on oeis.org

1, 2, 3, 5, 12, 30, 53, 128, 247, 493, 989, 1889, 3434, 6390, 11526, 20400, 35818, 62083, 106223, 180170

Offset: 1

Gus Wiseman, Oct 01 2018

			The a(6) = 30 pairs:
  1 <= (1)
  2 <= (2)
  2 <= (1,1)
  3 <= (3)
  3 <= (2,1)
  3 <= (1,1,1)
  4 <= (4)
  4 <= (2,2)
  4 <= (3,1)
  4 <= (2,1,1)
  4 <= (1,1,1,1)
  5 <= (5)
  5 <= (3,2)
  5 <= (4,1)
  5 <= (2,2,1)
  5 <= (3,1,1)
  5 <= (2,1,1,1)
  5 <= (1,1,1,1,1)
  6 <= (6)
  6 <= (3,2)
  6 <= (3,3)
  6 <= (4,2)
  6 <= (5,1)
  6 <= (2,2,1)
  6 <= (2,2,2)
  6 <= (3,1,1)
  6 <= (3,2,1)
  6 <= (4,1,1)
  6 <= (2,1,1,1)
  6 <= (2,2,1,1)
  6 <= (3,1,1,1)
  6 <= (1,1,1,1,1)
  6 <= (2,1,1,1,1)
  6 <= (1,1,1,1,1,1)

Cf. A000792, A001970, A005520, A048249, A066739, A066815, A275870, A319850, A318949, A319909, A319910, A319911, A319913.

ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
mexos[ptn_]:=If[Length[ptn]==0,{0},Union@@Select[ReplaceListRepeated[{Sort[ptn]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_?(#>1&),mie___,y_?(#>1&),afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]];
Table[Total[Length/@mexos/@IntegerPartitions[n]],{n,20}]

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

A181957 Smallest positive integer which cannot be calculated by an expression containing n binary operators (either add or multiply) whose operands are integers between 1 and 9; parenthesis allowed.

Original entry on oeis.org

10, 19, 92, 239, 829, 2831, 10061, 38231, 189311, 621791, 2853533, 11423579

Offset: 0

Derek M. Jones, Apr 03 2012

			a(4) = 239 because at least 4 operators are needed to calculate this value, e.g., (5*5+9)*7+1.

Derek M. Jones, R program for calculating values
Index to sequences related to the complexity of n

Cf. A181898, A181958, A181959, A181960.

Cf. A005520 (operand literal is always 1).

first(n)=my(op=[(x, y)->x+y, (x, y)->x*y], v=vector(n+1), t); v[1]=[1..9]; for(k=2, #v, my(u=[]); for(i=1, (k+1)\2, my(a=v[i], b=v[k-i]); t=Set(concat(apply(f->setbinop(f, a, b), op))); u=concat(u, t)); v[k]=setminus(Set(u), [0])); t=10; for(i=1, #v, while(setsearch(v[i], t), t++); v[i]=t); v;
print(first(7)) \\ Michael S. Branicky, Oct 19 2021 after Charles R Greathouse IV in A181898

def aupton(nn):
    alst = [10]
    R = {0: set(range(1, 10))}   # R[n] is set reachable using n ops
    for n in range(1, nn):
        R[n] = set()
        for i in range((n+1)//2):
            for a in R[i]:
                for b in R[n-1-i]:
                    R[n].update([a+b, a*b])
        k = 10
        while k in R[n]: k += 1  # n.b. R[n-1] <= R[n] due to * by 1
        alst.append(k)
    return alst
print(aupton(9)) # Michael S. Branicky, Oct 19 2021

a(5)-a(7) corrected by and a(8)-a(11) from Michael S. Branicky, Oct 19 2021

A255641 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, 29, 41, 58, 67, 101, 131, 173, 262, 346, 461, 617, 787, 1123, 1571, 2077, 2767, 4153, 5443, 7963, 10733, 13997, 21101, 27997, 36643, 49747, 72103, 99317, 143239, 179107, 260213

Offset: 1

Janis Iraids, Mar 01 2015

nonn

Until n = 10 the terms are equal to A005520(n) where subtraction is not allowed.

			a(11) = 29, because 23 = (1+1)*(1+1)*(1+1)*(1+1+1)-1, but 29 = ((1+1+1)*(1+1)+1)*(1+1)*(1+1)+1.

Janis Iraids, Table of n, a(n) for n = 1..81
Juris Čerņenoks, Jānis Iraids, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arXiv:1409.0446 [math.NT], 2014.
Index to sequences related to the complexity of n

Least inverse (or records) of A091333.

Cf. A005520, A005245, A173419.

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

A182061 Smallest number with "natural" logarithm n, cf. A061373.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 46, 47, 83, 94, 139, 167, 235, 283, 359, 517, 659, 719, 1081, 1319, 1439, 2209, 2878, 2879, 5756, 5758, 8637, 11516, 14395, 20147, 28790, 31669, 48943, 61993, 66217, 103823, 132434, 135313, 238957, 270626, 397303

Offset: 1

Reinhard Zumkeller, Apr 09 2012

nonn

Corresponding to A061373 like A005520 to A005245; A061373(a(n)) = n and A061373(m) < n for m < a(n).

Index to sequences related to the complexity of n

import Data.List (elemIndex)
import Data.Maybe (fromJust)
a182061 = (+ 1) . fromJust . (`elemIndex` a061373_list)

A253177 Numbers which can be expressed with fewer 1s using +, -, and * than with + and *.

Original entry on oeis.org

23, 47, 53, 59, 69, 71, 89, 94, 106, 107, 134, 141, 142, 143, 159, 161, 167, 177, 178, 179, 188, 191, 207, 212, 213, 214, 215, 227, 233, 239, 242, 251, 263, 265, 267, 268, 269, 282, 283, 284, 286, 287, 299, 311, 317, 318, 319, 321

Offset: 1

Charles R Greathouse IV, Mar 23 2015

nonn

Numbers n such that A005245(n) > A091333(n). Is it true that a(n) ~ n?

			23 = 2*3*4 - 1 = 3*(2*3 + 1) + 2 can be written with 10 1s using subtraction but requires 11 without, hence 23 is a member. Here the digits 2, 3, and 4 are used for clarity, but could be expanded to (1+1), (1+1+1), etc.

Charles R Greathouse IV, Table of n, a(n) for n = 1..3128
Index to sequences related to the complexity of n

Cf. A091333, A005520, A005245, A173419, A255641.

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

A048183 Least inverse of A048182.

Original entry on oeis.org

2, 3, 4, 5, 7, 10, 11, 17, 22, 29, 41, 58, 67, 101, 131, 173, 259, 346, 461, 617, 787, 1037, 1571, 2074, 2767, 3703, 5357, 7403, 9427, 12443, 16663, 22217, 33323, 44437, 63677, 88843, 113117, 149323, 219803, 298597, 399883, 533237, 771403, 1018483

Offset: 0

David W. Wilson

nonn

Also a(n) is the smallest integer that cannot be obtained by using the number 1 at most n+1 times and the operators +, -, *, /. - Koksal Karakus (karakusk(AT)hotmail.com), May 27 2002

			a(4)=7 because by using the number 1 at most five times we can write 1=1, 1+1=2, 1+1+1=3, 1+1+1+1+1=5, (1+1)*(1+1+1)=6 but we cannot obtain 7 in the same way.

Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis, and Karlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arxiv:1409.0446 [math.NT], 2014; see Table 2.
Index entries for similar sequences

Cf. A005520, A060315, A181898.

cp's OEIS Frontend

A319909 Number of distinct positive integers that can be obtained by iteratively adding any two or multiplying any two non-1 parts of an integer partition until only one part remains, starting with 1^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A319912 Number of distinct pairs (m, y), where m >= 1 and y is an integer partition of n, such that m can be obtained by iteratively adding any two or multiplying any two non-1 parts of y until only one part (equal to m) remains.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A181957 Smallest positive integer which cannot be calculated by an expression containing n binary operators (either add or multiply) whose operands are integers between 1 and 9; parenthesis allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Extensions

A255641 Smallest number requiring n 1's to build using +, * and -.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A182061 Smallest number with "natural" logarithm n, cf. A061373.

Views

Author

Keywords

Comments

Links

Programs

Haskell

A253177 Numbers which can be expressed with fewer 1s using +, -, and * than with + and *.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs