前回の定義でB(n)は、
10e ≡ 1(mod n)
を満たす最小のe(> 0)としました。これをnの既約剰余類群での10の位数と言います。これを効率的に求めればよいです。
nを素因数分解して、
n = p1e1...pmem
とすると、
B(n) = lcm(B(p1e1), ... , B(pmem))
となります。よって、個々のB(pe)を計算すればよいです。オイラーの定理、
10φ(pe) ≡ 1(mod pe) （pと10は互いに素）
で、φ(pe) = (p - 1)pe-1なので、B(pe)は(p - 1)pe-1の約数です。例えば、B(169)を考えてみましょう。φ(169) = 12 * 13 = 22 * 3 * 13です。10のべき乗が1になるのにそれぞれの素因数が何個要るか調べます。まず2ですが、1078 ≡ 1で1039 ≡ 168なので、2は1個要ることになります。また、1052 ≡ 146なので3は1個、1012 ≡ 53なので13も1個要ることになります。結局、B(169) = 2 * 3 * 13 = 78となります。
25で0.13s、200で18sでした。
