A297621 - OEIS

%I #35 Jan 03 2018 17:05:38

%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