login
A327665
Fibonacci with binary selection.
1
0, 1, 1, 2, 3, 6, 11, 20, 34, 56, 121, 244, 481, 938, 1832, 3540, 6757, 12708, 23410, 42328, 73764, 122889, 275122, 408967, 832560, 1580364, 2834653, 5044480, 8652446, 13975133, 29832886, 58354102, 112803422, 215061934, 401711254, 737267883, 1313954863, 2259026414
OFFSET
0,4
FORMULA
a(n) = a(n-1) + Sum_{i=0..e(a(n-1))} b(a(n-1), e(a(n-1))-i)*a(n-i-2) where b(k, i) is the i-th bit in the binary expansion of k, with b(k, 0) being the low order bit of k, and e(k) = floor(log_2(k)). The initial terms are a(0) = 0, a(1) = 1. [edited by Michel Marcus, Sep 28 2019 and Michael S. Branicky, Jan 19 2021]
MATHEMATICA
e[n_] := Floor[Log2[n]]; a[0] = 0; a[1] = 1; a[2] = 1; a[n_] := a[n] = a[n - 1] + Sum[BitGet[a[n - 1], em - i] * a[n - 2 - i], {i, 0, (em = e[a[n - 1]])}]; Array[a, 38, 0] (* Amiram Eldar, Sep 28 2019 *)
PROG
(PARI) lista(nn) = {my(va = vector(nn)); va[1] = 0; va[2] = 1; va[3] = 1; for (n=4, nn, my(b = binary(va[n-1])); va[n] = va[n-1] + sum(k=1, #b, b[k]*va[n-k-1]); ); va; } \\ Michel Marcus, Sep 28 2019
(Python)
def aupton(nn):
alst = [0, 1, 1]
for n in range(3, nn+1):
b = list(map(int, bin(alst[n-1])[2:]))
alst.append(alst[n-1] + sum(bi*alst[n-i-2] for i, bi in enumerate(b)))
return alst[:nn+1]
print(aupton(37)) # Michael S. Branicky, Jan 19 2021
CROSSREFS
Sequence in context: A191629 A285553 A242842 * A131269 A358027 A090167
KEYWORD
nonn,base
AUTHOR
Hilarie Orman, Sep 21 2019
STATUS
approved