MojoでProject Euler 57

https://projecteuler.net/problem=57

分子と分母は


と漸化式で表されます。
厳密には多倍長整数使いますが、実数でも問題ないです。分子が10を超えたら両方10で割ればよいです。

import sys


#################### BigInteger ####################

@value
struct BigInteger(Stringable):
    var v: List[Int]
    
    fn __add__(self, other: BigInteger) -> BigInteger:
        var v = List[Int]()
        var carry = 0
        for i in range(max(self.v.size, other.v.size)):
            var d1 = self.v[i] if i < self.v.size else 0
            var d2 = other.v[i] if i < other.v.size else 0
            var n = d1 + d2 + carry
            v.append(n % 10)
            carry = n // 10
        if carry > 0:
            v.append(carry)
        return BigInteger(v)
    
    fn __str__(self) -> String:
        var s = String()
        for i in range(len(self.v) - 1, -1, -1):
            s = s + str(self.v[i])
        return s
    
    @staticmethod
    fn create(owned n: Int) -> BigInteger:
        var v = List[Int]()
        while n > 0:
            var d = n % 10
            n //= 10
            v.append(d)
        return BigInteger(v)


#################### process ####################

fn f(N: Int) -> Int:
    var a1 = BigInteger.create(1)
    var a2 = BigInteger.create(1)
    var b1 = BigInteger.create(0)
    var b2 = BigInteger.create(1)
    var counter = 0
    for _ in range(1, N):
        var tmp = (a2, a1 + a2 + a2)
        a1 = tmp.get[0, BigInteger]()
        a2 = tmp.get[1, BigInteger]()
        var tmp2 = (b2, b1 + b2 + b2)
        b1 = tmp2.get[0, BigInteger]()
        b2 = tmp2.get[1, BigInteger]()
        if len(a2.v) > len(b2.v):
            counter += 1
    return counter

fn main() raises:
    var args = sys.argv()
    var N = atol(args[1])
    print(f(N))