A368275 - OEIS

%I #47 Dec 21 2023 10:21:12

%S 1,1,2,3,6,4,10,6,11,10,15,11,17,15,18,17,22,18,26,22,27,26,29,27,33,

%T 29,34,33,36,34,40,36,41,40,45,41,49,45,50,49,54,50,56,54,57,56,61,57,

%U 63,61,64,63,68,64,70,68,71,70,75,71,77,75,78,77,82,78,86

%N Fibonacci zig-zag function.

%H The craft of coding, <a href="https://craftofcoding.wordpress.com/tag/zibonacci/">Weird recursive algorithms</a>, zib(n).

%H Thomas Scheuerle, <a href="/A368275/a368275_1.png">Plot of a(n) - (5/4)*n for n = 1..200</a>.

%H Thomas Scheuerle, <a href="/A368275/a368275.png">Plot of a(n) - (5/4)*n for n = 1..100000</a>.

%F a(0)=1 and a(1)=1 and a(2)=2.

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

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

%F From _Thomas Scheuerle_, Dec 19 2023: (Start)

%F a(4^n+1) = (5*4^n - 8)/4, for n > 1.

%F a(2*4^n-1) = (5*4^n - 8)/2, for n > 0. (End)

%t a[0] = 1;a[1] = 1;a[2] = 2;a[n_Integer] := a[n] = Which[n == 0,1,n == 1,1,n == 2, 2,Mod[n, 2] == 1 && n >= 3, a[Quotient[(n-1),2]] + a[Quotient[(n-1),2]-1]+1,Mod[n,2] == 0 && n >= 4, a[Quotient[n,2]] + a[Quotient[n,2]+ 1]+1];result = Table[a[n],{n,0,66}] (* _James C. McMahon_, Dec 19 2023 *)

%o (Python)

%o from functools import cache

%o @cache

%o def a(n):

%o   if n < 3: return [1,1,2][n]

%o   x, y = (n-1)>>1, n>>1

%o   if n & 1 == 1: return a(x) + a(x-1) + 1

%o   else: return a(y) + a(y+1) + 1

%o print([a(n) for n in range(0,67)])

%o (MATLAB)

%o function a = A368275( max_n )

%o      a = [1, 1, 2];

%o      for m = 4:max_n

%o          n = m-1;

%o          if mod(n,2) == 0

%o             a(m) = a(1 + (n/2)) + a(2 + (n/2)) + 1;

%o          else

%o             a(m) = a(1 + (n-1)/2) + a((n-1)/2) + 1;

%o          end

%o      end

%o end % _Thomas Scheuerle_, Dec 19 2023

%Y Cf. A000045, A083420, A016813.

%K nonn

%O 0,3

%A _Darío Clavijo_, Dec 19 2023