ScalaでProject Euler（48）

Problem 29

この問題は100までと範囲が非常に狭いので次のような乱暴なコードでも瞬時に答えが出てしまいますが、

def pows(n :Int) =
    Iterator.iterate(BigInt(n * n))(_ * n).take(N - 1)

val N = 100
println (Iterator.range(2, N + 1).flatMap(pows).toSet.size)

もっと大きなNに対して解こうとすると楽しくなってきます。以前にも考察しました。

Project Euler 29（1） - 桃の天然水
Project Euler 29（2） - 桃の天然水
Project Euler 29（3） - 桃の天然水
Project Euler 29（4） - 桃の天然水

ここでは10⁷まで求めました。しかし、なにか中途半端に終わったような記憶があります。このときはPythonだったので、Scalaでは少なくとも1桁は多く求めようと思います。

メモリ制限

では上のコードでどこまで求められるか試してみたところ、N = 680くらいが限度でした。一方Pythonでは、

from itertools import *

def pows(n):
    m = n
    while True:
        m *= n
        yield m

N = 1500
print len(set(n for a in xrange(2, N + 1) for k, n in
                takewhile(lambda (k, n): k <= N, izip(count(2), pows(a)))))

N = 1500でも答えが出ました。いつもScalaは300MBくらいしかメモリを使っていないような気がするのですが、どこかで制限をかけているのでしょうか。
調べてみると、次のように環境変数を設定すれば使用できるメモリの上限を設定できるようです。

set JAVA_OPTS=-Xmx1024M

これでN = 1000でも答えが出ました。しかし、Pythonより1.5倍くらいメモリを消費して、2倍近く遅いという結果になりました。