問題
単位分数とは分子が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 を求めよ.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2026
回答
(1) 1/d の小数部の循環節の長さは、dが10^n-1を割り切る最小のnである点。
(2) 2,5等の因子は小数部の循環説の長さに寄与しない点。
の2点を前提(補足参照)に以下のコードを書いた。
get_prime_boolean, get_prime_listm get_primesの三点はmymathに収容しているので、そっちを参照してもよい。
コード
def get_prime_boolean(max):
bool = [False,False]+[True]*(max-1)
bool[4::2] = [False] * (len(bool[4::2]))
p = 3
p_max = int(math.sqrt(max))+1
while p<=p_max:
if bool[p]:
bool[p*2::p] = [False] * (len(bool[p*2::p]))
p+=2
return bool
def get_prime_list(bool):
length = len(bool)
return [i for i in range(2,length) if bool[i]]
def get_primes(max):
bool = get_prime_boolean(max)
list = get_prime_list(bool)
return {'bool':bool,'list':list}
def pe26():
MAX = 1000
seq = range(MAX)
ans = seq[3::10] + seq[7::10] + seq[9::10] + seq[11::10]
t = 9
while len(ans) > 1:
i = 0
while i < len(ans):
if (t%ans[i]) == 0:
ans.pop(i)
else:
i += 1
t = t*10 + 9
print ans[0]
import math
print math.log(t,10)
pe26()