Project Euler Problem 2

Problem 2

19 October 2001

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Answer: 4613732

 

Solution in Perl

 

use List::Util qw(sum);

sub fibUnder {
 my ($limit) = @_;
 my @r = (1, 1);
 while () {
  my $c = $r[-2] + $r[-1];
  last if ($c >= $limit);
  push(@r, $c);
 }
 @r;
}

print sum grep { $_ % 2 == 0 } fibUnder 4000000;

 

 

Python

 

def fibUnder(limit):   
    r = [ 1, 1 ]
    while(1):
        c = r[-2] + r[-1]
        if c >= limit: break
        r.append(c)   
    return r

def problem2():
    print sum(filter(lambda x: x % 2 == 0, fibUnder(4000000)));

 

 

Racket

 

(define (fibUnder limit)
  (define (loop r)
    (define c (apply + (take-right r 2)))
    (cond
      ((< c limit) (loop (append r (list c))))
      (else r)))
  (loop '(1 1)))
(define (problem2)
  (display (apply + (filter even? (fibUnder 4000000)))))
(problem2)

 

; Dynamic Programming

(define (problem2)
  (let loop ([a 1]
             [b 1]
             [sum 0])
    (if (<= a 4000000)
        (loop b (+ a b) (if (even? a) (+ sum a) sum))
        (display sum))))

(problem2)

; Imperative

(define (problem2)

  (define sum 0)

  (let loop ([a 1]

             [b 1])

    (when (<= a 4000000)

      (when (even? a) (set! sum (+ sum a)))

      (loop b (+ a b))))

  (display sum))

(problem2)

Clojure

(defn problem2 []

  (loop [a 1

 b 1

 sum 0]

    (if (<= a 4000000)

        (recur b (+ a b) (if (even? a) (+ sum a) sum))

        (println sum))))

(problem2)

 

 

Go

func fibUnder(limit int) []int {
 r := []int{1, 1}
 for {
  length := len(r)
  c := r[length-2] + r[length-1]
  if c >= limit {
   break
  }
  r = append(r, c)
 }
 return r
}

func problem2() {
 sum := 0
 for _, c := range fibUnder(4000000) {
  if c%2 == 0 {
   sum += c
  }
 }
 fmt.Println(sum)
}

func main() { 
 problem2()
}

C++

#include <iostream>

#include <vector>

using namespace std;

vector<int> fibUnder(int limit) {

vector<int> r(2, 1);

while (true) {

int length = r.size();

int c = r[length-2] + r[length-1];

if (c >= limit) {

break;

}

r.push_back(c);

}

return r;

}

void problem2() {

int sum = 0;

vector<int> fibs = fibUnder(4000000);

for (vector<int>::iterator itr = fibs.begin(); itr != fibs.end(); itr++) {

if (*itr % 2 == 0) {

sum += *itr;

}

}

cout << sum << endl;

}

int main(int argc, char* argv[])

{

problem2();

cin.get();

return 0;

}

C++ functional

template <typename TContainer, typename TCond>

int sumWhere(TContainer container, TCond cond) {

    int sum = 0;

    for (TContainer::iterator itr = container.begin(); itr != container.end(); itr++) {

        if (cond(*itr)) sum += *itr;

    }

    return sum;

}

void problem2a() {

    vector<int> fibs = fibUnder(4000000);

    struct {

        bool operator()(int x) {

            return x % 2 == 0;

        }

    } even;

    cout << sumWhere(fibs, even) << endl;

}

 

Bash

 

function fibUnder {
    limit=$1
    r="1 1"
    a=1
    b=1
    while ((1)); do
        let 'c=a+b'
        if ((c >= limit)); then break; fi
        let 'a=b'
        let 'b=c'
        r="$r $c"
    done
    echo $r
}

 

function problem2 {
    sum=0
    for x in $(fibUnder 4000000); do
        if ((x % 2 == 0)); then let 'sum += x'; fi
    done
    echo $sum
}

 

problem2

Javascript

var a=1, b=1, sum=0; while(a <= 4000000) { if (a % 2 == 0) sum += a; var c=a+b; a=b; b=c; } sum

Haskell

 

fibs = 1:1:zipWith (+) fibs (tail fibs)
main=print $ sum [x|x<-takeWhile (<= 4000000) fibs, even x]

 

 

* newLISP

 

(set 'a 1)
(set 'b 1)
(set 'sum 0)
(while (<= a 4000000)
 (set 'c (+ a b))
 (set 'a b)
 (set 'b c)
 (when (even? a) (set 'sum (+ sum a))))
(println sum)

 

C

#include <stdio.h>

int main() {
  int a=1, b=1, s=0;
  while (1) {
    int c=a+b;
    if (c>4000000) break;
    if (c%2==0) s+=c;
    a=b;
    b=c;
  }
  printf("%d\n", s);
}

 

Emacs Lisp

 

(setq a 1)
(setq b 1)
(setq sum 0)
(while (<= a 4000000)
  (setq c (+ a b)
        a b
        b c)
  (when (zerop (% a 2)) (setq sum (+ sum a))))
(princ sum)

 

Common Lisp

(let ((a 1) (b 1) (sum 0) (c))
  (loop while (<= a 4000000) do
       (setq c (+ a b)
         a b
         b c)
       (when (zerop (mod a 2)) (setq sum (+ sum a))))
  (princ sum))

Arc

 

(= a 1
 b 1
 sum 0)
(while (<= a 4000000)
 (= c (+ a b)
  a b
  b c)
 (when (even a) (++ sum a)))
(prn sum)