cp's OEIS Frontend

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.

%I A005421 M0430 #43 Feb 16 2025 08:32:28
%S A005421 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 A005421 1094,1475,2058,2878,3929,5493,7669,10501,14707,20476,28226,39287,
%U A005421 54817,75619,105584,146910,203294,283764,394437,547485,763821,1061367,1476067,2057708,2861449
%N 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.
%D A005421 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005421 Janis Iraids, <a href="/A005421/b005421.txt">Table of n, a(n) for n = 1..75</a>
%H A005421 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 A005421 Tim Peters, <a href="/A005421/a005421.txt">Python program to compute this sequence</a>
%H A005421 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 A005421 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IntegerComplexity.html">Integer Complexity</a>
%H A005421 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%t A005421 terms = 30;
%t A005421 kmax = 60000;
%t A005421 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 A005421 Clear[a]; a[_] = 0;
%t A005421 Do[n = cpx[k]; a[n] += 1, {k, 1, kmax}];
%t A005421 Array[a, terms] (* _Jean-François Alcover_, Aug 30 2018 *)
%Y A005421 Cf. A005245 (complexity of n), A005520 (records).
%K A005421 nonn,nice
%O A005421 1,5
%A A005421 _Simon Plouffe_
%E A005421 More terms from Tim Peters (tim.one(AT)comcast.net), Nov 12 2004
%E A005421 a(43)-a(75) from _Janis Iraids_, Apr 20 2011
%E A005421 Name clarified by _Glen Whitney_, Oct 05 2021