%I M0523 #111 Apr 10 2024 11:16:07
%S 1,2,3,4,5,7,10,11,17,22,23,41,47,59,89,107,167,179,263,347,467,683,
%T 719,1223,1438,1439,2879,3767,4283,6299,10079,11807,15287,21599,33599,
%U 45197,56039,81647,98999,163259,203999,241883,371447,540539,590399,907199
%N Smallest number of complexity n: smallest number requiring n 1's to build using + and *.
%C _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
%C Largest number of complexity n is given by A000792. - _David W. Wilson_, Oct 03 2005
%C 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
%C a(54)-a(89) are all primes. - _Janis Iraids_, Apr 21 2011
%C Previous observations (primes with property -1 mod 120) still hold. - _Martins Opmanis_, Oct 16 2009
%C 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
%C The sequence A265360 (second smallest number of complexity n) seems to have similar properties. - _Janis Iraids_ via _Antti Karttunen_, Dec 15 2015
%D R. K. Guy, Unsolved Problems in Number Theory, Sec. F26 (related material).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Janis Iraids, <a href="/A005520/b005520.txt">Table of n, a(n) for n = 1..89</a>
%H Kazuyuki Amano, <a href="https://doi.org/10.4230/LIPIcs.ISAAC.2022.29">Integer Complexity and Mixed Binary-Ternary Representation</a>, 33rd Int'l Symp. Alg. Comp. (ISAAC 2022) Leibniz Int'l Proc. Informatics (LIPIcs) Vol. 248.
%H J. Arias de Reyna, <a href="http://hdl.handle.net/11441/40419">Complejidad de los números naturales</a>, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250.
%H J. Arias de Reyna, <a href="/A005245/a005245_1.pdf">Complejidad de los números naturales</a>, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250. [Cached copy, with permission]
%H J. Arias de Reyna, <a href="https://arxiv.org/abs/2111.03345">Complexity of natural numbers</a>, arXiv:2111.03345 [math.NT], 2021. See also <a href="http://math.colgate.edu/~integers/y19/y19.pdf">Integers</a> (2024) Vol. 24, A19, p. 6.
%H J. Arias de Reyna and J. van de Lune, <a href="http://arxiv.org/abs/1404.1850">The question "How many 1's are needed?" revisited</a>, arXiv preprint arXiv:1404.1850 [math.NT], 2014.
%H Jānis Iraids, Kaspars Balodis, Juris Čerņenoks, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, <a href="http://arxiv.org/abs/1203.6462">Integer complexity: experimental and analytical results</a>, arXiv:1203.6462 [math.NT], 2012.
%H Ed Pegg Jr., <a href="http://www.mathpuzzle.com/MAA/17-Integer%20Complexity/mathgames_04_12_04.html">Math Games: Integer Complexity</a>, www.mathpuzzle.com, April 12, 2004.
%H D. A. Rawsthorne, <a href="http://www.fq.math.ca/Scanned/27-1/rawsthorne.pdf">How many 1's are needed?</a>, Fib. Quart. 27 (1989), 14-17.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IntegerComplexity.html">Integer Complexity</a>
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e Examples from Piotr Fabian:
%e 1 = 1, 1 "one": first 1, a(1) = 1
%e 2 = 1+1, 2 "ones": first 2, a(2) = 2
%e 3 = 1+1+1, 3 "ones": first 3, a(3) = 3
%e 4 = 1+1+1+1, 4 "ones": first 4, a(4) = 4
%e 5 = 1+1+1+1+1, 5 "ones": first 5, a(5) = 5
%e 6 = (1+1)*(1+1+1), 5 "ones"
%e 7 = 1+((1+1)*(1+1+1)), 6 "ones": first 6, a(6) = 7
%e 8 = (1+1)*(1+1+1+1), 6 "ones"
%e 9 = (1+1+1)*(1+1+1), 6 "ones"
%e 10 = 1+((1+1+1)*(1+1+1)), 7 "ones": first 7, a(7) = 10
%e 11 = 1+(1+(1+1+1)*(1+1+1)), 8 "ones": first 8, a(8) = 11
%e 12 = (1+1)*((1+1)*(1+1+1)), 7 "ones"
%p N:= 100000: # to get all terms <= N
%p R:= Vector(N):
%p R[1]:= 1: A[1]:= 1:
%p for n from 2 to N do
%p inds:= [seq(n-i,i=1..floor(n/2))];
%p m:= min(R[1..floor(n/2)] + R[inds]);
%p for d in select(`<=`,numtheory:-divisors(n),floor(sqrt(n))) minus {1} do
%p m:= min(m, R[d]+R[n/d])
%p od;
%p R[n]:= m;
%p if not assigned(A[m]) then A[m]:= n fi;
%p od:
%p seq(A[m],m=1..max(R)); # _Robert Israel_, Dec 14 2015
%t nn = 10000;
%t R = Table[0, nn];
%t R[[1]] = 1; Clear[A]; A[1] = 1;
%t For[n = 2, n <= nn, n++,
%t inds = Table[n-i, {i, 1, n/2}];
%t m = Min[R[[1 ;; Floor[n/2]]] + R[[inds]]];
%t Do[
%t m = Min[m, R[[d]] + R[[n/d]]], {d,
%t Select[Rest[Divisors[n]], # <= Sqrt[n]&]}
%t ];
%t R[[n]] = m;
%t If[!IntegerQ[A[m]], A[m] = n];
%t ];
%t Table[A[m], {m, 1, Max[R]}] (* _Jean-François Alcover_, Aug 05 2018, after _Robert Israel_ *)
%o See the Python program by Tim Peters at A005421.
%o (MATLAB)
%o N = 10^6;
%o fact = cell(1,N);
%o for n = 2:sqrt(N)
%o for m = [n^2:n:N]
%o fact{m} = [fact{m},n];
%o end
%o end
%o R = zeros(1,N);
%o R(1) = 1;
%o A(1) = 1;
%o mmax = 1;
%o for n = 2:N
%o m = min(R(1:floor(n/2)) + R([n-1:-1:ceil(n/2)]));
%o if numel(fact{n}) > 0
%o m = min(m, min(R(fact{n}) + R(n ./ fact{n})));
%o end
%o R(n) = m;
%o if m > mmax
%o A(m) = n;
%o mmax = m;
%o elseif A(m) == 0
%o A(m) = n;
%o end
%o end
%o A % _Robert Israel_, Dec 14 2015
%o (Python)
%o def aupton(nn):
%o alst, R = [1], {0: {1}} # R[n] is set reachable using n+1 1's (n ops)
%o for n in range(1, nn):
%o R[n] = set(a+b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
%o R[n] |= set(a*b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
%o alst.append(min(R[n] - R[n-1]))
%o return alst
%o print(aupton(35)) # _Michael S. Branicky_, Jun 08 2021
%Y Cf. A005245, A025280, A003037, A005421, A048183, A181898, A182061, A265360.
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_
%E Corrected and extended by _David W. Wilson_, May 1997
%E Extended to terms a(40)=163259 and a(41)=203999 by _John W. Layman_, Nov 03 1999
%E Further terms from Piotr Fabian (PCF(AT)who.net), Mar 30 2001
%E a(68)-a(89) from _Janis Iraids_, Apr 20 2011