A005421 Number of numbers of complexity n, i.e., that can be built from n ones using + and *, and require at least that many ones.

1, 1, 1, 1, 2, 3, 2, 6, 6, 7, 14, 16, 20, 34, 42, 56, 84, 108, 152, 214, 295, 398, 569, 763, 1094, 1475, 2058, 2878, 3929, 5493, 7669, 10501, 14707, 20476, 28226, 39287, 54817, 75619, 105584, 146910, 203294, 283764, 394437, 547485, 763821, 1061367, 1476067, 2057708, 2861449

Offset: 1

Author

Simon Plouffe

Keywords

• nonn
• nice

References

• 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..75
• 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.
• Tim Peters, Python program to compute this sequence
• 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

Crossrefs

Cf. A005245 (complexity of n), A005520 (records).

Programs

Mathematica

terms = 30;
kmax = 60000;
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]]}]];
Clear[a]; a[_] = 0;
Do[n = cpx[k]; a[n] += 1, {k, 1, kmax}];
Array[a, terms] (* Jean-François Alcover, Aug 30 2018 *)

Extensions

More terms from Tim Peters (tim.one(AT)comcast.net), Nov 12 2004

a(43)-a(75) from Janis Iraids, Apr 20 2011

Name clarified by Glen Whitney, Oct 05 2021