Project Euler Problems 1-5

Author	Max Niederman
Published	2022-06-29
Tags	project-euler
Description	My solutions to the first five Project Euler problems.

#1, “Multiples of 3 and 5”

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.

The simplest solution is to simply iterate over all the natural numbers below 1000 and add them only if they are multiples of 3 or 5:

sum [n | n <- [1..999], n `rem` 3 == 0 || n `rem` 5 == 0]

A slightly more efficient solution avoids divisibility checks by incrementing by 5 or 3, respectively:

sum [0,3..999] + sum [0,5..999]

But this is actually incorrect, because multiples of both 3 and 5 are counted twice. We can solve this by subtracting the sum of multiples of 15 from the sum of multiples of 3 and 5:

sum [0,3..999] + sum [0,5..999] - sum [0,15..999]

Unless the compiler is really smart though, this is still $O (n)$ time; we can do better.

The sum of the first $n$ natural numbers is $\frac{n ^{2} - n}{2}$ . We can find the sum of the first $n$ multiples of a number $m$ by simply multiplying that formula by $m$ . Now all that’s left is to divide the upper bound by $m$ to find the number of multiples of $m$ . This yields a formula for the sum of the multiples of $m$ less than $n$ :

m \frac{⌊ \frac{n - 1}{m} ⌋ ^{2} - ⌊ \frac{n - 1}{m} ⌋}{2}

Substituting the problem’s upper bound and factors:

3 \frac{33 3 ^{2} - 333}{2} + 5 \frac{19 9 ^{2} - 199}{2} - 15 \frac{6 6 ^{2} - 66}{2}

This evaluates to the correct answer in $O (1)$ time.

#2, “Even Fibonacci numbers”

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, \dots$
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

First, I define the sequence. Because Haskell is lazy, I can define it as an infinite list, and it will only be computed when it actually needs to be accessed.

fibs :: Num a => [a]
fibs = 0 : scanl (+) 1 fibs

How this works may not be immediately obvious, but it’s actually fairly simple. scanl scans across a list and produces a new list by repeated application of a function. Since it only scans one element at a time, it can be used recursively to generate the sequence and find a number by its index.

fib :: Num a => Int -> a
fib = (!!) fibs

Starting with zero, every third Fibonacci number is even, so

-- each nth element of a list
each :: Int -> [a] -> [a]
each _ []     = []
each n (x:xs) = x : each n (drop (n - 1) xs)

answer n = sum $ each 3 $ takeWhile (<= n) fibs

And this gives the correct answer in $O (lo g n)$ time!

#3, “Largest prime factor”

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

What is the largest prime factor of the number 600851475143?

If you think of the number as a product of prime factors, you can reframe the problem as stripping away the smallest prime factors until you are left with a single factor, the largest one.

In Haskell, that process can be implemented like so:

lpf :: Integral a => a -> a
lpf n = case filter (\x -> n `rem` x == 0) [2..n] of
  n:[] -> n
  f:_  -> lpf (n `quot` f)

First, lpf gets a list of all factors of n except 1. Note that since Haskell is lazy, it won’t actually compute the entire list, but only the elements it actually needs to. This step could also be made slightly faster for n with very large prime factors by only going up to the square root of n.

Then, if the list contains only one element, n is prime, so lpf returns it. Otherwise, it divides n by that factor and calls itself on the quotient.

The time complexity of this algorithm is somewhat hard to reason about, since the number of operations is related to the sum of the prime factors of n, but it should be at most $O (n lo g n)$ . In reality I’m sure it’s significantly faster than that.

#4, “Largest palindrome product”

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

At first, it might seem necessary to check all $1 0^{6}$ products of 3-digit numbers. But if you go the other way, and just factor six-digit palindromes beginning with the largest until you find one that has two factors that are 3-digit numbers, you only need to check at most $1 0^{3}$ products. Of course, this is still exponential, but it’s more than good enough for $n = 3$ .

First, I need a way to generate palindromic numbers:

-- convert a string of digits to a number
fromBase :: Num a => a -> [a] -> a
fromBase base = foldl (\acc d -> base * acc + d) 0

-- generate a list of all strings of length n
strings :: [a] -> Int -> [[a]]
strings symbols 0 = [[]]
strings symbols n = [ s:ss | s  <- symbols,
                             ss <- strings symbols (n - 1) ]

-- generate a palindrome from a list
palindrome :: [a] -> [a]
palindrome xs = xs ++ reverse xs

-- list of six-digit palindromes in descending order
myPalindromes :: (Num a, Enum a) => [a]
myPalindromes = map (fromBase 10 . palindrome) (strings [9,8..0] 3)

Then, I can filter out the palindromes that aren’t factors of two 3-digit numbers to get the answer.

digitFactors :: Integral a => a -> a -> a -> [a]
digitFactors base digits n =
  filter (\x -> n `rem` x == 0) $
  reverse [base ^ (digits - 1) .. base ^ digits - 1]

checkAnswer :: Integral a => a -> a -> a -> Bool
checkAnswer base digits n =
  let correctDigitCount q = q >= base ^ (digits - 1) && q < base ^ digits
   in any (correctDigitCount . quot n) (digitFactors base digits n)

answer = head $ filter checkAnswer myPalindromes

#5, “Smallest multiple”

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

As is often the case with these kinds of problems, it’s useful to think of numbers as their prime factorizations. For example, we can rephrase the question of whether a number $a$ evenly divides a number $b$ as whether the multiset of the prime factors of $a$ is included in the multiset of the prime factors of $b$ .

Therefore, the smallest number which is evenly divisible by all elements of a set of numbers is the smallest number whose prime factorization includes the prime factorizations of each element of the set. This is also the multiset union of the factorizations.

It’s pretty easy to figure this out on paper, so I won’t bother writing code for it. You just count up from 1 to 20, factor each number, and remember the highest power of each prime factor. Then you can just multiply those together to find the answer.