The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A246878 a(0) = 1, then a(n) = sum(a(k), k = floor(log_2(n)) .. n - 1). 1
 1, 1, 1, 2, 3, 6, 12, 24, 47, 94, 188, 376, 752, 1504, 3008, 6016, 12030, 24060, 48120, 96240, 192480, 384960, 769920, 1539840, 3079680, 6159360, 12318720, 24637440, 49274880, 98549760, 197099520, 394199040, 788398077 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS a(n) = Theta(2^n), and more precisely, for n >= 4, (13/16)*(3/16)2^n <= a(n) <= (3/16)*2^n. Indeed, from the formula, one gets a(n) <= (3/16)*2^n, and injecting this in the formula, one gets a(n) >= 2*a(n - 1) - (3/32)*n. Then by induction, and using the formula sum(k*2^k, k = 1 .. n) = (n - 1)*2^(n + 1) + 2, one obtains a(n) >= (13/16)*(3/16)2^n + (3/32)*n + (3/8). LINKS Reinhard Zumkeller, Table of n, a(n) for n = 0..1000 W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216, 2015 FORMULA If n >= 1 is not a power of 2, then a(n) = 2*a(n - 1), and if k >= 1, then a(2^k) = 2*a(2^k - 1) - a(k - 1). EXAMPLE a(2) = a(1) = a(0) = 1. a(3) = a(2) + a(1) = 2. a(4) = a(3) + a(2) = 3. a(5) = a(4) + a(3) + a(2) = 6. PROG (Haskell) import Data.List (genericDrop) a246878 n = a246878_list !! n a246878_list = 1 : f [1] a000523_list where    f xs (k:ks) = y : f (xs ++ [y]) ks where y = sum \$ genericDrop k xs -- Reinhard Zumkeller, Sep 16 2014 CROSSREFS Cf. A000523. Sequence in context: A124313 A049890 A262236 * A251709 A293340 A251714 Adjacent sequences:  A246875 A246876 A246877 * A246879 A246880 A246881 KEYWORD nonn,easy AUTHOR Benoit Jubin, Sep 06 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 18 04:26 EST 2022. Contains 350410 sequences. (Running on oeis4.)