算額（その1454）
山形県高畠町亀岡 亀岡文殊（松髙山大聖寺文殊堂）
五輪教一：黄金比の眠るほこら，日本評論社，2015年7月10日
キーワード：中国剰余定理
#Julia, #SymPy, #算額, #和算
ある同好会の一行が亀岡文殊を参拝した。総人数を x としたとき，x を 5 で割れば 1 余り，7 で割れば 2 余り，9 で割れば 3 余り，11 で割れば 4 余り，13 で割れば 5 余り，17 で割れば 6 余る。総人数は何人か。
中国剰余定理を使えば一発で答えが出る。
Julia の SymPy の元は Python の sympy である。crt はインポートされていないので，明示的に sympy.ntheory.modular.crt として呼び出す。
using SymPy
#from sympy.ntheory.modular import crt
# 剰余の条件
moduli = [5, 7, 9, 11, 13, 17] # 除数のセット
remainders = [1, 2, 3, 4, 5, 6] # 剰余のセット
# 中国剰余定理を使用して解を求める
solution = sympy.ntheory.modular.crt(moduli, remainders) # 最小解と周期が返される
(698196, 765765)
総勢 698196 人である。
検算で正しい解であることがわかる。
mod.(698196, moduli) |> println
[1, 2, 3, 4, 5, 6]
ブルートフォースでやってみる。0.1 秒で計算できた。
@time begin
for n = 1:1000000000
all(mod.(n, [5, 7, 9, 11, 13, 17]) .== [1, 2, 3, 4, 5, 6]) && (println(n); break)
end
end
698196
0.105789 seconds (4.90 M allocations: 213.974 MiB, 23.61% gc time, 14.33% compilation time)
