A294044 a(0) = 0, a(1) = a(2) = 1; a(2*n) = 2*a(n) + a(n+1), a(2*n+1) = a(n) + a(n+1).

0, 1, 1, 2, 4, 3, 8, 6, 11, 7, 14, 11, 22, 14, 23, 17, 29, 18, 28, 21, 39, 25, 44, 33, 58, 36, 51, 37, 63, 40, 63, 46, 76, 47, 64, 46, 77, 49, 81, 60, 103, 64, 94, 69, 121, 77, 124, 91, 152, 94, 123, 87, 139, 88, 137, 100, 166, 103, 143, 103, 172, 109, 168, 122, 199, 123, 158, 111, 174, 110, 169

Offset: 0

Author

Ilya Gutkovskiy, Oct 22 2017

Keywords

• nonn

Examples

			a(0) = 0; a(1) = a(2) = 1;
a(3) = a(2*1+1) = a(1) + a(2) = 2;
a(4) = a(2*2) = 2*a(2) + a(3) = 4;
a(5) = a(2*2+1) = a(2) + a(3) = 3;
a(6) = a(2*3) = 2*a(3) + a(4) = 8, etc.
G.f. = x + x^2 + 2*x^3 + 4*x^4 + 3*x^5 + 8*x^6 + 6*x^7 + 11*x^8 + 7*x^9 + 14*x^10 + ... - _Michael Somos_, Jul 24 2023
		

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• Michael Gilleland, Some Self-Similar Integer Sequences
• Ilya Gutkovskiy, Extended graphical example

Crossrefs

Cf. A001622, A002487, A002878, A005248, A005592.

Programs

Maple

f:= proc(n) option remember;
  if n::odd then procname((n+1)/2)+procname((n-1)/2)
  else 2*procname(n/2)+procname(n/2+1)
  fi
end proc:
f(0):= 0: f(1):= 1: f(2):= 1:
map(f, [$0..100]); # Robert Israel, Oct 24 2017

Mathematica

a[0] = 0; a[1] = 1; a[2] = 1; a[n_] := If[EvenQ[n], 2 a[n/2] + a[(n + 2)/2],  a[(n - 1)/2] + a[(n + 1)/2]]; Table[a[n], {n, 0, 70}]

PARI

{a(n) = if(n<1, 0, n<3, 1, n%2, a(n\2) + a(n\2+1), 2*a(n\2) + a(n\2+1))}; /* Michael Somos, Jul 24 2023 */

Formula

a(n) = a(2*n) - a(2*n+1) for n > 1.

a(n+1) = 2*a(2*n+1) - a(2*n) for n > 1.

a(2^(k+1)) = floor(phi^(2*k+1)) = A002878(k), where phi is the golden ratio (A001622).

a(2^(k+1)+1) = phi^(2*k) + phi^(-2*k) = A005248(k).

a(2^(k+1)-1) = floor(phi^(2*k)) = A005592(k).

G.f. g(x) satisfies g(x) = (x + 2 + 1/x + 1/x^2)*g(x^2) - 1 - 2*x^2. - Robert Israel, Oct 24 2017