login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A352961
a(0) = 0, a(1) = 1, and for any n > 1, a(n) = a(n-2^e) + a(n-2^(e+1)) with e as large as possible (e = A070939(n) - 2).
2
0, 1, 1, 2, 1, 3, 2, 5, 1, 4, 3, 7, 2, 7, 5, 12, 1, 5, 4, 9, 3, 10, 7, 17, 2, 9, 7, 16, 5, 17, 12, 29, 1, 6, 5, 11, 4, 13, 9, 22, 3, 13, 10, 23, 7, 24, 17, 41, 2, 11, 9, 20, 7, 23, 16, 39, 5, 22, 17, 39, 12, 41, 29, 70, 1, 7, 6, 13, 5, 16, 11, 27, 4, 17, 13
OFFSET
0,4
COMMENTS
This sequence is a variant of the Fibonacci sequence (A000045) with variable steps.
FORMULA
a(2*n) = a(n).
EXAMPLE
a(0) = 0 by definition.
a(1) = 1 by definition.
a(2) = a(2-2^0) + a(2-2^1) = a(1) + a(0) = 1 + 0 = 1.
a(3) = a(3-2^0) + a(3-2^1) = a(2) + a(1) = 1 + 1 = 2.
a(4) = a(4-2^1) + a(4-2^2) = a(2) + a(0) = 1 + 0 = 1.
a(5) = a(5-2^1) + a(5-2^2) = a(3) + a(1) = 2 + 1 = 3.
a(6) = a(6-2^1) + a(6-2^2) = a(4) + a(2) = 1 + 1 = 2.
a(7) = a(7-2^1) + a(7-2^2) = a(5) + a(3) = 3 + 2 = 5.
a(8) = a(8-2^2) + a(8-2^3) = a(4) + a(0) = 1 + 0 = 1.
PROG
(PARI) { for (n=1, #a=vector(75), print1 (a[n]=if (n==1, 0, n==2, 1, e=#binary(n-1)-2; a[n-2^e]+a[n-2^(e+1)]), ", ")) }
CROSSREFS
See A352964 for a similar sequence.
Sequence in context: A300383 A120250 A280689 * A116529 A368071 A169747
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Apr 11 2022
STATUS
approved