%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
|