Project Euler 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の余りを出す
④余りのリストに同じ余りがあるかチェック
⑤なければリストに追加し、③に戻る
⑥同じ余りがあればそこから循環するので循環節の長さを返す
これをそのままコードにしています。
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で割る
コード
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だったりするので分母が非素数だった場合の循環節のルールがよくわかりません…