Create a gist now

Instantly share code, notes, and snippets.

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:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment