login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A297621 a(0) = 1; for n > 0, a(n) = 1 + Sum_{k = 1..n} 2^k a(floor(log_2(k))). 1

%I

%S 1,3,15,39,279,759,1719,3639,13623,33591,73527,153399,313143,632631,

%T 1271607,2549559,20834103,57403191,130541367,276817719,569370423,

%U 1154475831,2324686647,4665108279,9345951543,18707638071,37431011127,74877757239,149771249463

%N a(0) = 1; for n > 0, a(n) = 1 + Sum_{k = 1..n} 2^k a(floor(log_2(k))).

%H Robert P. Adkins, <a href="/A297621/b297621.txt">Table of n, a(n) for n = 0..999</a>

%H Robert Adkins, <a href="https://www.quora.com/Can-you-find-an-explicit-formula-for-the-runtime-recursion-of-T-n-sum_-k-0-lfloor-log_2-n-rfloor-2-k-*-T-k-and-T-0-1">Can you find an explicit formula for the runtime recursion of T(n) ...</a>, Quora.

%t a[0] := 1; a[n_] := a[n] = 1 + Sum[2^k a[Floor@ Log2@ k], {k, 1, n}]; Array[a[#] &, 28, 0] (* _Michael De Vlieger_, Jan 02 2018 *)

%o (Python)

%o from math import log

%o def exp_fit(n, a, b):

%o k = int(log(n, 2))

%o return 3 * (a[k] * (2 ** (n + 1)) - b[k])

%o def S(n):

%o if n == 0:

%o return 1

%o k = int(log(n, 2))

%o a = [0]

%o b = [-1]

%o for i in range(1,k + 1):

%o S_0 = exp_fit(i, a, b)

%o S_1 = exp_fit(2 ** i - 1, a, b)

%o a.append(S_0 / 3)

%o b.append(((2 ** 2 ** i) * S_0 - S_1) / 3)

%o return exp_fit(n, a, b)

%K nonn

%O 0,2

%A _Robert P. Adkins_, Jan 01 2018

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 29 01:40 EST 2021. Contains 349416 sequences. (Running on oeis4.)