Project Euler Problem 026

http://projecteuler.net/index.php?section=problems&id=26
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2026

A unit fraction contains 1 in the numerator.
The decimal representation of the unit fractions with denominators 2 to 10 are given:

  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
 
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle.
It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d  1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

循環小数の循環する長さを計算する。

割り算の筆算の要領で計算したとき、一度出た被除数と除数のペアが再び出て来ると繰り返しに突入する。
今回の場合は除数は調べたい数で固定なので、一度出た被除数の位置を記録しておいて、また出た時に前回の位置との差が繰り返しの長さとなる。

import datetime


def unit_fraction(num):
    def it(num):
        a = 10
        while a:
            yield (a / num, a)
            a = (a % num) * 10

    result = '0.'
    used  = {}
    cycle = 0
    for i, (n, b) in enumerate(it(num)):
        if b in used:
            cycle = i - used[b]
            break
        used[b] = i
        result += str(n)
    
    return result, cycle


def euler026():
    maxc = 0
    maxv = 0
    for i in xrange(2, 1000):
        s, c = unit_fraction(i)
        if c > maxc:
            maxv = i
            maxc = c
        
    print '1/%d is %d cycle' % (maxv, maxc)


begin = datetime.datetime.now()
euler026()
end   = datetime.datetime.now()
print end - begin

答え: 983
実行時間: 0.080350秒くらい (resultを削除して計った)