# Project Euler Problem 2 and 3 with Clojure, Python, Javascript and C++

Fri, Mar 19, 2021 in post General javascript clojure python c++ euler project euler problem

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!

## comments