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

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

nonn,nice,easy

Author

Jeffrey Shallit, N. J. A. Sloane

Extensions

More terms from Michel Marcus, Sep 09 2013

Offset changed to 0 by Reinhard Zumkeller, May 08 2014

Status

approved