OFFSET
0,2
LINKS
Robert P. Adkins, Table of n, a(n) for n = 0..999
Robert Adkins, Can you find an explicit formula for the runtime recursion of T(n) ..., Quora.
MATHEMATICA
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 *)
PROG
(Python)
from math import log
def exp_fit(n, a, b):
k = int(log(n, 2))
return 3 * (a[k] * (2 ** (n + 1)) - b[k])
def S(n):
if n == 0:
return 1
k = int(log(n, 2))
a = [0]
b = [-1]
for i in range(1, k + 1):
S_0 = exp_fit(i, a, b)
S_1 = exp_fit(2 ** i - 1, a, b)
a.append(S_0 / 3)
b.append(((2 ** 2 ** i) * S_0 - S_1) / 3)
return exp_fit(n, a, b)
CROSSREFS
KEYWORD
nonn
AUTHOR
Robert P. Adkins, Jan 01 2018
STATUS
approved