Scalaで素数ものさしを探す
1 概要
京大生協で，目盛が素数だけの「素数ものさし」が売っているそうだ．
+-----------------------------------+
| |
| | | | | | | | |
+---+-+---+---+-------+---+-------+-+
2 3 5 7 11 13 17
この定規は，1cmから18cmまでのすべてを測ることができる(もちろん 1cm単位で)． たとえば 12cm は 17cmと 5cmの間で測れる． 他にこのような定規があるだろうか? Scalaでプログラムを書いて調べてみよう．
1.1 注意
本Webページの作成には Emacs org-mode を用い， 数式等の表示は MathJax を用いています． IEでは正しく表示されないことがあるため， Firefox, Safari等のWebブラウザでJavaScriptを有効にしてお使いください． また org-info.js を利用しており， 「m」キーをタイプするとinfoモードでの表示になります． 利用できるショートカットは「?」で表示されます．
1.2 参考リンク
2 考察
\(p_i\) を \(i\) 番目の素数とする． すなわち \(p_1=2\), \(p_2=3\), \(p_3=5\), … である．
\(n\) 番目の素数までを目盛とした全長 \(L\) cmのものさしを考える． \(L-1\) cm を測るためには 1cm あるいは \(L-1\) cm のどちらかに目盛がなければならない． 1cm の箇所には目盛がないので， \(L-1\) cm の箇所に目盛がある必要がある． すなわち \(L = p_n + 1\) である必要がある． したがって，以下を問題とする．
正整数 \(n\) が与えられた時， \(p_1\), …, \(p_n\) を目盛とする全長 \(p_n + 1\) cmのものさしが， 1cm から \(p_n + 1\) cm までのすべてを測れるかどうかを調べるプログラムを作成する．
3 素数
Scalaでリスト処理 で学んだように，素数かどうかは以下の関数での判定できる．
scala> def isPrime(p: Int) = (2 to math.sqrt(p).toInt).forall(p % _ != 0)
この isPrime を用いて，p より大きい最初の素数を返す関数 nextPrime(p) を定義する．
scala> def nextPrime(p: Int): Int = if (isPrime(p+1)) p+1 else nextPrime(p+1) scala> nextPrime(2) res: Int = 3
この nextPrime を用いて，n 番目までの素数のリストを返す関数 primes(n) を定義する． 作成は練習問題とする．
3.1 練習問題
- n 番目までの素数のリストを返す関数 primes(n) を定義せよ．n は 1以上とする．
- (解答例)
-
scala> def primes(n: Int): Seq[Int] = | if (n == 1) Seq(2) else { val ps = primes(n-1); ps :+ nextPrime(ps.last) } scala> primes(10) res: Seq[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)以下のようにも書ける．
scala> def primes(n: Int, p: Int = 2): Seq[Int] = | if (n == 1) Seq(p) else p +: primes(n-1, nextPrime(p)) scala> primes(10) res: Seq[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)さらに以下のようにすれば末尾再帰になる．
scala> def primes(n: Int, ps: Seq[Int] = Seq(2)): Seq[Int] = | if (n == 1) ps.reverse else primes(n-1, nextPrime(ps.head) +: ps) scala> primes(10) res: Seq[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
4 素数ものさしの判定
n 個の素数目盛を持つものさしは，両端を含めて 0 および \(p_n + 1\) も目盛と考えると都合が良い． これらの目盛を返す関数 ruler を定義する．
scala> def ruler(n: Int) = { val ps = primes(n); 0 +: ps :+ (ps.last+1) }
scala> ruler(7)
res: Seq[Int] = List(0, 2, 3, 5, 7, 11, 13, 17, 18)
2つの目盛の任意の組合せは，combinations メソッドで生成できる．
scala> ruler(7).combinations(2).toList res: List[Seq[Int]] = List(List(0, 2), List(0, 3), ..., List(17, 18))
したがって，測れる長さの集合は以下のようにして求めることができる．
scala> ruler(7).combinations(2).map(x => x(1)-x(0)).toSet res: Set[Int] = Set(5, 10, 14, 1, ..., 15)
この集合が 1 から 18 から成る集合と一致すれば良い．
scala> ruler(7).combinations(2).map(x => x(1)-x(0)).toSet == (1 to 18).toSet res: Boolean = true
そこで，与えられた目盛のリストですべての長さが測れるかどうかを調べる 関数 isComplete を定義する．
scala> def isComplete(ruler: Seq[Int]) =
| ruler.combinations(2).map(x => x(1)-x(0)).toSet == (1 to ruler.last).toSet
scala> isComplete(ruler(7))
res: Boolean = true
scala> ruler(8)
res: Seq[Int] = List(0, 2, 3, 5, 7, 11, 13, 17, 19, 20)
scala> isComplete(ruler(8))
res: Boolean = true
scala> ruler(13)
res: Seq[Int] = List(0, 2, 3, 5, 7, 11, ..., 41, 42)
scala> isComplete(ruler(13))
res: Boolean = false
4.1 練習問題
- 他にどのような素数ものさしが存在するか?
- (解答例)
-
scala> (1 to 30).filter(n => isComplete(ruler(n))) res: IndexedSeq[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 18) scala> (1 to 30).filter(n => isComplete(ruler(n))).map(n => ruler(n).last) res: IndexedSeq[Int] = Vector(3, 4, 6, 8, 12, 14, 18, 20, 24, 30, 32, 38, 44, 62)
- ruler(7) で，それぞれの長さを測る方法は何通りあるか?
- (解答例)
-
scala> val xs = ruler(7).combinations(2).map(x => x(1)-x(0)).toList xs: List[Int] = List(2, 3, 5, ..., 5, 1) scala> (1 to 18).map(x => xs.count(_ == x)) res: IndexedSeq[Int] = Vector(2, 4, 2, 3, ..., 1)
以下の方法もある．
scala> xs.groupBy(x => x).map(kv => kv._1 -> kv._2.size) res: Map[Int,Int] = Map(5 -> 3, 10 -> 2, 14 -> 1, 1 -> 2, ..., 15 -> 2)
- 62cm より長い素数ものさしは存在するか?