A327665 Fibonacci with binary selection.

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

Links

Table of n, a(n) for n=0..37.

Hilarie Orman, C program for generating Fibonacci with binary selection

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

Cf. A000045, A007088.

Sequence in context: A191629 A285553 A242842 * A131269 A358027 A090167

Adjacent sequences: A327662 A327663 A327664 * A327666 A327667 A327668

Keyword

nonn,base

Author

Hilarie Orman, Sep 21 2019

Status

approved