Project Euler Problem 26 循環小数の循環節

Python ProjectEuler

循環小数の秘密というサイトによると，既約分数を少数になおしたものは次の3つに分類されます．

  1. 有限小数
  2. 純循環小数
  3. 混循環小数

これらは分母の値を素因数分解することで次のように区別できます．

  1. 素因数が2と5のみで構成されるならば，有限小数
  2. 素因数に2と5が含まれていなければ，純循環小数
  3. それ以外の場合，混循環小数

そして，循環小数nとその循環節の長さlについて次のような性質が成り立ちます．
10^l\equiv1 (mod \frac{n}{2^a5^b})※aとbはそれぞれ2と5の素因数の個数
これにより循環節の長さを計算するプログラムを書くことができます．

def cycle(n):
    while n % 2 == 0:
        n /= 2
    while n % 5 == 0:
        n /= 5
    if n == 1:
        return 0
    count = 1
    while 10**count % n != 1:
        count += 1
    return count

循環小数に関する下記のサイトの議論は非常に参考になったので再掲します．