Alternating Power Fibonacci Sequence
Python 2, 30 bytes
f=lambda n:n<1or f(n/4)-f(n/2)
Try it online!
One-indexed.
The sequence felt like a puzzle, something that Dennis generated by having a short way to express it. The power-of-two repetitions suggest recursing by bit-shifting (floor-dividing by 2). The alternating-sign Fibonacci recursion f(n)=f(n-2)-f(n-1)
can be adapted to bitshift in place of decrementing. The base case works out nicely because everything funnels to n=0
.
Jelly, 5 bytes
BLCÆḞ
Try it online!
How?
Extending the Fibonacci series back into negative indexes such that the relation f(i) = f(i-2) + f(i-1)
still holds:
i ... -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 4 5 ...
f(i) ... -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 ...
Going back from i=0
the numbers are those we need to repeat 2n-1 times, and Jelly's Fibonacci built-in, ÆḞ
, will calculate these.
We can find the -i
(a positive number) that we need by taking the bit-length of n
and subtracting 1
.
Since we want i
(a negative number) we can instead perform 1-bitLength
and Jelly has an atom for 1-x
, C
, the complement monad.
BLCÆḞ - Main link: n e.g. 500
B - convert n to a binary list [1,1,1,1,1,0,1,0,0]
L - get the length 9
C - complement -8
ÆḞ - Fibonacci -21
Mathematica, 43 36 24 bytes
Fibonacci@-Floor@Log2@#&
7 bytes saved thanks to @GregMartin, and a further 12 thanks to @JungHwanMin.