# Project Euler in Nim

February 15, 2015

After a discussion on , 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 =
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.