ScalaでProject Euler（27）

Problem 14

Rangeオブジェクトの罠

RangeオブジェクトはPythonのxrangeに似ています。すなわち、等差数列の最初と最後（と公差）だけ持ちます。

val N = 1e8.toInt
println ((1 to N).reduceLeft(-_ + _))

しかし、一度なにか操作するとVectorオブジェクトになり各要素を保持します。

val N = 1e8.toInt
println ((1 to N).filter(0 <).reduceLeft(-_ + _))

上のコードは結果が返ってきますが、このコードはメモリが足りないらしく落ちてしまいます。Pythonの次のようなコードと同じように考えてはいけないんですね。

from itertools import *

N = 10 ** 8
print reduce(lambda x, y: -x + y,
            ifilter(lambda x: x > 0, xrange(1, N + 1)))

Pythonと同じように組みたければItertorを使えばよいでしょう。Iterator#rangeはPythonのxrangeとほとんど同じです。

val N = 1e8.toInt
println (Iterator.range(1, N + 1).filter(0 <).reduceLeft(-_ + _))

問題はとりあえず1個ずつ再帰的に長さを求めます。

def Collatz(n :Long) :Int =
    if(n == 1)
        1
    else if(n % 2 == 0)
        1 + Collatz(n / 2)
    else
        1 + Collatz(n * 3 + 1)

val N = 1e6.toInt
val a = Iterator.range(N / 2, N).map(n => (Collatz(n), n))
println (a.max._2)