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

A319975 Smallest number of complexity n with respect to the operations {1, shift, multiply}.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 10, 11, 14, 19, 22, 23, 38, 43, 58, 59, 89, 107, 134, 167, 179, 263, 347, 383, 537, 713, 719, 1103, 1319, 1439, 2099, 2879, 3833, 4283, 5939, 6299, 9059, 12239, 15118, 19079, 23039, 26459, 44879, 49559, 66239, 78839, 98999, 137339

Offset: 1

N. J. A. Sloane, Oct 11 2018

nonn

The shift operation here is also sometimes called successor, see A263283.

Note this complexity measure counts both operands (the ones) and operators (the shifts and multiplications), whereas most of the complexity measures in the crossrefs count only operands. However, in the presence of successor it would not make sense to count only operands, since any number can be expressed with a single occurrence of 1. - Glen Whitney, Oct 06 2021

			1 = 1 has complexity 1
2 = S1 has complexity 2
3 = SS1 has complexity 3
4 = SSS1 has complexity 4
5 = SSSS1 has complexity 5
6 = SSSSS1 has complexity 6
7 = SSSSSS1 has complexity 7
10 = S*SS1SS1 = shift(product of (3 and 3)) has complexity 8
(Note that 8 = *S1SSS1 has complexity 7)
11 = SS*SS1SS1 has complexity 9
14 = SS*SS1SSS1 has complexity 10

Michael S. Branicky, Table of n, a(n) for n = 1..67
Akshunna Shaurya Dogra, Minimal Representations of Natural Numbers Under a Set of Operators, arXiv preprint 1801.01360 [math.HO], Jan 2018.
Index to sequences related to the complexity of n.

Smallest number of complexity n (other definitions): A003037, A005520, A244743, A259466, and A265360.

Other definitions of the complexity of n: A005208, A005245, A025280, and A099053.

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

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