Alternating Power Fibonacci Sequence

Question

Definition

The Alternating Power Fibonacci Sequence is formed as follows.

Start with the empty sequence and set n to 1.
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.
If n is odd, change the sign of f_n.
Append 2^n-1 copies of f_n to the sequence.
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

As long as your algorithm works for arbitrarily large values of n, you can assume that it fits into your data type. — Dennis, Jan 31, 2017 at 18:56

xnor · Accepted Answer · 2017-01-31 19:30:56Z

22

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.

edited Jan 31, 2017 at 19:30

answered Jan 31, 2017 at 19:20

xnor

144k26 gold badges273 silver badges637 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2017-01-31 20:59:18Z

12

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

edited Jan 31, 2017 at 20:59

answered Jan 31, 2017 at 20:14

Jonathan Allan

103k7 gold badges62 silver badges270 bronze badges

\$\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

Add a comment |

martin · Accepted Answer · 2017-02-01 12:08:46Z

6

Mathematica, 43 36 24 bytes

Fibonacci@-Floor@Log2@#&

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

edited Feb 1, 2017 at 12:08

answered Jan 31, 2017 at 20:08

martin

1,3458 silver badges15 bronze badges

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

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Community · Accepted Answer · 2017-04-13 12:38:59Z

4

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)

edited Apr 13, 2017 at 12:38

CommunityBot

1

answered Jan 31, 2017 at 19:10

ETHproductions

49.9k6 gold badges93 silver badges239 bronze badges

Add a comment |

ovs · Accepted Answer · 2017-02-18 14:38:40Z

4

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!

edited Feb 18, 2017 at 14:38

answered Jan 31, 2017 at 18:49

ovs

58k3 gold badges42 silver badges154 bronze badges

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

Add a comment |

miles · Accepted Answer · 2017-01-31 20:55:45Z

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)

ETHproductions · Accepted Answer · 2017-01-31 20:59:24Z

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.

Community · Accepted Answer · 2017-04-13 12:39:13Z

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

smls · Accepted Answer · 2017-01-31 21:28:06Z

2

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.

answered Jan 31, 2017 at 21:28

smls

4,41214 silver badges19 bronze badges

Add a comment |

Community · Accepted Answer · 2017-04-13 12:39:06Z

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.

miles · Accepted Answer · 2017-02-05 19:23:28Z

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

Stack Exchange Network

Alternating Power Fibonacci Sequence

Definition

Task

Test cases (1-based)

Test cases (0-based)

12 Answers 12

Python 2, 30 bytes

Jelly, 5 bytes

How?

Mathematica, 43 36 24 bytes

MATL, 19 17 16 11 bytes

How it works

JavaScript (ES6), 33 bytes

Python 2, 83 82 79 bytes

Jelly, 9 bytes

Explanation

Japt, 6 bytes

How it works

05AB1E, 11 10 bytes

Perl 6, 53 bytes

Julia 0.5, 19 bytes

How it works

J, 18 bytes

Explanation

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
sequence
array
fibonacci
or ask your own question.

Hot Network Questions

Alternating Power Fibonacci Sequence

Definition

Task

Test cases (1-based)

Test cases (0-based)

12 Answers 12

Python 2, 30 bytes

Jelly, 5 bytes

How?

Mathematica, 43 36 24 bytes

MATL, 19 17 16 11 bytes

How it works

JavaScript (ES6), 33 bytes

Python 2, 83 82 79 bytes

Jelly, 9 bytes

Explanation

Japt, 6 bytes

How it works

05AB1E, 11 10 bytes

Perl 6, 53 bytes

Julia 0.5, 19 bytes

How it works

J, 18 bytes

Explanation

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
math
sequence
array
fibonacci
or ask your own question.