%I M0430 #40 Oct 06 2021 08:26:57
%S 1,1,1,1,2,3,2,6,6,7,14,16,20,34,42,56,84,108,152,214,295,398,569,763,
%T 1094,1475,2058,2878,3929,5493,7669,10501,14707,20476,28226,39287,
%U 54817,75619,105584,146910,203294,283764,394437,547485,763821,1061367,1476067,2057708,2861449
%N Number of numbers of complexity n, i.e., that can be built from n ones using + and *, and require at least that many ones.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Janis Iraids, <a href="/A005421/b005421.txt">Table of n, a(n) for n = 1..75</a>
%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 Tim Peters, <a href="/A005421/a005421.txt">Python program to compute this sequence</a>
%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>
%t terms = 30;
%t kmax = 60000;
%t cpx[1] = 1; cpx[k_] := cpx[k] = Min[Sequence @@ Table[cpx[i] + cpx[k-i], {i, 1, k/2}], Sequence @@ Table[cpx[d] + cpx[k/d], {d, Divisors[k][[2 ;; -2]]}]];
%t Clear[a]; a[_] = 0;
%t Do[n = cpx[k]; a[n] += 1, {k, 1, kmax}];
%t Array[a, terms] (* _Jean-François Alcover_, Aug 30 2018 *)
%Y Cf. A005245 (complexity of n), A005520 (records).
%K nonn,nice
%O 1,5
%A _Simon Plouffe_
%E More terms from Tim Peters (tim.one(AT)comcast.net), Nov 12 2004
%E a(43)-a(75) from _Janis Iraids_, Apr 20 2011
%E Name clarified by _Glen Whitney_, Oct 05 2021
|