Project Euler, Problem #1

Of late, I’ve been working through the Project Euler problems, initially using Ruby as my language of choice. But then I started reading through Real World Haskell (generously made freely available) and thought it would be an interesting exercise to attempt to create idiomatic implementations of solutions in different languages. Here’s a start for Project Euler problem #1 — find the sum of all natural numbers less than 1000 that are divisible by 3 or 5.

In Ruby:
``````# find the sum of natural numbers less than 1000 divisible by 3 or 5
(1..999).select {|n| (n % 3 == 0) or (n % 5 == 0)}.inject { |sum, n| sum + n }``````
In Python:
``````# find the sum of natural numbers less than 1000 divisible by 3 or 5
sum([x for x in range(1000) if x % 3 == 0 or x % 5 == 0])``````
In Common Lisp:
``````;; define a common range generating function
(defun iota (count &optional (start 0) (step 1))
(loop repeat count for i from start by step collect i))

;; find the sum of natural numbers less than 1000 divisible by 3 or 5
(reduce #'+
(remove-if-not #'(lambda (n)
(or (zerop (rem n 3))
(zerop (rem n 5))))
(iota 1000)))``````
In Clojure:
``````;; find the sum of natural numbers less than 1000 divisible by 3 or 5
(reduce +
(filter #(or (zero? (rem % 3))
(zero? (rem % 5)))
(range 1000)))``````
In Perl:
``````#!/usr/bin/perl
use strict;
use List::Util qw(reduce);

# find the natural numbers less than 1000 divisible by 3 or 5
my @multiples = ();
foreach (1..999) {
if (\$_ % 3 == 0 || \$_ % 5 == 0) { push(@multiples, \$_); }
}

# sum them
print reduce { \$a + \$b } @multiples;``````
``````-- find the sum of natural numbers less than 1000 divisible by 3 or 5
import Data.List
foldl' (+) 0 [ x | x <- [1..999], (x `mod` 3 == 0) || (x `mod` 5 == 0) ]``````

When implementing these, Ruby came the most naturally (with Python a close second), but I think I find the syntax of the Haskell solution the most pleasing.

Update: Added implementations in Common Lisp, Clojure, and Perl.

Another Update: Changed Haskell implementation to use more efficient `foldl'` instead of `foldr`.

Posted 21 October 2009