A006696 - OEIS

A006696

a(n) = min_{k=1..n} (a(k-1) + 2^k*(n + a(n-k))); a(0) = 0.
(Formerly M1836)

0, 2, 8, 22, 50, 110, 226, 464, 938, 1888, 3794, 7598, 15208, 30438, 60890, 121792, 243606, 487238, 974488, 1948998, 3898034, 7796078, 15592168, 31184358, 62368754, 124737534, 249475080, 498950182, 997900402, 1995800846, 3991601704, 7983203430, 15966406898

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

REFERENCES

M. V. Connolly and W. J. Knight, Search in an array in which probe costs grow exponentially or factorially, preprint, 1990.

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

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

M. V. Connolly and W. J. Knight, Search in an array in which probe costs grow exponentially or factorially, preprint, 1990.

PROG

(PARI) geta(a, j) = if (j <= 0, 0, a[j]);

lista(nn) = {print1(0, ", "); a = vector(nn); for (i = 1, nn, amin = 0; for (k = 1, i, new = geta(a, k-1) + 2^k*(i + geta(a, i-k)); if (! amin, amin = new, amin = min(amin, new); ); ); print1(amin, ", "); a[i] = amin; ); } \\ Michel Marcus, Sep 09 2013, May 09 2014

(Haskell)

a006696 n = a006696_list !! (n-1)

a006696_list = 0 : f 1 [0] where

f u vs = w : f (u + 1) (w : vs) where

w = minimum $ zipWith (+)

(reverse vs) (zipWith (*) (tail a000079_list) (map (+ u) vs))

- Reinhard Zumkeller, May 08 2014

CROSSREFS

Cf. A000079.

Sequence in context: A212683 A346586 A094533 * A094939 A006732 A005803

Adjacent sequences: A006693 A006694 A006695 * A006697 A006698 A006699

KEYWORD