|
%I #27 Jun 02 2018 14:18:13
%S 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 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 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 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.
%C This problem has the optimal substructure property.
%D 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 R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
%H Alois P. Heinz, <a href="/A117632/b117632.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 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 Ed Pegg, Jr., <a href="http://library.wolfram.com/infocenter/MathSource/5175/">Integer Complexity.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IntegerComplexity.html">Integer Complexity.</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Optimal_substructure">Optimal substructure.</a>
%e a(1) = 1 because "1" has a single 1.
%e a(2) = 2 because "1+1" has two 1's.
%e a(3) = 2 because 3 = T(1+1) has two 1's.
%e a(6) = 2 because 6 = T(T(1+1)).
%e a(10) = 3 because 10 = T(T(1+1)+1).
%e a(12) = 4 because 12 = T(T(1+1)) + T(T(1+1)).
%e a(15) = 4 because 15 = T(T(1+1)+1+1)).
%e a(21) = 2 because 21 = T(T(T(1+1))).
%e a(28) = 3 because 28 = T(T(T(1+1))+1).
%e a(55) = 3 because 55 = T(T(T(1+1)+1)).
%p a:= proc(n) option remember; local m; m:= floor (sqrt (n*2));
%p if n<3 then n
%p elif n=m*(m+1)/2 then a(m)
%p else min (seq (a(i)+a(n-i), i=1..floor(n/2)))
%p fi
%p end:
%p seq (a(n), n=1..110); # _Alois P. Heinz_, Jan 05 2011
%t 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 Array[a, 110] (* _Jean-François Alcover_, Jun 02 2018, from Maple *)
%Y 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 Cf. A000217, A005245, A005520, A003313, A076142, A076091, A061373, A005421, A023361, A053614, A064097, A025280, A003037, A099129, A050536, A050542, A050548, A050909, A007501.
%K nonn
%O 1,2
%A _Jonathan Vos Post_, Apr 08 2006
%E I do not know how many of these entries have been proved to be minimal. - _N. J. A. Sloane_, Apr 15 2006
%E Corrected and extended by _Alois P. Heinz_, Jan 05 2011
|
