Alternating Fibonacci

Question

In the alternating Fibonacci sequence, you first start with 1 and 1 as usual.

However, instead of always adding the last two values to get the next number, you alternate starting with adding, and every other time you subtract instead.

The sequence starts like this:

1
1
2    # 1 + 1
-1   # 1 - 2
1    # 2 + -1
-2   # -1 - 1
-1   # 1 + -2
-1   # -2 - -1
-2   # -1 + -1
1    # -1 - -2
-1   # -2 + 1
2    # 1 - -1
1    # -1 + 2
1    # 2 - 1

etc.

^{Notice that after it starts over once it gets to 1 and 1 again.}

Given a number N, print the Nth term of the alternating fibonacci sequence.

Remember, this is code-golf, so the code with the smallest number of bytes wins.

Do the first two 1 values count as initial values for the output? Or do we start directly with the 2? — Luis Mendo, Commented Nov 8, 2016 at 23:58

ETHproductions · Accepted Answer · 2016-11-09 02:09:43Z

17

JavaScript (ES6), 25 bytes

n=>"334130110314"[n%12]-2

0-indexed. You can shorten the string with a slightly recursive version, though it adds 6 bytes:

f=n=>"3341301"[n]-2||f(13-n%12)

This is still shorter than the definitive recursive formula:

f=n=>n<2||f(n-2)+f(n-1)*(-n%2|1)

edited Nov 9, 2016 at 2:09

answered Nov 8, 2016 at 23:53

ETHproductions

50.1k6 gold badges94 silver badges240 bronze badges

Add a comment |

xnor · Accepted Answer · 2016-11-09 00:51:09Z

8

Python, 31 bytes

lambda n:2-33107256/5**(n%12)%5

Doesn't bother trying to compute the value. Just looks in up in the peroidic length-12 list [1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2], which is compressed in base 5.

Compare to a recursive solution (37 bytes) with True's for 1:

f=lambda n:n<2or(-1)**n*f(n-1)+f(n-2)

or to string storage

lambda n:int('334130110314'[n%12])-2

or an attempt at an arithmetical expression.

lambda n:4**n%7%3*(-1)**((n+n%2*4)/6)

edited Nov 9, 2016 at 0:51

answered Nov 9, 2016 at 0:08

xnor

147k26 gold badges279 silver badges652 bronze badges

Add a comment |

Adnan · Accepted Answer · 2016-11-09 01:38:41Z

7

Oasis, 10 bytes

Reminds me to implement some more built-ins :p. The input is 0-indexed.

Code:

n>2%x<*c+V

Translated version:

a(n) = (2*((n+1)%2)-1) * a(n-1) + a(n-2)
a(1) = 1
a(0) = 1

And calculates the nth term.

Try it online!

edited Nov 9, 2016 at 1:38

answered Nov 9, 2016 at 0:58

Adnan

44.5k6 gold badges82 silver badges246 bronze badges

Add a comment |

Adnan · Accepted Answer · 2016-11-09 02:28:38Z

5

05AB1E, 10 bytes

•É&Â†º•sèÍ

Uses the CP-1252 encoding. Try it online!

answered Nov 9, 2016 at 2:28

Adnan

44.5k6 gold badges82 silver badges246 bronze badges

\$\begingroup\$ I think I should start learning 05AB1E instead of Jelly. \$\endgroup\$
– Erik the Outgolfer
Commented Nov 10, 2016 at 12:26

Add a comment |

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

4

Pyth - 13 bytes

Base encoded once cycle series, modular indexed.

@-R2jC"
ûx"5

Try it online here.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 9, 2016 at 0:04

Maltysen

25.8k4 gold badges55 silver badges127 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2016-11-09 00:12:11Z

Jelly, 12 bytes

“½Ġ⁻S’b5_2⁸ị

TryItOnline!

1-based, given the first and second values are 1.

Not sure if this is shorter yet, but for this I noted that the series has a period of 12:
[1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2]

So, I took that and added 2 to give
[3, 3, 4, 1, 3, 0, 1, 1, 0, 3, 1, 4]
then converted that as a base 5 number to base 250, to give:
[11, 197, 140, 84]
(which is 184222584).

“½Ġ⁻S’b5_2⁸ị - Main link: n
“½Ġ⁻S’       - base 250 number      184222584
      b5     - convert to base 5   [3, 3, 4, 1, 3, 0, 1, 1, 0, 3, 1, 4]
        _2   - subtract 2          [1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2]
          ⁸  - left argument, n
           ị - index into (1-based and modular)

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

4

Haskell, 33 26 bytes

a!b=a:b:(a+b)!(-a)
(1!1!!)

Recursive approach. 0-indexed. Try it on Ideone.
Saved 7 bytes thanks to xnor.

Usage:

Prelude> (1!1!!)11
2

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 9, 2016 at 15:38

Laikoni

26.3k6 gold badges52 silver badges115 bronze badges

\$\begingroup\$ Looks shorter to just do a!b=a:b:(a+b)!(-a). \$\endgroup\$
– xnor
Commented Nov 9, 2016 at 21:44

Add a comment |

Greg Martin · Accepted Answer · 2016-11-09 00:20:15Z

3

Mathematica, 40 bytes

Just creates a lookup table and accesses it cyclically, as in ETHproductions's answer. Unnamed function, 1-indexed.

Join[s={2,1,1,2,-1,1},-s][[#~Mod~12+1]]&

answered Nov 9, 2016 at 0:20

Greg Martin

16.2k4 gold badges21 silver badges72 bronze badges

Add a comment |

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

3

MATL, 17 16 15 bytes

'"Bl)e'F5Za2-i)

Input is 1-based.

Try it online!

Explanation

The sequence has period [1 1 2 -1 1 -2 -1 -1 -2 1 -1 2].

'"Bl)e     % Compressed array [1 1 2 -1 1 -2 -1 -1 -2 1 -1 2] with source 
           % alphabet [-2 -1 0 1 2]
F5Za       % Decompress with target alphabet [0 1 2 3 4]
2-         % Subtract 2 to transform alphabet into [-2 -1 0 1 2]
i)         % Input N and use as (modular, 1-based) index into the sequence

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 8, 2016 at 23:57

Luis Mendo

105k9 gold badges135 silver badges372 bronze badges

Add a comment |

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

WinDbg, 26 bytes

?(85824331b>>@$t0%c*3&7)-2

Input is passed in through the pseudo-register $t0. 0-indexed. +2 of each term in the sequence is stored in 3 bits making 85824331b.

How it works:

? (85824331b >> @$t0 % c * 3 & 7) - 2 ;*? Evalutes the expression. Shifts 85824331b to get
                                       *the 3 bits for the @$t0'th term (mod c (12) when
                                       *the sequence repeats). Bitwise AND by 7 to get the
                                       *desired 3 bits, finally subtract 2 since the terms
                                       *where stored as +2.

Sample output, a loop printing the first 14 values of the sequence:

0:000> .for(r$t0=0;@$t0<e;r$t0=@$t0+1){?(85824331b>>@$t0%c*3&7)-2}
Evaluate expression: 1 = 00000001
Evaluate expression: 1 = 00000001
Evaluate expression: 2 = 00000002
Evaluate expression: -1 = ffffffff
Evaluate expression: 1 = 00000001
Evaluate expression: -2 = fffffffe
Evaluate expression: -1 = ffffffff
Evaluate expression: -1 = ffffffff
Evaluate expression: -2 = fffffffe
Evaluate expression: 1 = 00000001
Evaluate expression: -1 = ffffffff
Evaluate expression: 2 = 00000002
Evaluate expression: 1 = 00000001
Evaluate expression: 1 = 00000001

Olivier Grégoire · Accepted Answer · 2016-11-09 09:46:24Z

3

Java, 32 bytes

n->"334130110314".charAt(n%12)-50

Since this is Java, the answer is 0-indexed.

Testing and ungolfed:

class Ideone {
  public static void main (String[] args) throws Exception {
    java.util.function.IntFunction f = n->"334130110314".charAt(n%12)-50;
    for (int i = 0; i < 12; i++) {
      System.out.printf("%d -> %d%n", i, f.apply(i));
    }
  }
}

Test on Ideone

edited Nov 9, 2016 at 9:46

answered Nov 9, 2016 at 9:40

Olivier Grégoire

14.4k3 gold badges32 silver badges56 bronze badges

Add a comment |

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

2

Mathematica, 45 41 38 bytes

Thanks to @MartinEnder for 3 bytes.

±0=±1=1;±n_:=±(n-2)+±(n-1)(1-2n~Mod~2)

0-indexed.

Usage

±5

-2

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 9, 2016 at 0:01

JungHwan Min

13.9k3 gold badges23 silver badges69 bronze badges

2

\$\begingroup\$ You can probably save three bytes by defining a unary operator ± instead of a function a. \$\endgroup\$
– Martin Ender
Commented Nov 9, 2016 at 8:32

Add a comment |

Brad Gilbert b2gills · Accepted Answer · 2016-11-09 03:19:35Z

1

Perl 6, 39 35 32 bytes

{(1,1,{|(($/=$^a+$^b),$b-$/)}...*)[$_]}

{(|(334130110314.comb X-2)xx*)[$_]}

{(|334130110314.comb xx*)[$_]-2}

{334130110314.substr($_%12,1)-2}

answered Nov 9, 2016 at 3:19

Brad Gilbert b2gills

13.3k1 gold badge18 silver badges36 bronze badges

Add a comment |

Pete Arden · Accepted Answer · 2016-11-09 13:01:06Z

1

C#, 117 Bytes

Golfed:

int A(int n){var f=new List<int>{0,1,1};for(int i=3;i<=n;i++){f.Add(i%2>0?f[i-1]+f[i-2]:f[i-2]-f[i-1]);}return f[n];}

Ungolfed:

public int A(int n)
{
  var f = new List<int> { 0, 1, 1 };

  for (int i = 3; i <= n; i++)
  {
    f.Add(i % 2 > 0 ? f[i - 1] + f[i - 2] : f[i - 2] - f[i - 1]);
  }

  return f[n];
}

Testing:

var alternatingFibonacci = new AlternatingFibonacci();
Console.WriteLine(alternatingFibonacci.B(10));
1

answered Nov 9, 2016 at 13:01

Pete Arden

1,2117 silver badges9 bronze badges

\$\begingroup\$ Compile to a Func<int, int> so public int A(int n) is now n=>, you can remove the braces around the for statement saving 2 bytes, you can pre increment the i in the loop i.e. ++i <= n and set i = 2 saving 3 bytes because it removes the i++ at the end of the statement \$\endgroup\$
– TheLethalCoder
Commented Nov 10, 2016 at 11:31
\$\begingroup\$ Also see my answer if you kept track of the previous variables instead of creating a list of them all it is a lot shorter \$\endgroup\$
– TheLethalCoder
Commented Nov 10, 2016 at 12:02

Add a comment |

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

1

R, 38 bytes

Uses the lookup table solution inspired by @ETHproductions JS answer.

c(s<-c(2,1,1,2,-1,1),-s)[scan()%%12+1]

Edit: Forgot to mention that this is 1-indexed.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 9, 2016 at 8:43

Billywob

3,50312 silver badges16 bronze badges

Add a comment |

score 1 · Accepted Answer · 2016-11-10 11:36:40Z

1

Actually, 22 bytes

34*@%"334130110314"E≈¬

Try it online!

Explanation:

34*@%"334130110314"E≈¬
34*@%                   input % 12
     "334130110314"E    get that character in the string
                    ≈¬  convert to int, subtract 2

edited Nov 10, 2016 at 11:36

answered Nov 10, 2016 at 11:21

user45941

Add a comment |

peech · Accepted Answer · 2016-11-10 15:18:59Z

1

Java 7, 88 82 79 bytes

golfed:

int f(int n){int c,i=0,a=1,b=1;for(;i<n;){c=i++%2>0?a-b:a+b;a=b;b=c;}return b;}

ungolfed:

int f(int n)
{
    int c, i = 0, a = 1, b = 1;
    for (; i < n;)
    {
        c = i++ % 2 > 0 ? a - b : a + b;
        a = b;
        b = c;
    }
    return b;
}

Try it online

edited Nov 10, 2016 at 15:18

answered Nov 10, 2016 at 11:45

peech

3091 silver badge4 bronze badges

1

\$\begingroup\$ Since you go the "logical" way, here are some hints: 1. you forgot to declare int as return type. 2. you can spare bytes by moving the assignment of 0 to the declaration of i: int c,i=0 and for(;i<n;){. 3. You can remove parenthesis around the ternary operator condition. \$\endgroup\$
– Olivier Grégoire
Commented Nov 10, 2016 at 15:12
1

\$\begingroup\$ @OlivierGrégoire thanks dude :) fixed. nice solution btw \$\endgroup\$
– peech
Commented Nov 10, 2016 at 15:20

Add a comment |

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

DC, 55 bytes

?sd[ln1+snly[[+2Q]sEln2%1=E-]xlyrsylnld>r]sr1sy0sn1lrxp

0-indexed.

?sd                                                     takes input and stores
                                                        it in register d

                                            1sy0sn1     stores 1 in register y
                                                        and 0 in register n and
                                                        appends 1 to the stack

   [ln1+snly                                            adds 1 to register n and
                                                        appends the value of
                                                        register y to the stack

            [[+2Q]sEln2%1=E-]                           adds or subtracts the
                                                        the two values on the
                                                        stack depending on
                                                        parity of n

                             xlyrsylnld>r]              does the rest of the
                                                        stuff required to store
                                                        the new values properly
                                                        and quits if it has
                                                        done enough iterations

                                          sr            stores the main macro
                                                        in register r

                                                   lrxp executes the macro and
                                                        prints the stack

Register d stores the index of the value. Register n counts the number of iterations completed. Register r stores the main macro. Register y stores the later value in the sequence, while the stack contains the earlier value in the sequence.

Visual explanation of whats going on in the big loop (assuming addition):

register: y=1     y=1   y=1    y=1   y=1    y=2
stack:     1      1 1    2     2 1   1 2     1
               ly     +     ly     r     sy

The check to determine whether to add or subtract takes the counter modulo two and uses this trick to make an if then else construction.

At the end the stack contains a single number, the desired value, which is printed with p.

(I'm new to dc, so I'd expect there are some obvious improvements to be made here.)

SuperJedi224 · Accepted Answer · 2016-11-09 02:22:48Z

0

ForceLang, 153 bytes

def s set
s a 1
s b 1
s p 1
s k io.readnum()
if k=0
goto b
label a
s c b.mult p
s c a+c
s a b
s b c
s p p.mult -1
s k k+-1
if k
goto a
label b
io.write a

answered Nov 9, 2016 at 2:22

SuperJedi224

12k1 gold badge45 silver badges68 bronze badges

Add a comment |

Destructible Lemon · Accepted Answer · 2016-11-09 03:52:30Z

Turtlèd, 35 bytes

#112-1_--_1-2#?:[*l+].(-r'1)(_"-2")

0 indexed

Explanation:

#112-1_--_1-2#                      the 12 values of sequence. - is -1, _ is -2
              ?:                    input a number and move right that many
                [*l+]               move back to the asterisk on start cell, 
                                    increment sting pointer by amount moved
                     .              write pointed char
                      (-r'1)        if it was -, move right, write 1
                            (_"-2") if it was _, write "-2"
      [print grid]

Try it online!

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

0

ABCR, 43 bytes

)AAB)ABB..A))A..A)AA(ABB.)A+A)))AiB5aAb(Bxo

Explanation: the first part ()AAB)ABB..A))A..A)AA(ABB.)A+A)))A) sets up queue A to contain [1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2], keeping all other queues empty. iB stores our desired term, and the loop 5aAb(Bx cycles through the the queue that many times. o prints the front of the queue as a number, which will then be our desired answer.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 9, 2016 at 10:05

Steven H.

2,99711 silver badges22 bronze badges

Add a comment |

Neil · Accepted Answer · 2016-11-09 17:17:06Z

Batch, 49 bytes

@cmd/cset/a"n=%1%%12,~!(n%%3)*(1|-!(n%%5*(n/4)))"

Takes input as a command-line parameter. Explanation: Closed form uses the following observations:

Sequence is cyclic with period 12
Every third term is ±2 while other terms are ±1
Terms after the third are negative except multiples of 5 (after reducing modulo 12)

We therefore start by reducing modulo 12 (to save 2 bytes). We then reduce modulo three and invert the result, which is 1 for multiples of 3 or 0 otherwise. We then bitwise not that value, giving us -2 for multiples of 3 or -1 otherwise. We then reduce modulo 5 and separately divide by 4, giving zero for terms 1, 2, 3, 5, 10 and 12 (0). Inverting and negating gives us -1 for those values and zero for other values. We then bitwise or that with 1 and multiply with the earlier calculation.

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

0

TI-Basic, 26 bytes

Unfortunately, very uninteresting approach. I could not find anything shorter. The list is 1-indexed.

Input :{1,1,2,-1,1,-2:augment(Ans,-Ans:Ans(X

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 9, 2016 at 23:41

Timtech

12.6k2 gold badges46 silver badges61 bronze badges

Add a comment |

TheLethalCoder · Accepted Answer · 2016-11-10 12:33:41Z

0

C#, 73 71 bytes

This uses 0-indexed values of n.

n=>{int a=1,b=1,i=0,r;for(;++i<n;){r=i%2>0?a+b:a-b;a=b;b=r;}return b;};

Formatted version:

Func<int, int> f = n =>
{
    int a = 1, b = 1, i = 0, r;

    for(; ++i < n;)
    {
        r = i % 2 > 0 ? a + b : a - b;
        a = b;
        b = r;
    }

    return b;
};

edited Nov 10, 2016 at 12:33

answered Nov 10, 2016 at 11:57

TheLethalCoder

7,23927 silver badges43 bronze badges

Add a comment |

Stack Exchange Network

Alternating Fibonacci

24 Answers 24

JavaScript (ES6), 25 bytes

Python, 31 bytes

Oasis, 10 bytes

05AB1E, 10 bytes

Pyth - 13 bytes

Jelly, 12 bytes

Haskell, 33 26 bytes

Mathematica, 40 bytes

MATL, 17 16 15 bytes

Explanation

WinDbg, 26 bytes

Java, 32 bytes

Testing and ungolfed:

Mathematica, 45 41 38 bytes

Perl 6, 39 35 32 bytes

C#, 117 Bytes

R, 38 bytes

Actually, 22 bytes

Java 7, 88 82 79 bytes

DC, 55 bytes

ForceLang, 153 bytes

Turtlèd, 35 bytes

Explanation:

Try it online!

ABCR, 43 bytes

Batch, 49 bytes

TI-Basic, 26 bytes

C#, 73 71 bytes

Your Answer

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

Linked

Hot Network Questions

24 Answers 24

JavaScript (ES6), 25 bytes

Python, 31 bytes

Oasis, 10 bytes

05AB1E, 10 bytes

Pyth - 13 bytes

Jelly, 12 bytes

Haskell, 33 26 bytes

Mathematica, 40 bytes

MATL, 17 16 15 bytes

Explanation

WinDbg, 26 bytes

Java, 32 bytes

Testing and ungolfed:

Mathematica, 45 41 38 bytes

Perl 6, 39 35 32 bytes

C#, 117 Bytes

R, 38 bytes

Actually, 22 bytes

Java 7, 88 82 79 bytes

DC, 55 bytes

ForceLang, 153 bytes

Turtlèd, 35 bytes

Explanation:

ABCR, 43 bytes

Batch, 49 bytes

TI-Basic, 26 bytes

C#, 73 71 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

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