Ståle’s weblog

Today I am feeling generous, so I will go through a couple off Euler problems in 1 post. First up is the 6th problem, here is the short version off the problem:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum

Thanks to the ease of creating ranges and applying functions to them in Scala, this turns out to be pretty easy:

1
2
3

val sumOfSquares = (1 to 100) map (a=>a*a) reduceLeft (_+_)
val squareOfSum = (BigInt(0) /: (1 to 100)) (_+_) pow(2)
println squareOfSum - sumOfSquares

Pretty simple code. The first line just maps each number in the 1 to 100 range to their 2nd power, then sums them all using reduceLeft. The second line uses the fold left operator (/:) to sum all the numbers in the 1 to 100 range into a single BigInt, which we then call the pow(2) method on to get the power off 2. Finally it’s just subtracting the 2 numbers.

Now onto problem 7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

The best way to find prime numbers, is to use the Sieve of Eratosthenes. We do this using a bitset. We start at index 2, and for each index we find that is not marked, we mark all the multiples for that index. So we first look at index 2, this is not marked, so we mark 4,6,8,10 and so on, up to our max. We then check index 3, this is not marked, so we mark 6,9,12,15 and so on. Then we go to index 4, this is marked, so we don’t do anything. This goes on until half the max value. Now we have a bit set where all non-primes are marked. Here is the method implemented in Scala using a mutable BitSet:

1
2
3
4
5
6
7
8

import scala.collection._
def primesUpTo(max:Int) = {
    val nonPrimes = new mutable.BitSet
    for (n <- 2 to (max/2); if !nonPrimes(n); x <- n*2 until(max,n)) {
        nonPrimes += x
    }
    for (n <- 1 to max; if !nonPrimes(n)) yield n
}

We first import everything in the scala.collections package, then mutable.BitSet can be resolved to scala.collections.mutable.BitSet. This is an extension to the package system in Java where only classes can be imported, in Scala we can import namespaces and refer to things within those namespaces. Now we iterate from 2 until max/2, for each number we see if it’s not set in the bitset, if it isn’t we iterate until max with a step off n, and mark off each multiple. Finally we just iterate over the entire bitset, and yield all unmarked values, as those will be the primes.

Now to get the solution to the problem, we just need to figure out a max value that creates more than 10001 primes, and get the 10001th prime from that:

1

println(primesUpTo(500000)(10001))

Now I am going to skip number 8, as I can use that to deal with file parsing, and instead move directly on to number 9:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

There are some clever ways off doing this, but I am just heading straight for brute force solution to this one, as the solution space is pretty small.

1
2

val n = 1000
for (a <- 1 to n; b <- a to n-a; c=n-a-b;if a*a+b*b==c*c) println(a*b*c)

Since I use the target value 1000 a few times, I just put it in a constant that I can refer to. I first iterate a from 1 to 1000, then b goes from a to n-a, and c will then have to be 1000-a-b for the a and b that are set at that part in the iteration. We then just check if the values we have for a,b and c fulfill the Pythagorean formula, and print the product off the first one we find. Short and sweet.

That’s it for todays program. Next up will problem 8, and file parsing, which I haven’t looked into yet for Scala. I will have to compare it to Python, which has some nice and simple features for text file parsing.

Staale Euler, Scala Euler, Scala