A368275 Fibonacci zig-zag function.

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, 29, 34, 33, 36, 34, 40, 36, 41, 40, 45, 41, 49, 45, 50, 49, 54, 50, 56, 54, 57, 56, 61, 57, 63, 61, 64, 63, 68, 64, 70, 68, 71, 70, 75, 71, 77, 75, 78, 77, 82, 78, 86

Offset: 0

Author

Darío Clavijo, Dec 19 2023

Keywords

• nonn

Links

• The craft of coding, Weird recursive algorithms, zib(n).
• Thomas Scheuerle, Plot of a(n) - (5/4)*n for n = 1..200.
• Thomas Scheuerle, Plot of a(n) - (5/4)*n for n = 1..100000.

Crossrefs

Cf. A000045, A083420, A016813.

Programs

MATLAB

function a = A368275( max_n )
     a = [1, 1, 2];
     for m = 4:max_n
         n = m-1;
         if mod(n,2) == 0
            a(m) = a(1 + (n/2)) + a(2 + (n/2)) + 1;
         else
            a(m) = a(1 + (n-1)/2) + a((n-1)/2) + 1;
         end
     end
end % Thomas Scheuerle, Dec 19 2023

Mathematica

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 *)

Python

from functools import cache
@cache
def a(n):
  if n < 3: return [1,1,2][n]
  x, y = (n-1)>>1, n>>1
  if n & 1 == 1: return a(x) + a(x-1) + 1
  else: return a(y) + a(y+1) + 1
print([a(n) for n in range(0,67)])

Formula

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

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

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

From Thomas Scheuerle, Dec 19 2023: (Start)

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

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