MojoでProject Euler 25 - inamori’s diary

真面目にフィボナッチ数列を求めてもいいのですが、以下のように概算できます。
漸化式から、

$\displaystyle F_n = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)$
となります。10進でN桁として、
$log_{10}{F_n} \ge N-1$
となる最小の $n$ を求めればよいです。
右辺第2項は小さいので無視すると、
$\displaystyle n \ge \frac{N-1+\log_{10}{5}}{\log_{10}{\frac{1+\sqrt{5}}{2}}}$
となります。
ところで、Mojoにsqrtは無いようなので0.5乗を使います。また数学関数は、SIMD用しか用意されていないので、

    var a = SIMD[DType.float64, 1](2.0)
    var b = log10(a)
    print(b[0])    # 0.3010299956639812

のように、SIMDを経由して計算します。

from math import log10
import sys

fn log10_float(x: Float64) -> Float64:
    var x1 = SIMD[DType.float64, 1](x)
    var y1 = log10(x1)
    return y1[0]

fn f(N: Int) -> Int:
    var beta = (1+5.0**0.5)/2
    var y = log10_float(5.0**0.5)
    return int((N-1+log10_float(5.0**0.5))/log10_float(beta)) + 1

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