|
|
A117632
|
|
Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.
|
|
1
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
This problem has the optimal substructure property.
|
|
REFERENCES
|
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.
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
|
|
LINKS
|
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, December 1971. [Annotated scanned copy]
|
|
EXAMPLE
|
a(1) = 1 because "1" has a single 1.
a(2) = 2 because "1+1" has two 1's.
a(3) = 2 because 3 = T(1+1) has two 1's.
a(6) = 2 because 6 = T(T(1+1)).
a(10) = 3 because 10 = T(T(1+1)+1).
a(12) = 4 because 12 = T(T(1+1)) + T(T(1+1)).
a(15) = 4 because 15 = T(T(1+1)+1+1)).
a(21) = 2 because 21 = T(T(T(1+1))).
a(28) = 3 because 28 = T(T(T(1+1))+1).
a(55) = 3 because 55 = T(T(T(1+1)+1)).
|
|
MAPLE
|
a:= proc(n) option remember; local m; m:= floor (sqrt (n*2));
if n<3 then n
elif n=m*(m+1)/2 then a(m)
else min (seq (a(i)+a(n-i), i=1..floor(n/2)))
fi
end:
|
|
MATHEMATICA
|
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]}]]]]];
|
|
CROSSREFS
|
Cf. A000217, A005245, A005520, A003313, A076142, A076091, A061373, A005421, A023361, A053614, A064097, A025280, A003037, A099129, A050536, A050542, A050548, A050909, A007501.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
I do not know how many of these entries have been proved to be minimal. - N. J. A. Sloane, Apr 15 2006
|
|
STATUS
|
approved
|
|
|
|