Project Euler 1-3: Solving Algorithms in Four Styles

I’ve now finished the first 25 easy-rated problems in Project Euler, which is evidently the point at which my fragile ego will allow me to stop and reflect on such things as efficiency and best practice. Attempting to learn to think better, by comparing my naive solutions with some of the other solutions on the forum, will be the topic of this post.

As this is an exercise in thinking, which transcends coding, most of my code snippets will be a Rust or Python-like pseudocode. I tend to find Haskell and Lisp especially interesting to analyze, and will explore these some of solutions on the answers forum.

But most especially, this post will be an exploration of four styles of thinking that I’m going to call imperative, functional, math, and recursive (aka declarative, though I’m going to exclusively use the term recursive). Most of the problems seem to admit at least two if not more of each of these, often with small variations and improvements within the styles of thought.

1 Multiples of 3 and 5

Find the sum of all the multiples of 3 or 5 below 1000.

My solutions

Two obvious implementations: a loop, and functional simple filtering of elements:

sum = 0
for i in 1..1000
	if 3|i or 5|i
		sum += i
print sum
sum = (1..1000)
	.filter(|x| 3|x or 5|x) 
	.add()
print sum

One more math-y solution, using the identity that:
1+2+..+n = n*(n+1)/2

sum3s = 3*333*334/2
sum5s = 5*200*201/2
sum15s = 15*66*67/2
sum = sum3s + sum5s - sum15s
print sum

Others’ solutions

Looks like mostly math and imperative solutions on the first page. I was pleased to see dough’s Haskell one liner, which does something similar to what I did in my functional pseudocode.

sum [n | n <- [1..1000-1], n `mod` 5 == 0 || n `mod` 3 == 0]

Which drigz on the second page also implemented, this time in python

reduce(lambda x,y: x+y, filter(lambda n: n%3==0 or n%5==0, range(1000)))

I always enjoy a lisp solution, even an imperative one

(defun sum-of-3-or-5 (limit)
  (loop for i from 1 to limit
        if (or (= 0 (mod i 3))
               (= 0 (mod i 5)))
          sum i))
(defun euler1 ()
  (sum-of-3-or-5 999))

But here’s a Haskell solution by Cribs on the second page, that used recursion, which I didn’t consider!

multiples :: Int -> Int
multiples x 
  | x < 1000 && (mod x 3 == 0 ||  mod x 5 == 0)
   = x + multiples (x+1)
  | x < 1000 = multiples (x+1)
  | otherwise = 0

The pseudocode for that would look like this:

f(x int) returns int
	if x < 1000 and (3|x or 5|x)
		return x + f(x+1)
	if else x < 1000 
		return f(x+1)
	else 
		return 0

Learning

I didn’t consider using recursion for this problem. It’s probably overkill, but I may not be reaching for recursion as often as I ought.

2 Even Fibonacci numbers

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

My solutions

There’s gotta be a math way to do this, and I bet I’m going to learn it. But the obvious solutions come first.

(sum, fib1, fib0) = (0, 1, 1)
while fib1 < 4e6
	if_even(fib1) 
		sum += fib1
	(fib1, fib0) = (fib1+fib0, fib1)
print sum

If the operation was a bit more complex, I could create a struct for Fib, with an increment method implemented that held my fib0, fib1 vales, but for something so simple it’s not really worth it.
I’m having a bit of trouble thinking of how to construct my array functionally. I’m missing a tool then. My pseudocode will reflect that.

sum = [array of fibs less than 4e6]
	.filter(|x| x.is_even())
	.sum()
print sum

I think a way to construct that array may be to use an iterator using a take_while() :
(1..).map(|n| nth_fib(n)).take_while(|x| x < 4e6)
but that’s pretty bad, since we have to run fib from 1 for every new item in the list.
Into the Weeds of Functional Programming Alert
So what we actually want to do is hold internal state in our function, which is why this is annoying; that sounds monadic in Haskell, and like an opportunity for scan or fold in Rust, which are iterator tools holding state.
From the documentation,
Scan takes an initial state (like my fibonacci state) and a function, and returns an new state, and the same function.
Fold does the same, but without returning the state.
A try:

(1..).scan((1,1), |state, x| {
	state.0, state.1 = state.1+state.0, state.0
	return state.0
	})
	.take_while(|x| x < 4000000)
	.sum()

That actually gets me pretty close! I just need to throw in the even filter, drop the unused x variable, and rewrite the tuple assignment in a Rust-compatible way.
A link to actual code that runs: Rust Playground
I took that solution to the Rust users forum, and was pointed at a way to perform a stateful computation inside of a function, in a way that I didn’t know about!
Any possible improvements to this functional program? – help – The Rust Programming Language Forum
User jethrogb suggested I use instead, the repeat_with
instead, and take advantage of Rust’s scoping create a state variable, and use the move keyword to pass that state into a closure. He also suggested I replace my three lines of updating the Fibonacci state by constructing a tuple to represent the next state, and using the replace method to do that in one shot. I had actually wanted to know how to do this with tuple assignment, but tuple assignment isn’t possible in this sitch, as we want to update the elements of state, not state itself. Thanks jethrogb!
Weeds Escaped
In light of my previous revelation that I was ignoring recursive solutions, here’s a recursive solution; this problem doesn’t benefit from recursion, but it’s good practice.

even_fib_sum(max int, fib1 int, fib0 int) returns int
	if fib1 > max
		return 0
	else if 2|fib1
		return fib1 + even_fib_sum(max, fib1+fib0, fib1)
	else 
		return even_fib_sum(max, fib1+fib0, fib1)

Others’ solutions

From the overview thread for problem 2
Apparently every third fibonacci is even. That’s actually pretty easy to observe if we just look at the fibonacci sequence,
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610…
The skill inherent in observing that would be looking for patterns in small cases. The observation isn’t earth-shattering for our implementations, simply changing an is-even check to an every-third index. That is, until we make the further observation that the sequence that remains,
2,8, 34, 144, 610
has the formula
x_{i} = x_{i-1}*4+x_{i-2}
which allows for a little speedup.
Algebraic!
More math: RudyPenteado observed that the ratio between even terms approaches phi^3, and did a little rounding.
I didn’t see any other surprising solutions in the comment thread for 2, but indulge me a comparison of two lisp implementations.
Always love an imperative Lisp solution, by JonRock:

(defun list-fibs (limit) 
  (let ((fibs(2 1))) ; fibs a list to be expanded
	  ; do until nextfib > limit
    (do ((nextfib (+ (car fibs) (cadr fibs)) 
                  (+ (car fibs) (cadr fibs))))
        ((> nextfib limit))
			; reassign fibs to the next element followed by fibs
        (setq fibs (cons nextfib fibs)))
    fibs)) ; return fibs, the list of fibonaccis
(defun euler2 ()
  (reduce #’+ (remove-if-not #’evenp (list-fibs 1000000))))

I’m lying. I can barely read that. I find Lisp’s paretheses notation awful for constructing readable imperative programs.
In particular, I notice hard it is to find the endpoint for the do until loop.
In contrast is madmonky1’s recursive lisp solution, which is a bit more readable in my opinion:

(defun fib (x &optional (y 0) (z 1)) ; set default starting pts to 0 and 1
       (if (< x z) ; x is max value, if exceeded, return nil
            nil
            (append (list z) (fib x z (+ y z)))))
(reduce #’+ (remove-if-not #’evenp (fib 1000000)))

That’s all to say, Lisp is only sometimes pretty.

Learning

How to construct an array (in Rust) functionally, where each new element of the array is generated from the previous element using a closure that holds onto a state. In particular, I learned and showed how to use the scan keyword in Rust to do a stateful computation, and linked to an even better implementation than I was able to come up with.

3 Larges prime factor

What is the largest prime factor of the number 600851475143 ?

My Solutions

Factoring is a problem where we get a little more modularity in our solution. A couple of observations.

  1. Imperatively, the brutest thing we could do would be to just loop by one until we find a factor dividing n, divide n by that, and continue until we’re left with the largest prime factor.
  2. The next thing would be to only iterate through primes, rather than by i++, which we can either grab an array of off the internet, or construct ourselves, this one for instance https://primes.utm.edu/lists/small/1000.txt
  3. We could further note that if it turns out that the number is prime, we’d need only to check up to the square root of the number to prove this, because math.
  4. We might also be aware of Fermat’s method for factoring, which might reduce our runtime a bit. There are more advanced factoring algorithms, but they get a bit overkill.

We might construct an imperative solution using observations 1-3

let p_arr = parse 1000.txt   
arr = []
i = 0
n = 600851475143
max = sqrt(n)
while n != 1 
	if arr[i] > max
		exit, print(“prime array too short")
	if p_arr[i]|n
		append i to arr
		n /= i 
		continue (don’t update i: p may divide n multiple times)
	else
		i++
print last element in arr

Or use Fermat’s method:

factor(n int) 
	i = ceiling( sqrt(n) )
	b = i*i - n
	until b is a square (or sqrt(b) has no decimal)
		i += 1
		b = i*i-n  
	return i - sqrt(b)
arr = []
n = 600851475143
while n != 1 
	k = factor(n)
	append k to arr
	n /= k
print max(arr)

We could do one other clever thing, functionally. Since we have a list of possible divisors of n, we could just reduce the list to values that divide n evenly. This would look like:

let p_arr = parse 1000.txt   
max_p_div = p_arr.filter(|p| p|600851475143)
	.max()
print max_p_div

Note that since the square root of n is 75146, and the largest prime in our list is 7919, this shouldn’t work with a list of primes so small, but it does anyway, since the prime we’re looking for turns out to be in the 6000s.
I feel there’s probably a recursive way to solve this problem too. In fact, one recursive solution is pretty similar to my iterative solution.

find_factors(n int, start_at int) -> array of ints
	if n = 1
		return []
	else if start_at|n
		return [start_at] + find_factors(n/start_at, start_at)
	else if start_at = 2
		return find_factors(n, start_at+1)
	else 
		return find_factors(n, start_at+2)
print last element in arr

 

Others’ Solutions

A couple of the solutions used my prime array method to reduce runtime, but I didn’t see a single Fermat’s method on the first three pages. I did find some interesting solutions in Haskell and Lisp, which I’ll dive into.

In this function, Sartak defines two base cases, and tells his function that if it receives n, anything larger than 1, to return the prime factors of n divided by f, where the computation occurs in recursive calls to prime_factors_of to append new factors to the list. This is a bit inefficient, since the recursive calls don’t save the work from the previous recursion!

prime_factors_of :: Integer -> [Integer]
prime_factors_of 0 = [] --base cases
prime_factors_of 1 = [] 
prime_factors_of n = f : prime_factors_of(n `div` f)                                             where f = head $ filter (\d -> n `mod` d == 0) [2..n]

elt’s Haskell solution solves that problem by using two arguments like I did up above in the pseudocode: one for n, and one for the starting point.

primeFactors x = primeFactorsx 0
primeFactors0 _ = [] -- base case
primeFactors' x i
	| (current*current > x) = [x]
	| x `divBy` current = current:primeFactors(x `div` current) 0
	| otherwise = primeFactorsx (i+1)
		where
			current = primes!!i -- a missing prime list

Though it looks like let relies on a list of primes that’s not included in the code.

Learnings

Reminders of how to use Fermat’s factoring algorithm, and somehow a bit of cheeky Haskell practice snuck in 😉

In Review

In this blog post, I showed how to attack problems in four different ways: functional, imperative, recursive, and mathematical. I learned a few things along the way! If you got this far, maybe you did too, and that’d be neat.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s