3797 → 379 → 37 → 3のような右から短縮しても素数になる数は逆向きに生成できます。まず1桁の素数[ 2, 3, 5, 7 ]を用意して、それぞれに0〜9を右に加えて、元が2なら[ 23, 29 ]が素数なのでこれは「右短縮」になっています。さらに23に0〜9を右に加えて素数になっているか調べる、といったように生成できます。逆に3797 → 797 → 97 → 7のような「左短縮」の数は7に0〜9を加えて生成します。
さて、「右短縮」の素数はそのような2桁の素数があればその一つから3桁の素数は、素数定理より1/logN程度の確率で素数なので、10/logN程度の個数生成されます。Nはその3桁の素数です。
e10 = 22026.46…
なので、3桁なら10/logNは1より大きく「右短縮」の素数は2桁のそれより増えていることが期待されます。そして、ピークは4桁か5桁になりそうです。
しかし、「左短縮」の素数は、左から数字を付け加えるので、下1桁が3か7になっており、素数である確率が高くなっています。明らかに素数でない下1桁0, 2, 4, 5, 6, 8ではないことから素数である確率は2.5/logNになっているはずです。このことから「左短縮」の素数は「右短縮」の素数のピークの2.5倍の桁でピークになっていることが期待されます。すなわち「右短縮」の素数のほうがずっと少なくてすぐに新たに生成されます。
だから、「右短縮」の素数を列挙して、それが「左短縮」になっているかを調べればよいです。
しかし、マージ法を使えばどちらが少ないかを考える必要はありません。どちらも昇順に生成すれば、自然に短い方に合わせて途中で打ち切られます。
マージ法はIteratorよりStreamの方が書きやすいです。
Stream.consの代わりに#::が使えるのですね。これは書きやすいし読みやすい。
def is_prime(n :Int) = if(n < 2) false else Iterator.from(2).takeWhile(m => m * m <= n).forall(m => n % m != 0) def merge(s1 :Stream[Int], s2 :Stream[Int]) :Stream[Int] = (s1, s2) match { case (Stream(), _) => Stream() case (_, Stream()) => Stream() case (h1 #:: t1, h2 #:: t2) if h1 < h2 => merge(t1, s2) case (h1 #:: t1, h2 #:: t2) if h1 > h2 => merge(s1, t2) case (h1 #:: t1, h2 #:: t2) => h1 #:: merge(t1, t2) } def truncatable_left() = { def f(m :Int) :Int = if(m == 0) 1 else f(m / 10) * 10 def next(s :Stream[Int]) = for(d <- Stream.range(1, 10); m <- s; n = d * f(m) + m if is_prime(n)) yield n val ps = Stream(2, 3, 5, 7) Stream.iterate(ps)(next).takeWhile(Stream() !=).flatMap(m => m) } def truncatable_right() = { def next(s :Stream[Int]) = for(m <- s; d <- Stream.range(1, 10); n = d + m * 10 if is_prime(n)) yield n val ps = Stream(2, 3, 5, 7) Stream.iterate(ps)(next).takeWhile(Stream() !=).flatMap(m => m) } println (merge(truncatable_left, truncatable_right).filter(10 <).sum)
