25
\$\begingroup\$

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
Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Are there any constraints for n? \$\endgroup\$
    – Okx
    Jan 31, 2017 at 18:32
  • 2
    \$\begingroup\$ As long as your algorithm works for arbitrarily large values of n, you can assume that it fits into your data type. \$\endgroup\$
    – Dennis
    Jan 31, 2017 at 18:56
  • 1
    \$\begingroup\$ Does this have an OEIS number? \$\endgroup\$
    – Mindwin Remember Monica
    Feb 1, 2017 at 12:20
  • \$\begingroup\$ @Mindwin It does not. \$\endgroup\$
    – Dennis
    Feb 1, 2017 at 17:23

12 Answers 12

Reset to default
22
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
12
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I knew there was a shorter way but not by that much, thought it'd be 7 bytes with a way to remove µ and ⁸ \$\endgroup\$
    – miles
    Jan 31, 2017 at 20:21
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jonathan Allan
    Jan 31, 2017 at 20:37
  • 4
    \$\begingroup\$ Honestly, I'm surprised Jelly doesn't have a one-byte builtin to get the binary length of a number... \$\endgroup\$
    – ETHproductions
    Jan 31, 2017 at 20:50
6
\$\begingroup\$

Mathematica, 43 36 24 bytes

Fibonacci@-Floor@Log2@#&

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

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save a few bytes with Floor@Log2@#, and by writing Fibonacci[t=...] (and by removing the spaces in the last exponent). \$\endgroup\$
    – Greg Martin
    Jan 31, 2017 at 20:11
  • 1
    \$\begingroup\$ -12 bytes: Fibonacci@-Floor@Log2@#& -- Fibonacci can take negative arguments too (takes care of the sign for you). \$\endgroup\$
    – JungHwan Min
    Feb 1, 2017 at 5:23
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Whitespace not required at or -1. \$\endgroup\$
    – Yytsi
    Jan 31, 2017 at 19:25
3
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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))-1th coefficient of the generating function x/(1 + x - x2) 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
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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