cp's OEIS Frontend

A368275 Fibonacci zig-zag function.

%I A368275 #47 Dec 21 2023 10:21:12
%S A368275 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 A368275 29,34,33,36,34,40,36,41,40,45,41,49,45,50,49,54,50,56,54,57,56,61,57,
%U A368275 63,61,64,63,68,64,70,68,71,70,75,71,77,75,78,77,82,78,86
%N A368275 Fibonacci zig-zag function.
%H A368275 The craft of coding, <a href="https://craftofcoding.wordpress.com/tag/zibonacci/">Weird recursive algorithms</a>, zib(n).
%H A368275 Thomas Scheuerle, <a href="/A368275/a368275_1.png">Plot of a(n) - (5/4)*n for n = 1..200</a>.
%H A368275 Thomas Scheuerle, <a href="/A368275/a368275.png">Plot of a(n) - (5/4)*n for n = 1..100000</a>.
%F A368275 a(0)=1 and a(1)=1 and a(2)=2.
%F A368275 a(2*n+1) = a(n) + a(n-1) + 1, for n>=1.
%F A368275 a(2*n) = a(n) + a(n+1) + 1, for n>=2.
%F A368275 From _Thomas Scheuerle_, Dec 19 2023: (Start)
%F A368275 a(4^n+1) = (5*4^n - 8)/4, for n > 1.
%F A368275 a(2*4^n-1) = (5*4^n - 8)/2, for n > 0. (End)
%t A368275 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 A368275 (Python)
%o A368275 from functools import cache
%o A368275 @cache
%o A368275 def a(n):
%o A368275   if n < 3: return [1,1,2][n]
%o A368275   x, y = (n-1)>>1, n>>1
%o A368275   if n & 1 == 1: return a(x) + a(x-1) + 1
%o A368275   else: return a(y) + a(y+1) + 1
%o A368275 print([a(n) for n in range(0,67)])
%o A368275 (MATLAB)
%o A368275 function a = A368275( max_n )
%o A368275      a = [1, 1, 2];
%o A368275      for m = 4:max_n
%o A368275          n = m-1;
%o A368275          if mod(n,2) == 0
%o A368275             a(m) = a(1 + (n/2)) + a(2 + (n/2)) + 1;
%o A368275          else
%o A368275             a(m) = a(1 + (n-1)/2) + a((n-1)/2) + 1;
%o A368275          end
%o A368275      end
%o A368275 end % _Thomas Scheuerle_, Dec 19 2023
%Y A368275 Cf. A000045, A083420, A016813.
%K A368275 nonn
%O A368275 0,3
%A A368275 _Darío Clavijo_, Dec 19 2023