|
%I M1836 #31 Aug 11 2017 18:54:00
%S 0,2,8,22,50,110,226,464,938,1888,3794,7598,15208,30438,60890,121792,
%T 243606,487238,974488,1948998,3898034,7796078,15592168,31184358,
%U 62368754,124737534,249475080,498950182,997900402,1995800846,3991601704,7983203430,15966406898
%N a(n) = min_{k=1..n} (a(k-1) + 2^k*(n + a(n-k))); a(0) = 0.
%D M. V. Connolly and W. J. Knight, Search in an array in which probe costs grow exponentially or factorially, preprint, 1990.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Reinhard Zumkeller, <a href="/A006696/b006696.txt">Table of n, a(n) for n = 0..1000</a>
%H M. V. Connolly and W. J. Knight, <a href="/A006696/a006696.pdf">Search in an array in which probe costs grow exponentially or factorially</a>, preprint, 1990.
%o (PARI) geta(a, j) = if (j <= 0, 0, a[j]);
%o 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
%o (Haskell)
%o a006696 n = a006696_list !! (n-1)
%o a006696_list = 0 : f 1 [0] where
%o f u vs = w : f (u + 1) (w : vs) where
%o w = minimum $ zipWith (+)
%o (reverse vs) (zipWith (*) (tail a000079_list) (map (+ u) vs))
%o - _Reinhard Zumkeller_, May 08 2014
%Y Cf. A000079.
%K nonn,nice,easy
%O 0,2
%A _Jeffrey Shallit_, _N. J. A. Sloane_
%E More terms from _Michel Marcus_, Sep 09 2013
%E Offset changed to 0 by _Reinhard Zumkeller_, May 08 2014
|
