A181898 -id:A181898 - cp's OEIS frontend

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

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

A288350 Lexically smallest string of n digits from 1...9, such that no formula using the single digits in the given order exists that evaluates to 0.

Original entry on oeis.org

1, 12, 124, 1251, 12721, 169896, 8985898

Offset: 1

Hugo Pfoertner, Jun 08 2017

The formula may use any combination of the four binary operators +, -, *, /, the unary minus and parentheses. All digits have to be used exactly once and in the given order. Concatenation of the digits is not allowed. 0/0 in the evaluation of expressions makes the result invalid.
The last term a(7)=8985898, which is the only string of 7 digits for which it is not possible to construct an expression with result 0, is conjectured to be the last sequence term, i.e. for all strings of 8 or more digits expressions with result 0 can be found.
The conjecture is almost trivially true. Since 8985898 is the only exception for strings of 7 digits, an 8 digit string containing 8985898 can only be of the form x8985898 or 8985898x. But since any of x898589 and 985898x /= 8985898 leads to a 7 digit string that can represent 0, one can always find a substring of length 7 representing 0 in a string of 8 or more digits. Therefore the sequence ends at a(7).

			a(3)=124: For all numbers starting with 11.. the formula can be chosen as (1-1)*..,
121: 1-2+1=0, 122: (1-2/2)=0, 123: 1+2-3=0, 124: 0 cannot by obtained by any valid formula.

IBM Research, Ponder This Challenge - June 2017, related problem for 7-digit numbers.

Cf. A000108 (number of ways to insert the parentheses), A181898, A288351, A288353, A288354, A288355, A288356.

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

A181958 Number of distinct values that can be generated by an expression containing n binary operators (any of add, subtract, multiply and divide) whose operands are any integer between 1 and 9; parenthesis allowed.

Original entry on oeis.org

9, 93, 931, 11644, 126436, 1443224

Offset: 0

Derek M. Jones, Apr 03 2012

			a(1) = 93 and the distinct values are -8, -7, -6, -5, -4, -3, -2, -1, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1, 9/8, 8/7, 7/6, 6/5, 5/4, 9/7, 4/3, 7/5, 3/2, 8/5, 5/3, 7/4, 9/5, 2, 9/4, 7/3, 5/2, 8/3, 3, 7/2, 4, 9/2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72, 81

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

Cf. A181898, A181957, A181959, A181960.

A181959 Number of distinct integers that can be generated by an expression containing n binary operators (any of add, subtract, multiply and divide) whose operands are any integer between 1 and 9; parenthesis allowed.

Original entry on oeis.org

9, 48, 236, 1274, 6489, 30229, 142320, 711955, 3601566

Offset: 0

Derek M. Jones, Apr 03 2012

nonn

			a(1)=48, the distinct values are -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 54 56 63 64 72 81

Derek M. Jones, R program to generate list
Index to sequences related to the complexity of n

Cf. A181898, A181957, A181958, A181960.

A181960 Number of distinct nonnegative integers that can be generated by an expression containing n binary operators (any of add, subtract, multiply and divide) whose operands are any integer between 1 and 9; parenthesis allowed.

Original entry on oeis.org

9, 40, 156, 740, 3668, 16948, 77861, 379084, 1889419

Offset: 0

Derek M. Jones, Apr 03 2012

			a(1)=40, the distinct values are:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 54 56 63 64 72 81

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

Cf. A181898, A181957, A181958, A181959.

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

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

A288350 Lexically smallest string of n digits from 1...9, such that no formula using the single digits in the given order exists that evaluates to 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A181958 Number of distinct values that can be generated by an expression containing n binary operators (any of add, subtract, multiply and divide) whose operands are any integer between 1 and 9; parenthesis allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

A181959 Number of distinct integers that can be generated by an expression containing n binary operators (any of add, subtract, multiply and divide) whose operands are any integer between 1 and 9; parenthesis allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

A181960 Number of distinct nonnegative integers that can be generated by an expression containing n binary operators (any of add, subtract, multiply and divide) whose operands are any integer between 1 and 9; parenthesis allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

A048183 Least inverse of A048182.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs