# Code and Life

Programming, electronics and other cool tech stuff

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!