17
\$\begingroup\$

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 , so the code with the smallest number of bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Is the sequence 0-indexed or 1-indexed (or either one)? \$\endgroup\$ – Doorknob Nov 8 '16 at 23:47
  • \$\begingroup\$ @Doorknob Either one. Specify in your answer. \$\endgroup\$ – Oliver Ni Nov 8 '16 at 23:48
  • \$\begingroup\$ Can we return true for 1? \$\endgroup\$ – ETHproductions Nov 8 '16 at 23:57
  • \$\begingroup\$ Do the first two 1 values count as initial values for the output? Or do we start directly with the 2? \$\endgroup\$ – Luis Mendo Nov 8 '16 at 23:58
  • \$\begingroup\$ @LuisMendo The first two count. \$\endgroup\$ – Oliver Ni Nov 9 '16 at 0:01

24 Answers 24

17
\$\begingroup\$

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)
\$\endgroup\$
8
\$\begingroup\$

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)
\$\endgroup\$
7
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 10 bytes

•É&†º•sèÍ

Uses the CP-1252 encoding. Try it online!

\$\endgroup\$
  • \$\begingroup\$ I think I should start learning 05AB1E instead of Jelly. \$\endgroup\$ – Erik the Outgolfer Nov 10 '16 at 12:26
4
\$\begingroup\$

Pyth - 13 bytes

Base encoded once cycle series, modular indexed.

@-R2jC"
ûx"5

Try it online here.

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Looks shorter to just do a!b=a:b:(a+b)!(-a). \$\endgroup\$ – xnor Nov 9 '16 at 21:44
3
\$\begingroup\$

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]]&
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ You can probably save three bytes by defining a unary operator ± instead of a function a. \$\endgroup\$ – Martin Ender Nov 9 '16 at 8:32
1
\$\begingroup\$

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}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\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 Nov 10 '16 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 Nov 10 '16 at 12:02
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • 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 Nov 10 '16 at 15:12
  • 1
    \$\begingroup\$ @OlivierGrégoire thanks dude :) fixed. nice solution btw \$\endgroup\$ – peech Nov 10 '16 at 15:20
1
\$\begingroup\$

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.)

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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;
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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