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

 

Logo
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

%I #20 May 04 2016 21:39:25

%S 1,1,1,2,3,6,12,24,47,94,188,376,752,1504,3008,6016,12030,24060,48120,

%T 96240,192480,384960,769920,1539840,3079680,6159360,12318720,24637440,

%U 49274880,98549760,197099520,394199040,788398077

%N a(0) = 1, then a(n) = sum(a(k), k = floor(log_2(n)) .. n - 1).

%C a(n) = Theta(2^n), and more precisely, for n >= 4, (13/16)*(3/16)2^n <= a(n) <= (3/16)*2^n.

%C 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).

%H Reinhard Zumkeller, <a href="/A246878/b246878.txt">Table of n, a(n) for n = 0..1000</a>

%H W. Kuszmaul, <a href="http://arxiv.org/abs/1509.08216">Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations</a>, arXiv preprint arXiv:1509.08216, 2015

%F 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).

%e a(2) = a(1) = a(0) = 1.

%e a(3) = a(2) + a(1) = 2.

%e a(4) = a(3) + a(2) = 3.

%e a(5) = a(4) + a(3) + a(2) = 6.

%o (Haskell)

%o import Data.List (genericDrop)

%o a246878 n = a246878_list !! n

%o a246878_list = 1 : f [1] a000523_list where

%o f xs (k:ks) = y : f (xs ++ [y]) ks where y = sum $ genericDrop k xs

%o -- _Reinhard Zumkeller_, Sep 16 2014

%Y Cf. A000523.

%K nonn,easy

%O 0,4

%A _Benoit Jubin_, Sep 06 2014

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 01:36 EDT 2024. Contains 371264 sequences. (Running on oeis4.)