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