A294044 - OEIS

%I #16 Aug 02 2023 14:32:21

%S 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,

%T 51,37,63,40,63,46,76,47,64,46,77,49,81,60,103,64,94,69,121,77,124,91,

%U 152,94,123,87,139,88,137,100,166,103,143,103,172,109,168,122,199,123,158,111,174,110,169

%N 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).

%H Robert Israel, <a href="/A294044/b294044.txt">Table of n, a(n) for n = 0..10000</a>

%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>

%H Ilya Gutkovskiy, <a href="/A294044/a294044.jpg">Extended graphical example</a>

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

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

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

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

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

%F 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

%e a(0) = 0; a(1) = a(2) = 1;

%e a(3) = a(2*1+1) = a(1) + a(2) = 2;

%e a(4) = a(2*2) = 2*a(2) + a(3) = 4;

%e a(5) = a(2*2+1) = a(2) + a(3) = 3;

%e a(6) = a(2*3) = 2*a(3) + a(4) = 8, etc.

%e 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

%p f:= proc(n) option remember;

%p   if n::odd then procname((n+1)/2)+procname((n-1)/2)

%p   else 2*procname(n/2)+procname(n/2+1)

%p   fi

%p end proc:

%p f(0):= 0: f(1):= 1: f(2):= 1:

%p map(f, [$0..100]); # _Robert Israel_, Oct 24 2017

%t 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}]

%o (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 */

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

%K nonn

%O 0,4

%A _Ilya Gutkovskiy_, Oct 22 2017