

A007077


Optimal cost of search tree for searching an ordered array of n elements with cost k of probing element k.
(Formerly M3379)


2



1, 4, 10, 19, 31, 47, 68, 92, 120, 153, 190, 232, 279, 332, 392, 454, 521, 593, 670, 753, 841, 936, 1036, 1141, 1252, 1370, 1494, 1625, 1763, 1909, 2063, 2216, 2376, 2542, 2713, 2890, 3074, 3264, 3460, 3663, 3872, 4088, 4310, 4540, 4776, 5021
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Table of n, a(n) for n=1..46.
M. V. Connolly and W. J. Knight, Search in an array in which probe costs grow exponentially or factorially, Preprint. (Annotated scanned copy)
William J. Knight, Search in an ordered array having variable probe cost, SIAM J. Comput. 17 (1988), no. 6, 12031214.
W. J. Knight, Letter to N. J. A. Sloane, Jul. 1991
Index entries for sequences related to rooted trees
Index entries for sequences related to trees


FORMULA

a(n) = m(n, 0) where m(0, d) = 0 and for n > 0, m(n, d) = min_{1 <= r <= n} {(r+d) * n + m(r1, d) + m(nr, r+d)} [from Knight].  Sean A. Irvine, Oct 07 2017


CROSSREFS

Cf. A007078.
Sequence in context: A005448 A301247 A037040 * A301202 A301021 A009895
Adjacent sequences: A007074 A007075 A007076 * A007078 A007079 A007080


KEYWORD

nonn


AUTHOR

N. J. A. Sloane, Mira Bernstein


EXTENSIONS

More terms from Sean A. Irvine, Oct 07 2017


STATUS

approved



