cp's OEIS Frontend

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

%I A117632 #32 Feb 16 2025 08:33:00
%S A117632 1,2,2,3,4,2,3,4,4,3,4,4,5,6,4,5,6,6,7,6,2,3,4,4,5,6,4,3,4,5,5,6,6,5,
%T A117632 6,4,5,6,6,7,8,4,5,6,4,5,6,6,5,6,6,7,8,8,3,4,5,5,6,7,5,6,6,7,6,4,5,6,
%U A117632 6,7,8,6,7,8,8,5,6,4,5,6,6,7,6,6,7,8,6,7,8,8,5,6,7,7,8,9,7,8,6,7,8,8
%N A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.
%C A117632 This problem has the optimal substructure property.
%D A117632 W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, 1971.
%D A117632 R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
%H A117632 Alois P. Heinz, <a href="/A117632/b117632.txt">Table of n, a(n) for n = 1..10000</a>
%H A117632 W. A. Beyer, M. L. Stein and S. M. Ulam, <a href="/A003037/a003037.pdf">The Notion of Complexity</a>. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
%H A117632 R. K. Guy, <a href="http://www.jstor.org/stable/2323338">Some suspiciously simple sequences</a>, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
%H A117632 Ed Pegg, Jr., <a href="http://library.wolfram.com/infocenter/MathSource/5175/">Integer Complexity.</a>
%H A117632 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IntegerComplexity.html">Integer Complexity.</a>
%H A117632 Wikipedia, <a href="http://en.wikipedia.org/wiki/Optimal_substructure">Optimal substructure.</a>
%e A117632 a(1) = 1 because "1" has a single 1.
%e A117632 a(2) = 2 because "1+1" has two 1's.
%e A117632 a(3) = 2 because 3 = T(1+1) has two 1's.
%e A117632 a(6) = 2 because 6 = T(T(1+1)).
%e A117632 a(10) = 3 because 10 = T(T(1+1)+1).
%e A117632 a(12) = 4 because 12 = T(T(1+1)) + T(T(1+1)).
%e A117632 a(15) = 4 because 15 = T(T(1+1)+1+1).
%e A117632 a(21) = 2 because 21 = T(T(T(1+1))).
%e A117632 a(28) = 3 because 28 = T(T(T(1+1))+1).
%e A117632 a(55) = 3 because 55 = T(T(T(1+1)+1)).
%p A117632 a:= proc(n) option remember; local m; m:= floor (sqrt (n*2));
%p A117632       if n<3 then n
%p A117632     elif n=m*(m+1)/2 then a(m)
%p A117632     else min (seq (a(i)+a(n-i), i=1..floor(n/2)))
%p A117632       fi
%p A117632     end:
%p A117632 seq (a(n), n=1..110);  # _Alois P. Heinz_, Jan 05 2011
%t A117632 a[n_] := a[n] = Module[{m = Floor[Sqrt[n*2]]}, If[n < 3, n, If[n == m*(m + 1)/2, a[m], Min[Table[a[i] + a[n - i], {i, 1, Floor[n/2]}]]]]];
%t A117632 Array[a, 110] (* _Jean-François Alcover_, Jun 02 2018, from Maple *)
%Y A117632 See also A023361 = number of compositions into sums of triangular numbers, A053614 = numbers that are not the sum of triangular numbers. Iterated triangular numbers: A050536, A050542, A050548, A050909, A007501.
%Y A117632 Cf. A000217, A005245, A005520, A003313, A076142, A076091, A061373, A005421, A023361, A053614, A064097, A025280, A003037, A099129, A050536, A050542, A050548, A050909, A007501.
%K A117632 nonn
%O A117632 1,2
%A A117632 _Jonathan Vos Post_, Apr 08 2006
%E A117632 I do not know how many of these entries have been proved to be minimal. - _N. J. A. Sloane_, Apr 15 2006
%E A117632 Corrected and extended by _Alois P. Heinz_, Jan 05 2011