Instantly share code, notes, and snippets.

# seratch/gist:1213678 Created Sep 13, 2011

What would you like to do?
S-99 P36-P41 Blank
 // *** 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: