This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2. 1

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 16 10:23 EDT 2019. Contains 327094 sequences. (Running on oeis4.)