cp's OEIS Frontend

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

%I A005520 M0523 #114 Feb 16 2025 08:32:28
%S A005520 1,2,3,4,5,7,10,11,17,22,23,41,47,59,89,107,167,179,263,347,467,683,
%T A005520 719,1223,1438,1439,2879,3767,4283,6299,10079,11807,15287,21599,33599,
%U A005520 45197,56039,81647,98999,163259,203999,241883,371447,540539,590399,907199
%N A005520 Smallest number of complexity n: smallest number requiring n 1's to build using + and *.
%C A005520 _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 A005520 Largest number of complexity n is given by A000792. - _David W. Wilson_, Oct 03 2005
%C A005520 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 A005520 a(54)-a(89) are all primes. - _Janis Iraids_, Apr 21 2011
%C A005520 Previous observations (primes with property -1 mod 120) still hold. - _Martins Opmanis_, Oct 16 2009
%C A005520 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 A005520 The sequence A265360 (second smallest number of complexity n) seems to have similar properties. - _Janis Iraids_ via _Antti Karttunen_, Dec 15 2015
%D A005520 R. K. Guy, Unsolved Problems in Number Theory, Sec. F26 (related material).
%D A005520 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005520 Janis Iraids, <a href="/A005520/b005520.txt">Table of n, a(n) for n = 1..89</a>
%H A005520 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 A005520 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 A005520 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 A005520 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 A005520 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 A005520 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 A005520 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 A005520 D. A. Rawsthorne, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/27-1/rawsthorne.pdf">How many 1's are needed?</a>, Fib. Quart. 27 (1989), 14-17.
%H A005520 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IntegerComplexity.html">Integer Complexity</a>
%H A005520 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A005520 Examples from Piotr Fabian:
%e A005520 1 = 1, 1 "one": first 1, a(1) = 1
%e A005520 2 = 1+1, 2 "ones": first 2, a(2) = 2
%e A005520 3 = 1+1+1, 3 "ones": first 3, a(3) = 3
%e A005520 4 = 1+1+1+1, 4 "ones": first 4, a(4) = 4
%e A005520 5 = 1+1+1+1+1, 5 "ones": first 5, a(5) = 5
%e A005520 6 = (1+1)*(1+1+1), 5 "ones"
%e A005520 7 = 1+((1+1)*(1+1+1)), 6 "ones": first 6, a(6) = 7
%e A005520 8 = (1+1)*(1+1+1+1), 6 "ones"
%e A005520 9 = (1+1+1)*(1+1+1), 6 "ones"
%e A005520 10 = 1+((1+1+1)*(1+1+1)), 7 "ones": first 7, a(7) = 10
%e A005520 11 = 1+(1+(1+1+1)*(1+1+1)), 8 "ones": first 8, a(8) = 11
%e A005520 12 = (1+1)*((1+1)*(1+1+1)), 7 "ones"
%p A005520 N:= 100000: # to get all terms <= N
%p A005520 R:= Vector(N):
%p A005520 R[1]:= 1: A[1]:= 1:
%p A005520 for n from 2 to N do
%p A005520   inds:= [seq(n-i,i=1..floor(n/2))];
%p A005520   m:= min(R[1..floor(n/2)] + R[inds]);
%p A005520   for d in select(`<=`,numtheory:-divisors(n),floor(sqrt(n))) minus {1} do
%p A005520     m:= min(m, R[d]+R[n/d])
%p A005520   od;
%p A005520   R[n]:= m;
%p A005520   if not assigned(A[m]) then A[m]:= n fi;
%p A005520 od:
%p A005520 seq(A[m],m=1..max(R)); # _Robert Israel_, Dec 14 2015
%t A005520 nn = 10000;
%t A005520 R = Table[0, nn];
%t A005520 R[[1]] = 1; Clear[A]; A[1] = 1;
%t A005520 For[n = 2, n <= nn, n++,
%t A005520   inds = Table[n-i, {i, 1, n/2}];
%t A005520   m = Min[R[[1 ;; Floor[n/2]]] + R[[inds]]];
%t A005520   Do[
%t A005520     m = Min[m, R[[d]] + R[[n/d]]], {d,
%t A005520     Select[Rest[Divisors[n]], # <= Sqrt[n]&]}
%t A005520   ];
%t A005520   R[[n]] = m;
%t A005520   If[!IntegerQ[A[m]], A[m] = n];
%t A005520 ];
%t A005520 Table[A[m], {m, 1, Max[R]}] (* _Jean-François Alcover_, Aug 05 2018, after _Robert Israel_ *)
%o A005520 See the Python program by Tim Peters at A005421.
%o A005520 (MATLAB)
%o A005520 N = 10^6;
%o A005520 fact = cell(1,N);
%o A005520 for n = 2:sqrt(N)
%o A005520   for m = [n^2:n:N]
%o A005520     fact{m} = [fact{m},n];
%o A005520   end
%o A005520 end
%o A005520 R = zeros(1,N);
%o A005520 R(1) = 1;
%o A005520 A(1) = 1;
%o A005520 mmax = 1;
%o A005520 for n = 2:N
%o A005520   m = min(R(1:floor(n/2)) + R([n-1:-1:ceil(n/2)]));
%o A005520   if numel(fact{n}) > 0
%o A005520     m = min(m, min(R(fact{n}) + R(n ./ fact{n})));
%o A005520   end
%o A005520   R(n) = m;
%o A005520   if m > mmax
%o A005520     A(m) = n;
%o A005520     mmax = m;
%o A005520   elseif A(m) == 0
%o A005520     A(m) = n;
%o A005520   end
%o A005520 end
%o A005520 A % _Robert Israel_, Dec 14 2015
%o A005520 (Python)
%o A005520 def aupton(nn):
%o A005520   alst, R = [1], {0: {1}} # R[n] is set reachable using n+1 1's (n ops)
%o A005520   for n in range(1, nn):
%o A005520     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 A005520     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 A005520     alst.append(min(R[n] - R[n-1]))
%o A005520   return alst
%o A005520 print(aupton(35)) # _Michael S. Branicky_, Jun 08 2021
%Y A005520 Cf. A005245, A025280, A003037, A005421, A048183, A181898, A182061, A265360.
%K A005520 nonn,nice
%O A005520 1,2
%A A005520 _N. J. A. Sloane_
%E A005520 Corrected and extended by _David W. Wilson_, May 1997
%E A005520 Extended to terms a(40)=163259 and a(41)=203999 by _John W. Layman_, Nov 03 1999
%E A005520 Further terms from Piotr Fabian (PCF(AT)who.net), Mar 30 2001
%E A005520 a(68)-a(89) from _Janis Iraids_, Apr 20 2011