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
Examples
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"
References
- 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).
Links
- 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
Programs
-
MATLAB
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 -
Maple
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 -
Mathematica
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 *) -
Python
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
Extensions
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
Comments