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)

 


 

신고
Posted by steloflute

Problem 1

05 October 2001

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.


Answer:
233168

Solution in C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    static class Program {
        static void problem1() {
            Console.WriteLine(Enumerable.Range(1, 999).Where(x => x % 3 == 0 || x % 5 == 0).Sum());
        }

        static void Main(string[] args) {
            problem1();
            Console.ReadKey();
        }
    }
}

 

Solution in Perl

 

# 1
for (1..999) {$sum+=$_ if $_%3==0 or $_%5==0} print $sum;

# 2
use List::Util qw(sum);
print sum grep {$_%3==0 or $_%5==0} 1..999;

 

Python

 

def problem1():
    print sum(x for x in xrange(1, 1000) if x % 3 == 0 or x % 5 == 0)

 

def problem1a():

    print sum(filter(lambda x:x%3==0 or x%5==0, xrange(1,1000)))

 

problem1()

 

 

Racket

 

#lang racket
(define (range start end step) 
  (define (loop x r)
    (cond
      ((<= x end) (loop (add1 x) (append r (list x))))
      (else r)))
  (loop start '())
  )

(display (apply + (filter
                     (lambda (x) (or (= (remainder x 3) 0)
                                     (= (remainder x 5) 0)))
                     (range 1 999 1))))

 


 

; using sequence

(define (problem1)
  (sequence-fold
   + 0
   (sequence-filter
    (lambda (x) (or (zero? (remainder x 3))
                    (zero? (remainder x 5))))
    (in-range 1 1000))))

 


 

; for loop

#lang racket
(define (problem1)
  (let ([sum 0])
    (for ([i (in-range 1 1000)])
      (when (or (= 0 (modulo i 3))
                (= 0 (modulo i 5)))
        (set! sum (+ sum i))))
    (display sum)))

(problem1)

 


 

; no set!

(define (problem1)
  (display
   (let loop ([sum 0]
              [i 1])
     (if (< i 1000)
         (if (or (= 0 (modulo i 3))
                 (= 0 (modulo i 5))
                 )
             (loop (+ sum i) (+ 1 i))
             (loop sum (+ 1 i)))
         sum))))

(problem1)

 


; set

(apply + (set->list (set-union (apply set (range 3 1000 3)) (apply set (range 5 1000 5)))))

 


; list

(define-syntax-rule (fn lst ...)
  (lambda lst ...))
(define-syntax-rule (% lst ...)
  (modulo lst ...))

(apply + (filter (fn (x) (or (= 0 (% x 3)) (= 0 (% x 5))))
                 (range 1 1000)))

 

; for/sum

(for/sum ([i (in-range 1 1000)]

          #:when (or (zero? (remainder i 3)) (zero? (remainder i 5))))

  i)

 

Clojure

 

(defn problem1 []
  (println
    (loop [sum 0
           i 1]
      (if (< i 1000)
        (if (or (= 0 (mod i 3))
                (= 0 (mod i 5)))
          (recur (+ sum i) (+ 1 i))
          (recur sum (+ 1 i)))
        sum))))

(problem1)



(apply + (filter #(or (zero? (rem % 3)) (zero? (rem % 5))) (range 1000)))


 

 

Go

Playground: http://play.golang.org/p/INa3pMe_B0


package main

import "fmt"

func problem1() {
    sum := 0
    for i := 1; i < 1000; i++ {
        if i%3 == 0 || i%5 == 0 {
            sum += i
        }
    }
    fmt.Println(sum)
}

func main() {
    problem1()
}



C++


#include <iostream>

using namespace std;


void problem1() {

 int sum = 0;

 for (int i = 1; i < 1000; i++) {

  if (i % 3 == 0 || i % 5 == 0) {

  sum += i;

  }

 }

 cout << sum << endl;

}


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

{

 problem1();

 cin.get();

 return 0;

}



C++ functional

 

template <typename TCond>

class range {

private:

    int start, end;

    TCond cond;

public:

    range(int start, int end, TCond cond) {

        this->start = start;

        this->end = end;

        this->cond = cond;

    }


    int sum() {

        int s = 0;

        for (int i = start; i <= end; i++) {

            if (cond(i)) s += i;

        }

        return s;

    }

};


void problem1a() {

    struct cond1 {

        bool operator()(int x) {

            return x % 3 == 0 || x % 5 == 0;

        }

    };


    cout << range<cond1>(1, 999, cond1()).sum() << endl;

}

 

C++11

 

#include <iostream>
using namespace std;
int main() {
  auto s = 0;
  for (auto i = 1; i <= 999; i++) {
    if (i % 3 == 0 || i % 5 == 0) s += i;
  }
  cout << s << endl;
}

 



Javascript

 

function problem1() {
 var sum = 0;
 for (var i = 1; i < 1000; i++) {
  if (i % 3 == 0 || i % 5 == 0) {
   sum += i;
  }
 }
 WScript.Echo(sum);
}

problem1();

 

// one-liner

for(var sum=0,i=1;i<1000;i++) if(i%3==0||i%5==0) sum+=i

 

Bash

 

#!/bin/bash

# In emacs, run with C-c C-x

function problem1 {
    local sum=0 i=1
    while ((i < 1000))
    do
        if ((i % 3 == 0 || i % 5 == 0)); then ((sum += i)); fi
        ((i++))
    done
    echo $sum
}

problem1


 

# one-liner

((sum=0)); for ((i=1; i<=999; i++)); do if ((i%3==0||i%5==0)); then ((sum+=i)); fi; done; echo $sum

 

Haskell

 

import Data.List (union)
main = print $ sum (union [3,6..999] [5,10..999])

 

 

* newLISP

 

; 1
(define sum 0)
(for (x 1 999) (if (or (= 0 (% x 3)) (= 0 (% x 5))) (set 'sum (+ sum x))))
(println sum)

; 2
(println
 (apply +
        (filter (fn (x) (or (= 0 (% x 3)) (= 0 (% x 5))))
                (sequence 1 999))))

 

Common Lisp

 

;1

(let ((sum 0))
  (loop for i from 1 to 999 do
    (if (or (zerop (mod i 3)) (zerop (mod i 5)))
      (incf sum i)))
  (print sum))

 

; 2

(loop for i from 1 to 999 when (or (zerop (mod i 3)) (zerop (mod i 5))) sum i)



C


#include <stdio.h>

int main() {
  int s=0, i=1;
  for (; i<1000; i++) {
    if (i%3 == 0 || i%5 == 0) s+=i;
  }
  printf("%d\n", s);
}


Emacs Lisp

emacs --script euler1.el

 

(setq sum 0
      i 1)
(while (< i 1000)
  (if (or (= 0 (% i 3)) (= 0 (% i 5))) (setq sum (+ sum i)))
  (setq i (1+ i)))
(princ sum)


 

Arc

 

(apply + (keep [or (is 0 (mod _ 3)) (is 0 (mod _ 5))] (range 1 999)))



# Ada


with Ada.Text_IO;


procedure main is

   sum: Integer := 0;

begin

   for i in 1 .. 999 loop

      if i mod 3 = 0 or else i mod 5 = 0 then

         sum := sum + i;

      end if;

   end loop;

   Ada.Text_IO.Put_Line(Integer'Image(sum));

end main;




# Pascal

var
i: longint;
sum: longint;
begin
sum := 0;
for i := 1 to 999 do
begin
if (i mod 3 = 0) or (i mod 5 = 0) then
sum := sum + i
end;
writeln(sum)
end.


신고
Posted by steloflute

Project Euler

Project Euler 2012.05.27 23:43

http://projecteuler.net/

 

수학과 프로그래밍을 연습할 수 있는 매우 훌륭한 곳이다.

 

 

My Banner

Profile Image

 

 

http://code.google.com/p/projecteuler-solutions/wiki/ProjectEulerSolutions

 

 

신고
Posted by steloflute


Generate bitcoin for me

What's this?