# Project Euler in Nim

February 15, 2015

After a discussion on linux-l@lists.ufl.edu, I decided to spend the majority of my day playing with Nim. I used it to solve the first three Project Euler problems, with a unnecessarily complicated dynamic programming solution to problem #2.

I know posting solutions to PE problems is looked down upon, but the first three problems are trivial, and solutions can undoubtedly be found elsewhere online.

# Problem One

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.

```
var sum = 0
for i in 1..999:
if i mod 3 == 0 or i mod 5 == 0:
sum += i
echo sum
```

# Problem Two

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.

```
# Of course, this solution is unnecessarily complicated, but that's as an excuse
# to try out more language features!
import tables
type MemoFunc = proc (a: int): int
proc memoize(f: MemoFunc): MemoFunc =
var previous = initTable[int, int]()
return proc(i: int): int =
if not previous.hasKey i:
previous[i] = f(i)
return previous[i]
# fib must be declared *before* use in the anonymous proc, otherwise nim won't
# be able to find it, as nim has static binding
var fib: proc(a: int): int
fib = memoize do (i: int) -> int:
if i == 0 or i == 1:
return 1
return fib(i-1) + fib(i-2)
var
sum = 0
i = 0
while true:
if fib(i) > 4_000_000:
break
if fib(i) mod 2 == 0:
sum += fib(i)
i += 1
echo sum
```

# Problem Three

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

```
var remaining = 600_851_475_143
# `..` retains a reference to `remaining`, not a value, unlike python's `range`
for i in 2..remaining:
if remaining mod i == 0:
remaining = remaining div i
echo "found prime factor: ", i
```

The views expressed on this site are my own and do not reflect those of my employer.