Project Euler 026

026

単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる.
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
0.1(6)は 0.166666... という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある.
d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ.

->次の問題

考え方

とりあえず、2・5以外の素数が分母の素因数に含まれると循環小数になるようです。

コード書いてから調べてみたところによると、フェルマーの小定理により、
2・5以外の素数pについて、1/pの循環小数はp-1桁で循環するとのこと。
ただ、これは循環節がp-1というわけではなく、p-1桁のところでは少なくとも循環するってことのようです。
1/3 = 0.33 33 33 33 33
1/7 = 0.142857 142857 142857
1/11 = 0.0909090909 0909090909 0909090909
つまり循環節はp-1の約数のどれかとなります。

上記を調べる前にコードを書いたので(T_T)、全ての数について循環節の数を調べていました。
まず、循環節の数を返す関数を定義しました。
手順としては、分母dについて
①1/dの余りを出す
②余りを[余りのリスト]に追加
③(余り*10)/dの余りを出す
④余りのリストに同じ余りがあるかチェック
⑤なければリストに追加し、③に戻る
⑥同じ余りがあればそこから循環するので循環節の長さを返す
これをそのままコードにしています。

euler026.py

def digits_recurring_cycle(denominator: int) -> int:
    """
    1/d(denominator)の循環小数の循環節の数を返す関数
    1/7 = 0.142857142857...循環節は6
    割り切れる場合は0を返す
    :param denominator: 分母 int
    :return: 循環節の数 int
    """
    remainder = 1
    remainders = []  # 各計算の余りを格納する
    while True:
        remainder = remainder % denominator  # 余りを求める
        if remainder == 0:  # 割り切れれば
            return 0
        # 出た余りが以前に出ていれば、そこから繰り返し(循環)に入るということ
        # 以前に同じ余りが出たところ(remainders.index(numerator))から
        # 今回出たところの直前(配列の終わり)までの長さが循環節の長さになる
        if remainder in remainders:  # 今回出た余りと同じ余りが以前出ていれば
            return len(remainders[remainders.index(remainder):])  # 循環節の長さを返す
        remainders.append(remainder)  # なければ余りのリストに追加して次のループへ
        remainder *= 10  # 余りを10倍して、次のループでもう一度denominatorで割る

コード

euler026.py

def main():
    n = 1000
    max_digits = 0
    answer = 0
    # 結果を見るに、探索範囲は素数だけでいいような気がする
    for i in range(3, n + 1, 2):
        digits = digits_recurring_cycle(i)
        if digits > max_digits:
            max_digits = digits
            answer = i
    print(f'{n}以下で1/dの循環節が最大となるのはd={answer}のとき、循環節は{max_digits}である')


def digits_recurring_cycle(denominator: int) -> int:
    """
    1/d(denominator)の循環小数の循環節の数を返す関数
    1/7 = 0.142857142857...循環節は6
    割り切れる場合は0を返す
    :param denominator: 分母 int
    :return: 循環節の数 int
    """
    remainder = 1
    remainders = []  # 各計算の余りを格納する
    while True:
        remainder = remainder % denominator  # 余りを求める
        if remainder == 0:  # 割り切れれば
            return 0
        # 出た余りが以前に出ていれば、そこから繰り返し(循環)に入るということ
        # 以前に同じ余りが出たところ(remainders.index(numerator))から
        # 今回出たところの直前(配列の終わり)までの長さが循環節の長さになる
        if remainder in remainders:  # 今回出た余りと同じ余りが以前出ていれば
            return len(remainders[remainders.index(remainder):])  # 循環節の長さを返す
        remainders.append(remainder)  # なければ余りのリストに追加して次のループへ
        remainder *= 10  # 余りを10倍して、次のループでもう一度denominatorで割る


if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')

paizaにて実行
結果 1000以下で1/dの循環節が最大となるのはd=983のとき、循環節は982である 0.15410661697387695 sec
結果を見るとなんとなく探索範囲は素数だけで良い気がしますが、
1/21の循環節が6だったりするので最も長い循環節になるのかなと思ったら1/49の循環節が42だったりするので分母が非素数だった場合の循環節のルールがよくわかりません…