Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Definition

The Alternating Power Fibonacci Sequence is formed as follows.

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

  2. Compute fn, the nth 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 fn.

  4. Append 2n-1 copies of fn 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 nth 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 ; 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
share|improve this question
    
Are there any constraints for n? – Okx yesterday
2  
As long as your algorithm works for arbitrarily large values of n, you can assume that it fits into your data type. – Dennis yesterday
1  
Does this have an OEIS number? – Mindwin 18 hours ago
    
@Mindwin It does not. – Dennis 13 hours ago

11 Answers 11

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.

share|improve this answer
    
Huh, I thought f(n-2)-f(n-1) might give alternating signs but I didn't have time to try it. +1 – ETHproductions yesterday

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
share|improve this answer
    
I knew there was a shorter way but not by that much, thought it'd be 7 bytes with a way to remove µ and – miles yesterday
    
Your repeated negation was clever though, I was looking at powers of minus one, which adds a couple of bytes, until I recalled about the negative Fibonacci values and tried plugging them into Jelly's monad. – Jonathan Allan yesterday
4  
Honestly, I'm surprised Jelly doesn't have a one-byte builtin to get the binary length of a number... – ETHproductions yesterday

Mathematica, 43 36 24 bytes

Fibonacci@-Floor@Log2@#&

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

share|improve this answer
1  
You can save a few bytes with Floor@Log2@#, and by writing Fibonacci[t=...] (and by removing the spaces in the last exponent). – Greg Martin yesterday
1  
-12 bytes: Fibonacci@-Floor@Log2@#& -- Fibonacci can take negative arguments too (takes care of the sign for you). – JungHwan Min yesterday

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
share|improve this answer

Python, 83 82 bytes, 1 based

Try it online

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

ungolfed:

def f(n):
  l=len(bin(n))-2  # binary length of n
  a=0
  b=1
  for _ in range(l-1): # calculate the lth fibonacci number 1-based
    a,b=b,a+b
  sign = -1 if l%2==1 else 1 # The number is positive if the binary length is even
  return a*sign
share|improve this answer
    
Whitespace not required at or -1. – TuukkaX yesterday

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)
share|improve this answer

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)
share|improve this answer

Japt, 6 bytes

Mg1-¢l

Test it online!

How it works

As mentioned in other answers, the nth term in the alternating-sign Fibonacci series is the same as the -nth 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.
share|improve this answer

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
share|improve this answer

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.

share|improve this answer

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 2k repetitions of the same number, we can pick any repetition of the previous run of 2k-1 numbers and the run of 2k-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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.