Alternating Power Fibonacci Sequence

Question

Definition

The Alternating Power Fibonacci Sequence is formed as follows.

1. Start with the empty sequence and set n to 1.

2. Compute f_n, the n^th non-negative Fibonacci number, with repetitions.
   0 is the first, 1 is the second and the third, 2 is the fourth. All others are obtained by summing the two previous numbers in the sequence, so 3 = 1 + 2 is the fifth, 5 = 2 + 3 is the sixth, etc.

3. If n is odd, change the sign of f_n.

4. Append 2^n-1 copies of f_n to the sequence.

5. Increment n and go back to step 2.

These are the first one hundred terms of the APF sequence.

 0  1  1 -1 -1 -1 -1  2  2  2  2  2  2  2  2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
 5  5  5  5  5  5  5  5  5  5  5  5  5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8

Task

Write a full program or a function that takes a positive integer n as input and prints or returns the n^th term of the APF sequence.

If you prefer 0-based indexing, you can alternatively take a non-negative integer n and print or return the APF number at index n.

This is code-golf; may the shortest code in bytes win!

Test cases (1-based)

    1 ->    0
    2 ->    1
    3 ->    1
    4 ->   -1
    7 ->   -1
    8 ->    2
  100 ->   -8
  250 ->   13
  500 ->  -21
 1000 ->   34
11111 ->  233
22222 -> -377
33333 ->  610

Test cases (0-based)

    0 ->    0
    1 ->    1
    2 ->    1
    3 ->   -1
    6 ->   -1
    7 ->    2
   99 ->   -8
  249 ->   13
  499 ->  -21
  999 ->   34
11110 ->  233
22221 -> -377
33332 ->  610

Answer 1

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 2^n-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

Answer 2

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.

Answer 3

Mathematica, 43 36 24 bytes

Fibonacci@-Floor@Log2@#&

7 bytes saved thanks to @GregMartin, and a further 12 thanks to @JungHwanMin.

Answer 4

MATL, 19 17 16 11 bytes

lOiB"yy-]x&

Input is 1-based.

Try it online! Or verify all test cases.

How it works

For 1-based input n, let m be the number of digits in the binary expansion of n. The n-th term in the output sequence is the m-th term in the Fibonacci sequence, possibly with its sign changed.

One idea would be to iterate m times to compute terms of the Fibonacci sequence. This is easy with a for each loop using the array of binary digits. If the Fibonacci sequence were initiallized with 0, then 1 as usual, iterating m times would result in m+2 terms on the stack, so the top two numbers would have to be deleted. Instead, we initiallize with 1, then 0. That way the next generated terms are 1, 1, 2, ... and only one deletion is needed.

The sign could be dealt with by using another loop to change sign m times. But that's costly. It is better to integrate the two loops, which is done simply by subtracting instead of adding in the Fibonacci iteration.

l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack

Answer 5

Python 2, 83 82 79 bytes

def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1)

Try it online!

Answer 6

JavaScript (ES6), 33 bytes

f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p

1-indexed.

A port of xnor's answer would be 23:

f=n=>n<1||f(n/4)-f(n/2)

Answer 7

Jelly, 9 bytes

BLµ’ÆḞN⁸¡

Uses one-based indexing.

Try it online!

Explanation

This method works if your Fibonacci function only supports non-negative arguments.

BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1)

Answer 8

Japt, 6 bytes

Mg1-¢l

Test it online!

How it works

As mentioned in other answers, the n^th term in the alternating-sign Fibonacci series is the same as the -n^th term in the regular series. n can be found by taking the bit-length of the input and subtracting one; negating this results in 1 minus the bit-length.

Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index.

Answer 9

05AB1E, 11 10 bytes

Uses 1-based indexing

05AB1E's Fibonacci function returns positive fib numbers less than n, meaning we'd have to generate more than necessary, get the correct one by index and then calculate the sign. So I doubt any method based around that will be shorter than calculating the numbers iteratively.

Uses the realisation that we can initialize the stack with 1, 0 reversed to handle the case when n=1 as described in Luis Mendo's MATL answer.

XÎbgG‚D«`-

Try it online!

Explanation

X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list 
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements

Answer 10

Julia 0.5, 19 bytes

!n=n<1||!(n/=4)-!2n

Try it online!

How it works

This uses the same formula as @xnor's Python answer. The recurrence relation
g(n) = g(n-2) + g(n-1) generates the negative terms of the Fibonacci sequence, which equal the positive terms with alternating signs. From anywhere in a run of 2^k repetitions of the same number, we can pick any repetition of the previous run of 2^k-1 numbers and the run of 2^k-2 numbers before those by dividing the index by 2 and 4.

Rather than the straightforward

f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes

we can redefine an operator for our purposes. Also, f will work just as fine with floats, so we get

!n=n<1||!(n/4)-!(n/2)   # 21 bytes

Finally, if we update n with a division by 4, wwe can write n/2 as 2n and omit a pair of parens, leading to the 19-byte function definition in this answer.

Answer 11

Perl 6, 53 bytes

{flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]}

Straightforward implementation of the sequence, the way it was described.
Zero-based.

Answer 12

J, 18 bytes

(%>:-*:)t.@<:@#@#:

Uses one-based indexing. Takes an input integer n > 0 and computes floor(log2(n)) by finding the length of its binary representation and then decrements that value by one. It then finds the floor(log2(n))-1^th coefficient of the generating function x/(1 + x - x²) which is the g.f for the negative-indexed Fibonacci values.

Try it online!

Explanation

(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value