S-99 P36-P41 Blank

gistfile1.scala

// *** S-99: Ninety-Nine Scala Problems ***
// http://aperiodic.net/phil/scala/s-99/
//
// wget http://www.scala-tools.org/repo-releases/org/scalatest/scalatest_2.9.1/1.6.1/scalatest_2.9.1-1.6.1.jar
// scala -deprecation -cp scalatest*.jar s99-36-41.scala

import org.scalatest.matchers.ShouldMatchers._

class NotImplementedYet extends RuntimeException

object S99Int {
  val primes = Stream.cons(2, Stream.from(3, 2) filter { _.isPrime })
  case class P31Int(i: Int) {
    def isPrime: Boolean = {
      i > 1 && (primes takeWhile { _ <= math.sqrt(i) } forall { i % _ != 0 })
    }
  }
  object P32 {
    def gcd(m: Int, n: Int): Int = if (n == 0) m else gcd(n, m % n)
  }
  implicit def fromIntToP31Int(i: Int): P31Int = P31Int(i)
  case class P33Int(i: Int) {
    def isCoprimeTo(j: Int): Boolean = P32.gcd(i, j) == 1
  }
  implicit def fromIntToP33Int(i: Int): P33Int = P33Int(i)
  case class P34Int(i: Int) {
    def totient34: Int = (1 to i) filter { j => i.isCoprimeTo(j) } length
  }
  implicit def fromIntToP34Int(i: Int): P34Int = P34Int(i)
}

// P36: Determine the prime factors of a given positive integer (2).
object P36 {
  case class P36Int(i: Int) {
    def primeFactorMultiplicity: List[(Int, Int)] = {
      throw new NotImplementedYet
    }
    def primeFactorMultiplicityAsMap: Map[Int, Int] = {
      throw new NotImplementedYet
    }
  }
  implicit def fromIntToP36Int(i: Int): P36Int = P36Int(i)

  def test {
    {
      315.primeFactorMultiplicity should equal(List((3,2), (5,1), (7,1)))
      315.primeFactorMultiplicityAsMap should equal(Map(3 -> 2, 5 -> 1, 7 -> 1))
    }
  }
}

// P37: Calculate Euler's totient function phi(m) (improved).
//   See problem P34 for the definition of Euler's totient function.
//   If the list of the prime factors of a number m is known in the form of problem P36
//   then the function phi(m>) can be efficiently calculated as follows:
//   Let [[p1, m1], [p2, m2], [p3, m3], ...]
//   be the list of prime factors (and their multiplicities) of a given number m.
//   Then phi(m) can be calculated with the following formula:
//   phi(m) = (p1-1)*p1(m1-1) * (p2-1)*p2(m2-1) * (p3-1)*p3(m3-1) * ...
//   Note that ab stands for the bth power of a.
object P37 {
  case class P37Int(i: Int) {
    def totient: Int = {
      throw new NotImplementedYet
    }
  }
  implicit def fromIntToP37Int(i: Int): P37Int = P37Int(i)

  def test {
    {
      10.totient should equal(4) // 1,3,7,9
      11.totient should equal(10) // 1,2,3,4,5,6,7,8,9,10
    }
  }
}

// P38: Compare the two methods of calculating Euler's totient function.
//   Use the solutions of problems P34 and P37 to compare the algorithms.
//   Try to calculate phi(10090) as an example.
object P38 {
  def test {
    throw new NotImplementedYet
  }
}

// P39: A list of prime numbers.
//   Given a range of integers by its lower and upper limit,
//   construct a list of all prime numbers in that range.
object P39 {
  def listPrimesinRange(r: Range): List[Int] = {
    throw new NotImplementedYet
  }
  def test {
    P39.listPrimesinRange(7 to 31) should equal(List(7, 11, 13, 17, 19, 23, 29, 31))
  }
}

// P40: Goldbach's conjecture.
//   Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers.
//   E.g. 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case.
//   It has been numerically confirmed up to very large numbers (much larger than Scala's Int can represent).
//   Write a function to find the two prime numbers that sum up to a given even integer.
object P40 {
  case class P40Int(i: Int) {
    def goldbach: (Int, Int) = {
      throw new NotImplementedYet
    }
  }
  implicit def fromIntToP40Int(i: Int): P40Int = P40Int(i)

  def test {
    28.goldbach should equal((5,23))
  }
}

// P41: A list of Goldbach compositions.
//   Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.
object P41 {
  def goldbachList(r: Range): String = {
    throw new NotImplementedYet
  }
  def goldbachListLimited(r: Range, limit: Int): String = {
    throw new NotImplementedYet
  }
  def test {
    {
      val actual= P41.goldbachList(9 to 20)
      print(actual)
      val expected = """10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17
"""
      actual should equal(expected)
    }
    {
      val actual = P41.goldbachListLimited(1 to 2000, 50)
      print(actual)
      val expected = """992 = 73 + 919
1382 = 61 + 1321
1856 = 67 + 1789
1928 = 61 + 1867
"""
      actual should equal(expected)
    }
  }
}

P36.test
P37.test
P38.test
P39.test
P40.test
P41.test

// vim: set ts=4 sw=4 et: