14
\$\begingroup\$

If you look at the Fibonacci Numbers, you will notice a pattern in their parity: 0, 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144. Every third number is even, and all the others are odd. This makes sense because an even plus an odd is odd, but an odd plus an odd is even and the sum for a term will always include at least one even number unless the last two terms were odd, which happens every three terms.

In this challenge you will have to look at a generalization of this problem.

Specs

  • You will be given as input two positive integers describing the Fibonacci integer sequence you will have to look at.
  • For example, 0, 1 describes the original Fibonacci numbers, and 2, 1 would be the Lucas numbers. The sequence is calculated with the recurrence relation: x(n+2)=x(n+1)+x(n).
  • You will also take a positive integer n.
  • Your code has to output the parity of the nth term of the described Fibonacci integer sequence (0 indexed).
  • The output format can be any two sane, consistent outputs (e.g. 0 for even and 1 for odd).

Test Cases

(Fibonacci numbers) [0, 1], 4  ->  odd
(Lucas numbers) [2, 1], 9  ->  even
[14, 17], 24  ->  even
[3, 9], 15  ->  odd
[2, 4], 10  ->  even
\$\endgroup\$
5
  • \$\begingroup\$ Is it possible for the input to contain two numbers of the same parity? For example, [2, 4] \$\endgroup\$
    – DJMcMayhem
    Jun 18, 2016 at 5:34
  • \$\begingroup\$ @DrGreenEggsandIronMan yes, adding. \$\endgroup\$
    – Maltysen
    Jun 18, 2016 at 5:37
  • \$\begingroup\$ Related \$\endgroup\$ Jun 18, 2016 at 6:35
  • \$\begingroup\$ Can the input be shaped [0,1], 4 or unshaped 0,1,4 depending on which is shorter to implement? \$\endgroup\$ Jun 18, 2016 at 17:15
  • \$\begingroup\$ @BradGilbertb2gills it can be shaped in any sane way \$\endgroup\$
    – Maltysen
    Jun 18, 2016 at 17:18

16 Answers 16

10
\$\begingroup\$

Python, 29 bytes

lambda a,b,n:[a,b,a+b][n%3]%2

The generalized Fibonacci sequence modulo 2 has cycle length of 3. So, we reduce n mod 3 and take that element of the first three.


31 bytes:

lambda a,b,n:0<a%2*2+b%2!=n%3+1

True for odd, False for even

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

Jelly, 4 bytes

^¡^Ḃ

Prints 0 for even, 1 for odd. Try it online!

How it works

The quick ¡ takes a link it applies repeated to the previous output, and optionally a second link that specifies the number of iterations. If that second link is absent (which is the case here), the number of iterations is taken from the last command-line argument.

When the first link is dyadic (which is the case with ^), ¡ applies that link to the previous return value (which is initialized as the left argument) and the right argument, then updates the return value with the result and the right argument with the previous return value. After doing so as many times as specified in the number of iterations, it returns the last return value.

The quicklink is called with the left argument (first command-line argument) and the result of ^ (bitwise XOR of the left and right argument, i.e., the first and second command-line argument). XORing is necessary since the right argument is not among the return values, meaning that the right argument has to be the x(-1) in order to return x(n) with x(0) ^ n ¡ x(1).

To actually calculate x(n), we'd use the code +¡_@ ( instead of and _@ – left argument subtracted from right argument – instead of ^), but since we're only interested in the parities, any combination of +, _ and ^ will do.

Finally, (bit) computes and returns the parity of x(n).

\$\endgroup\$
3
  • 3
    \$\begingroup\$ that was way too easy... :/ \$\endgroup\$
    – Maltysen
    Jun 18, 2016 at 4:24
  • \$\begingroup\$ Since when did Jelly accept triads? \$\endgroup\$
    – Leaky Nun
    Jun 18, 2016 at 4:31
  • 1
    \$\begingroup\$ @LeakyNun It doesn't, really. In the absence of a link specifying the number of iterations, ¡ uses the last command-line argument or (if there aren't any) an integer read from STDIN. \$\endgroup\$
    – Dennis
    Jun 18, 2016 at 4:46
3
\$\begingroup\$

Factor, 27 bytes

[ [ tuck + ] times . odd? ]

Try it online!

Well, executing the Fibonacci recurrence directly is way shorter than any other "smart" methods. Takes three items a0 a1 n on the stack, and outputs t for odd and f for even. Prints an unused value as a side effect.

For golfing, . is shorter than drop, and odd? is shorter than 2 mod or even?.

[                   ! ( a0 a1 n )
  [ tuck + ] times  ! ( an an+1 ) Execute Fibonacci recurrence n times
  . odd?            ! drop an+1 by printing and test if an is odd
]
\$\endgroup\$
2
\$\begingroup\$

Python, 38 bytes

lambda a,b,n:(b*(n%3>0)+a*(~-n%3>0))%2
\$\endgroup\$
2
\$\begingroup\$

Jelly, 3 bytes

+¡Ḃ

Try it online!

Outputs 0 for even and 1 for odd

How it works

+¡Ḃ - Main link. Takes a on the left and b on the right and n on the command line
 ¡  - Run the following dyad f(x,y) n times, starting with l = a and r = b.
      After each step, update l and r to l = r, r = f(l, r):
+   - f(x,y): x+y
      This is a generalised n'th Fibonacci "builtin"
  Ḃ - Bit; Return 1 for odd, 0 for even
\$\endgroup\$
1
\$\begingroup\$

J, 15 bytes

2|0{(]{:,+/)^:[

Simple method. Computes the nth term, and takes it modulo 2 to find its parity. Even parity is represented by 0 and odd parity by 1.

Usage

   f =: 2|0{(]{:,+/)^:[
   4 f 0 1
1
   9 f 2 1
0
   24 f 14 17
0
   15 f 3 9
1

Explanation

2|0{(]{:,+/)^:[  Input: n on LHS, and initial values [a, b] on RHS
    ( .... )^:[  Repeat the function n times
         +/      Find the sum of a+b
      {:         Get the value b from the tail of [a, b]
        ,        Join the values to get [b, a+b]
     ]           Return those values as the new [a, b]
  0{             Select the first value at index 0 from the list (after n applications)
2|               Take that value modulo 2 and return
\$\endgroup\$
1
\$\begingroup\$

MATL, 10 7 bytes

tshwQ)o

Try it online!

Explanation:

t            #Duplicate the array of numbers
 s           #Sum them
  h          #and add that to the end of the array
   w         #Swap inputs so that the *N* is on top
    Q        #Increment *N* (Since MATL uses 1-based indexing)
     )       #Get that element of the array. MATL uses modular indexing.
      o      #Return it's parity
\$\endgroup\$
3
  • \$\begingroup\$ You can remove 3\ thanks to modular indexing. Also, since this commit (which predates the challenge) you can use o instead of 2\ (note this doesn't work in TIO yet). So: tshwQ)o for 7 bytes \$\endgroup\$
    – Luis Mendo
    Jun 18, 2016 at 15:06
  • \$\begingroup\$ Really, it looks like it works to me: :P. Also, thanks for the tips! \$\endgroup\$
    – DJMcMayhem
    Jun 18, 2016 at 15:56
  • \$\begingroup\$ Yes, I asked Dennis to pull that commit and it works now \$\endgroup\$
    – Luis Mendo
    Jun 18, 2016 at 16:02
1
\$\begingroup\$

Perl 6,  24  23 bytes

{(|@^a,sum @a)[$^n%3]%2}
{(|@^a,&[+]...*)[$^n]%2}
{(|@^a,*+*...*)[$^n]%2}

Test:

use v6.c;
use Test;

constant even = 0;
constant odd = 1;
my @test = (
  ([0, 1], 4)    => odd,
  ([2, 1], 9)    => even,
  ([14, 17], 24) => even,
  ([3, 9], 15)   => odd,
  ([2, 4], 10)   => even,
);

my &seq-parity = {(|@^a,*+*...*)[$^n]%2}

for @test -> ( :key($input), :value($expected) ) {
  is seq-parity(|$input), $expected, ($input => <even odd>[$expected]).gist
}
ok 1 - ([0 1] 4) => odd
ok 2 - ([2 1] 9) => even
ok 3 - ([14 17] 24) => even
ok 4 - ([3 9] 15) => odd
ok 5 - ([2 4] 10) => even

Explanation:

{
  (
    # generate the Fibonacci integer sequence
    # ( @^a is the first two values )
    |@^a, *+* ... *
  )[ $^n ] # get the one at the appropriate index
  % 2 # modulo 2
}
\$\endgroup\$
1
\$\begingroup\$

Julia, 23 bytes

x\n=[x;sum(x)][n%3+1]%2

Try it online!

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

Mathematica, 38 36 bytes

OddQ@({#,#2,+##}&@@#)[[#2~Mod~3+1]]&

Anonymous function, based off of @xnor's Python approach. Takes a list and an integer, and outputs either True for odd or False for even. Not much beyond that.

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

R + pryr, 30 bytes

pryr::f(c(x,y,x+y)[n%%3+1]%%2)

Try it online!

Calculates parity of modular index of (x,y,x+y); returns 0 for even and 1 for odd. Function with arguments n,x and y, where x and y represent the initial two fibonacci numbers.

The f() function from the pryr library is a short way to define a function. In code-golf, it's sometimes used simply because pryr::f has one less character than function. However, it also tries to 'guess' the function arguments from the body of the function if they are not declared (using a mysterious and not well-documented algorithm). This is particularly useful here, where declaring x,y,n in a conventional function definition would cost an extra 5 bytes.
Luckily, in this case f somehow manages to guess the arguments perfectly.

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

Rust, 23 bytes

Port of xnor's answer, which you should upvote!

|a,b,n|[a,b,a+b][n%3]%2

Try it online!

Rust is Language of the month for December, but it doesn't have a ton of answers, so I'm posting a trivial one to remind y'all that Rust can sometimes beat Python too.

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

Pyke, 9 bytes

3%QDs+@2%

Try it here!

    s+    -   input+sum(input)
      @   -  ^[V]
3%        -   line_2 % 3
       2% - ^ % 2
\$\endgroup\$
0
\$\begingroup\$

Actually, 12 bytes

╗│+k3╜%@E2@%

This uses the same strategy as xnor's Python answer. Input is a b n, with the spaces replaced by newlines. Output is 0 for even parity and 1 for odd parity.

Try it online!

Explanation:

╗│+k3╜%@E2@%
              implicit input ([a, b, n])
╗             save n in reg0 ([a, b])
 │            duplicate stack ([a, b, a, b])
  +k          add, push stack as list ([[a, b, a+b]])
    3╜%       n mod 3 ([[a, b, a+b], n%3])
       @E     element in list ([[a, b, a+b][n%3])
         2@%  mod 2 ([[a, b, a+b][n%3]%2)
\$\endgroup\$
0
\$\begingroup\$

CJam, 9 bytes

q~_:++=2%

Even is zero, odd is one.

Try it online!

Explanation

q~        e# Read input and evaluate
  _       e# Duplicate initial tuple
   :+     e# Sum initial values
     +    e# Append sum to initial tuple
      =   e# Take the n-th element (modular indexing)
       2% e# Modulo 2
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -MList::Util=sum -pla, 21 bytes

A port of @xnor's python answer as a Perl program.

$_=(@F,sum@F)[<>%3]%2

Try it online!

Inputs the two starting sequence numbers on the first line and the element to find on the second. Outputs 1 for odd parity and 0 for even.

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