Project Euler Problems (01 - 05)

Posted on April 25, 2012 by Ryan O'Neill

Problem 1:

// http://projecteuler.net/problem=1
 
// 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.
 
object Problem01 {
  def main(args: Array[String]) {
    val output = "Sum of [3,5] multiples below %d: "
 
    val verify = multipleSum(10)
    println(output.format(10) + verify)
 
    val answer = multipleSum(1000)
    println(output.format(1000) + answer)
  }
 
  def multipleSum(upperLimit: Int) = 
    (1 until upperLimit).filter(x => (x % 3 == 0) || (x % 5 == 0)).sum
}

Problem 2:

// http://projecteuler.net/problem=2
 
// 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.
 
// Normal Fibonacci Recurrence
// F0 = 0
// F1 = 1
// Fi = Fi-1 + Fi-2
 
// In the CLRS Algorithms book (page 59), 
// the answer to the recurrence relation is shown as 
// [Golden Ratio] = (1 + square root 5) / 2
// [Conjugate] = (1 - square root 5) / 2
// Fi = ([Golden Ratio]^i - [Conjugate]^i) / (square root 5)
 
// This problem starts with 1,2 instead of 1,1 so terms are off by 1
 
object Problem02 {
  def main(args: Array[String]) {
    val limit = 4000000
    println(evenValuedFibonacciSum(limit))
  }
 
  def evenValuedFibonacciSum(upperBound: Int) = 
    fibStream(1).takeWhile(_ <= upperBound).filter(_ % 2 == 0).sum
 
  def fibStream(i: Int): Stream[Int] =
    fibonacci(i) #:: fibStream(i + 1)
 
  def fibonacci(i: Int) = {
    val termIndex = i + 1
 
    val root5 = math.sqrt(5)
    val golden = (1 + root5) / 2
    val conjugate = (1 - root5) / 2
 
    ((math.pow(golden, termIndex) - math.pow(conjugate, termIndex)) / root5).toInt
  }
}

Problem 3:

// http://projecteuler.net/problem=3
 
//The prime factors of 13195 are 5, 7, 13 and 29.
 
//What is the largest prime factor of the number 600851475143 ?
 
object Problem03 {
  def main(args: Array[String]) {
    //val number = 13195
    val number = 600851475143L
    println(maxPrimeFactor(number))
  }
 
  def maxPrimeFactor(value: Long) = 
    value match {
      case _ if (value < 2) => throw new IllegalArgumentException
      case _ => factors(value).sortWith(_ > _).filter(isPrime).max
    }
 
  def isPrime(value: Long) : Boolean =
    if (value == 2) true else primeTest(value, math.sqrt(value).toLong)
 
  def primeTest(value: Long, attempt: Long): Boolean = 
    attempt match {
      case 1 => true
      case _ if (value % attempt == 0) => false
      case _ => primeTest(value, attempt - 1)
    }
 
  def factors(value: Long): List[Long] = {
    val factorLimit = math.max(math.sqrt(value).toInt, 2)
    val smallFactors = (2 to factorLimit).toList.filter(value % _ == 0).map(_.toLong)
    val largeFactors = smallFactors.map(value / _)
    smallFactors ::: largeFactors
  }
}

Problem 4:

// http://projecteuler.net/problem=4
 
// 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.
 
object Problem04 {
  def main(args: Array[String]) {
 
    val twoDigitNumbers = (10 to 99).toList
    println("Largest Palindrome Product of 2-Digit Numbers: " 
      + maxPalindromeProduct(twoDigitNumbers))
 
    val threeDigitNumbers = (100 to 999).toList
    println("Largest Palindrome Product of 3-Digit Numbers: " 
      + maxPalindromeProduct(threeDigitNumbers))
  }
 
  def maxPalindromeProduct(numbers: List[Int]) = {
    val palindromes = 
      for {
        a <- numbers
        b <- numbers
        value = a * b
        if (value.toString == value.toString.reverse)
      } yield value
    palindromes.max
  }
}

Problem 5:

// http://projecteuler.net/problem=5
 
// 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?
 
object Problem05 {
  def main(args: Array[String]) {
    val numbersToTen = (1 to 10).toList
    println("Lowest Common Multiple of 1 to 10: " + lcmList(numbersToTen))
 
    val numbersToTwenty = (1 to 20).toList
    println("Lowest Common Multiple of 1 to 20: " + lcmList(numbersToTwenty))
  }
 
  def lcmList(numbers: List[Int]) = 
    numbers.foldLeft(1)(lcm)
 
  def lcm(a: Int, b: Int) = 
    ((a.toLong * b.toLong) / gcd(a, b)).toInt
 
  def gcd(a: Int, b: Int) : Int = 
    if (a == b) a else if (a > b) gcd(a - b, a) else gcd(a, b - a)
}