Project Euler

https://projecteuler.net/problem=302から順に等式が成り立つかどうか調べていっても十分間に合うのですが、これは重複組み合わせを使うと計算量が減ります。1634を分解して4乗和を取ると1634になりますが、1346や6431も1634になります。4桁で重複が無いから24個の数がが同じになることが分かります。6桁だと重複組み合わせは通りしかありません。なので、重複組合せをだして、[1, 3, 4, 6]のとき、4乗和が1634になって、それを数字に分解してソートすると、[1, 3, 4, 6]で元と同じになるので、1634が該当する数になります。この方法で17乗ま…

https://projecteuler.net/problem=29前回は例えば2乗までのとき何個がダブるかをナイーブに数えていましたが、2乗までなら2～N/2がダブると分かるので、数えるまでもありません。6乗までだと、N/6～N/3の間は2から5の倍数はダブりますが、重複を考えると包除原理を使わないといけません。しかし、前回よりかなり速いはずです。最後のところで多倍長整数を使うとより大きいときも計算できます。でも30秒程度でした。実際のところ、が素数でないと速いです。 from collections import Dict from math import min, max, abs i…

https://projecteuler.net/problem=29こういう問題はダブりの方を数える方が速いです。 例えば、5をベースで考えると、などダブりがあります。まで、49個あります。これは6でも同じです。などです。 このように、100までで何乗まであるかが同じならダブりの個数は同じです。6乗まであるのは2だけ、4乗まであるのは3だけ、2乗まであるのは6つなどです。 from collections import Set, KeyElement import sys #################### Power #################### @value struc…

https://projecteuler.net/problem=29ならとしてダブりを排除します。ただし、がべき乗数ならべき乗を外に出します。例えば、とします。 MojoでSetを使うには、KeyElementを継承します。 from collections import Set, KeyElement import sys #################### Power #################### @value struct Power(KeyElement): var b: Int var e: Int fn __init__(inout self, b: Int, …

https://projecteuler.net/problem=27素数の判定をどれくらい大きさまで行っていいか分からないので、ナイーブに判定してメモ化してみました。 MojoではDictを使えるようになりました。 from collections import Dict fn main() raises: var d = Dict[String, Int]() d["a"] = 1 print(d["a"]) # 1 print("a" in d) # True なので、これをメモ化に使おうとしましたが、 from collections import Dict var memo = Di…

https://projecteuler.net/problem=26各に対し、となる最小の自然数を求めます。オイラーの定理からなので、の約数となります。 実際のところは、素数の大きい方から順に調べて、周期がその数より1小さいものがあれば、その素数が求める答えです。 from math import min import sys #################### library #################### def div_pow(n: Int, d: Int) -> Tuple[Int, Int]: var m = n var e = 0 while m % d == 0…

https://projecteuler.net/problem=25真面目にフィボナッチ数列を求めてもいいのですが、以下のように概算できます。 漸化式から、 となります。10進でN桁として、 となる最小のを求めればよいです。 右辺第2項は小さいので無視すると、 となります。 ところで、Mojoにsqrtは無いようなので0.5乗を使います。また数学関数は、SIMD用しか用意されていないので、 var a = SIMD[DType.float64, 1](2.0) var b = log10(a) print(b[0]) # 0.3010299956639812 のように、SIMDを経由して計算…