Continuing from my Project Euler Problem 1, here are the next two Euler problems and some reflection!

Project Euler Problem 2

The second problem asks to find the sum of even Fibonacci numbers numbers below four million. For procedural languages, this is quite walk in the park, but for me a concise method to produce the series in Clojure proved a bit of a brain nugget!

Python 3

For Python, I decided to make a simple generator that yields the Fibonacci numbers below a given treshold N. Rest is just list comprehension:

def fib(N):
    i, j = 0, 1
    while j < N:
        yield(j)
        i, j = j, i+j

print(sum(i for i in fib(4e6) if i%2==0))

C++

In C++ it's natural to just loop with a conditional addition. This time I decided to drop using namespace std; to save a few characters. Without i, j = j, i+j syntax, the temporary variable ij is a bit ugly.

#include <iostream>

int main() {
    int i=0, j=1, s=0;

    while(j<4000000) {
        if(j%2==0) s += j;
        int ij = i + j; i = j; j = ij;
    }
    std::cout << s << std::endl;
}
}

Javascript

Here I could go either way, towards the Python list comprehension or C++ loop. Since generators are part of JS, I chose to try them out!

function *fib(N) {
    let i=0, j=1;
    while(j < N) {
        yield j;
        [i, j] = [j, i+j];
    }
}

console.log([...fib(4e6)].reduce((a,b) => a + b*(1-b%2), 0));

I combined the sum and conditional using reduce. Note that b*(1-b%2) evaluates to zero for off values of b!

Clojure

In Clojure, I wanted really to avoid just looping with while to get a feel of the different ways to generate the Fibonacci numbers. There are many ways to do it, including recursion (which gets really slow unoptimized) and lazy-cat solution that really eluded comprehension, until I realized that with lazy sequences, you can do (map + s (rest s)) and items are pulled from the linked list just in time to construct the next item.

First version uses iterate with a anonymous function [a b] -> [b a+b]. Starting with [0 1] you get [1 1], [1 2], [2 3], [3 5] and so on, and map last will transform that to Fibonacci sequence. First row is then just taking even numbers below 4 million and adding them up.

(prn (apply + (filter even? (take-while #(< % 4e6) (
    map last (iterate #(vector (% 1) (+ (% 0) (% 1))) [0 1]))))))

119 characters is actually less than the concise 132 characters of the Python solution, even though #(vector (% 1) (+ (% 0) (% 1))) does not elicit much feeling of elegance in my non-Lisp brain.

Adapting the lazy-seq positive numbers example in Clojure reference to produce Fibonacci numbers trims off 2 more characters:

(prn (apply + (filter even? (take-while #(< % 4e6) (
    (fn fib [a b] (lazy-seq (cons a (fib b (+ a b))))) 0 1)))))

Finally, the lazy-cat sets the floor with 109 character two-liner:

(def fib (lazy-cat [0 1] (map + (rest fib) fib)))
(prn (apply + (filter even? (take-while #(< % 4e6) fib))))

While harders to initially figure out, I do like the "seeding" of the lazy sequence with [0 1] and then just using lazy map to append to that one by one, producing new items just in time!

Project Euler Problem 3

Problem 3 deals with prime numbers, but compared to some later Euler problems, this is not too hard. Once you understand that p % d == 0 if d is a divisor of p, you can just eliminate factors until you are left with the biggest one (it follows that if you go from small to large divisors, the biggest factor will be the one remaining).

Python 3

Python does not have the nice for syntax of C, and range does not work as p is decreasing, so we have to contend with while and a separate addition. 88 characters:

p, d = 600851475143, 2
while d*d < p:
    while not p%d: p //= d
    d += 1
print(p)

C++

With C, we get the nice for loop, but #include and other overhead adds a few characters to a total of 155:

#include <iostream>

int main() {
    long p = 600851475143;
    for(long d=2; d*d < p; d++) while(!(p%d)) p /= d;
    std::cout << p << std::endl;
}

Javascript

For problem 2, JS combines the C like for and less overhead for printing the solution in just 82 characters:

p = 600851475143
for(let d=2; d*d < p; d++) while(!(p%d)) p /= d;
console.log(p)

Clojure

I have to admit that I'm not overly happy with my solutions in Clojure. My initial solution was to have a factor function to give the smallest divisor, and use recursion to get all factors and then return the biggest:

(defn factor [n] (first (filter #(zero? (mod n %)) (range 2 (Math/sqrt n)))))
(prn (apply max (loop [n 600851475143 s []]
    (if-let [d (factor n)]
        (recur (/ n d) (conj s d))
        (conj s n)))))

After some thinking, I realized that I can just divide out factors and print the remaining number. At 142 characters, this is OK and even quite readable:

(prn (loop [n 600851475143]
         (if-let [d (first (filter #(zero? (mod n %)) (range 2 (Math/sqrt n))))]
           (recur (/ n d)) n)))

Even if it yields a bit longer solution, I had fun time using iterate to either divide out d from the number if possible or increase d and try again. The progression ends when no more divisors are found, and then we just take the remainder of p from last tuple [p d].

(prn (first (last (take-while #(> (% 0) (% 1)) (
    iterate #(let [[p d] %] (if (zero? (mod p d)) [(/ p d) d] [p (inc d)]))
                     [600851475143 2])))))

Finally, I decided I'd just see if the Clojure looping structures would be less ugly. And lo and behold! The loop construct actually works really well for this problem, netting reasonable 121 characters:

(prn (loop [p 600851475143 d 2] (cond (>= d p) p
    (zero? (mod p d)) (recur (/ p d) d)
    :else (recur p (inc d)))))

Despite being more lengthy than the JS and Python solution ,this is less of a mind-bender. I like it.

Conclusions

The Project Euler problems 2 and 3 require already bit more processing, and I feel generating Fibonacci numbers and dividing away factors is well suited for procedural languages.

Still, in Problem 2 the lazy-cat solution generates the Fibonacci numbers in a very concise way, and using loop in Problem 3 nets a solution quite similar to other languages. Interesting!