Skip to content

Instantly share code, notes, and snippets.

@seratch

seratch/gist:1216403

Created September 14, 2011 12:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save seratch/1216403 to your computer and use it in GitHub Desktop.
Save seratch/1216403 to your computer and use it in GitHub Desktop.
Download ZIP
S99 P36-41 My Work
Raw
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_work.scala
import org.scalatest.Assertions.intercept
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)
case class P35Int(i: Int) {
def primeFactors: List[Int] = {
def _pf(result: List[Int], j: Int): List[Int] = {
if (j > 1) {
(2 to j) foreach {
case k if j % k == 0 => return _pf(k :: result, j / k)
case _ =>
}
}
result
}
_pf(Nil, i) reverse
}
}
implicit def fromIntToP35Int(i: Int): P35Int = P35Int(i)
}
// P36: Determine the prime factors of a given positive integer (2).
// 素因数分解して(素数,出てきた回数)のtupleのListを返す
object P36 {
case class P36Int(i: Int) {
// from P13
def encode[T](list: List[T]): List[(Int, T)] = {
if ( list.isEmpty ) Nil
else {
val (packed, next) = list span { _ == list.head }
next match {
case Nil => List((packed.length, packed.head))
case _ => (packed.length, packed.head) :: encode(next)
}
}
}
import S99Int._
def primeFactorMultiplicity: List[(Int, Int)] = {
encode(i.primeFactors) map { case (factor,count) => (count,factor) }
}
def primeFactorMultiplicityAsMap: Map[Int, Int] = {
encode(i.primeFactors) map { case (factor,count) => (count,factor) } toMap
}
}
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.
// P34でやったオイラーのファイ関数をP36の実装を使って改善する
object P37 {
case class P37Int(i: Int) {
import P36._
def totient: Int = {
i.primeFactorMultiplicity.foldLeft(1) {
(res, fm) => {
fm match { case (f, m) => res * (f-1) * math.pow(f, (m-1)).toInt }
}
}
}
}
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 resultAndTime[A](block: => A): (A,Long) = {
val start = System.currentTimeMillis
val result = block
val spentMillis = System.currentTimeMillis - start
(result, spentMillis)
}
def test {
import S99Int._
import P37._
val n = 10090
val (p34result, p34time) = resultAndTime{ n.totient34 }
val (p37result, p37time) = resultAndTime{ n.totient }
println("P34(" + n + "): " + p34time + " ms.")
println("P37(" + n + "): " + p37time + " ms.")
p37result should equal(p34result)
p37time should be < p34time
}
}
// 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] = {
import S99Int._
r filter { _.isPrime } toList
}
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) {
import S99Int._
def goldbach: (Int, Int) = {
if (i <= 2 || i % 2 != 0) throw new IllegalArgumentException
else {
val firstOrNot = (2 to i) find { n => n.isPrime && (i-n).isPrime }
firstOrNot match {
case Some(first) => (first, i-first)
case _ => throw new IllegalArgumentException
}
}
}
}
implicit def fromIntToP40Int(i: Int): P40Int = P40Int(i)
def test {
intercept[IllegalArgumentException] { 1.goldbach }
intercept[IllegalArgumentException] { 3.goldbach }
intercept[IllegalArgumentException] { 5.goldbach }
4.goldbach should equal((2,2))
6.goldbach should equal((3,3))
8.goldbach should equal((3,5))
10.goldbach should equal((3,7))
12.goldbach should equal((5,7))
14.goldbach should equal((3,11))
16.goldbach should equal((3,13))
18.goldbach should equal((5,13))
20.goldbach should equal((3,17))
22.goldbach should equal((3,19))
24.goldbach should equal((5,19))
26.goldbach should equal((3,23))
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 = goldbachListLimited(r, 1)
def goldbachListLimited(r: Range, limit: Int): String = {
import P40._
val filtered = r filter { n => n > 2 && n % 2 == 0 }
val acceptables = filtered collect { case n if n.goldbach._1 > limit => n }
(acceptables map {
case i => {
i.goldbach match { case (f,s) => i + " = " + f + " + " + s }
}
}).mkString("\n") + "\n"
}
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