ScalaでProject Euler（97）

Problem 64

連分数です。連分数はペル方程式と関係が深く、この後の問題の前振りになっているかもしれません。
問題を解くには問題文に書かれた手順を実行すればよいです。

としてa, b, cの変化をチェックします。そしてループを検出します。(a, b, c)が以前と同じならループになっていることになります。しかし、どうループになっているかわからないので、単純に考えると(a, b, c)を常に記憶しておき今回の(a, b, c)が過去のものと一致していないか最初から調べる必要があるように思えます。

実はそんな必要はありません。なぜなら、

√N + [√N]

を連分数にすると純粋なループになっているからです。例えば、

√3 + 1 = [ 2; 1, 2, 1, ... ]

です。ですから、最初の(a, b, c)とだけ一致するかを調べればよいです。

この記事と次の記事の分をフォーラムにアップしました。

import scala.math._

def gcd(m :Int, n :Int) :Int = if(n == 0) m else gcd(n, m % n)

def is_square(n :Int) = {
    val m = sqrt(n.toDouble).toInt
    m * m == n
}

def num_steps(N :Int) :Int = {
    val n = sqrt(N.toDouble).toInt
    val x0 = (1, n, 1, 0)
    
    def next(x :(Int,Int,Int,Int)) :(Int,Int,Int,Int) = {
        val (a, b, c, m) = x
        val m1 = (a * n + b) / c
        val e = m1 * c - b
        val (a1, b1, c1) = (a * c, c * e, a * a * N - e * e)
        val d = gcd(gcd(a1, b1), c1)
        (a1 / d, b1 / d, c1 / d, m1)
    }
    
    def equalto(x :(Int,Int,Int,Int)) =
        x._1 == x0._1 && x._2 == x0._2 && x._3 == x0._3
    
    Iterator.iterate(next(x0))(next).takeWhile(x => !equalto(x)).size + 1
}

val M = 10000
print ((2 to M).filter(N => !is_square(N) && num_steps(N) % 2 == 1).size)