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,3

Links

Table of n, a(n) for n=0..66.

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.

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)

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

Prog

(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)])
(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

Crossrefs

Cf. A000045, A083420, A016813.

Sequence in context: A194357 A165783 A354046 * A289272 A073318 A254047

Adjacent sequences: A368272 A368273 A368274 * A368276 A368277 A368278

Keyword

nonn

Author

Darío Clavijo, Dec 19 2023

Status

approved