這題是在去設定Cluster的時候看到的，發現這題蠻簡單的，所以回家的時候就順手解了它。

題目是這樣說的，有一種數叫做cyclic number，仔細的性質大家就去看一下Wikipedia上的介紹吧，這裡就不多加說明了。那麼題目要找的是一個開頭是00000000137，而結尾是56789的一個唯一的cyclic number，然後請我們算出它的數字和。

從142857說起

這個數字我是在高中的時候第一次聽到的，當時聽到的時候真是十分的驚訝，原來這世界上有這麼美的數字。

後來在學校的BBS裡面發現有很多更深入的討論，所以也對這種類型的數字有了一點點初步的了解。

BTW，在我大學的時候參加迎新宿營的時候，剛剛好也出了類似的題目，所以也就順手秒殺了XD，據說當時嚇到很多學長姐，因為他們本來想用這題來拖點時間的，結果沒有想到人算不如天算啊XDDD

回到正題

那麼這題的解題關鍵是什麼呢？其實每一個cyclic number都會有一個跟它對應的分數(如果妳不知道，可以看看上面wiki的連結，裡面應該是會有講才是。)，像是142857對應的就是1/7:p

所以現在問題就變成找一個質數p使得下面的事情成立：

• 1/p它前面的位數是0.00000000137
• (10^(p - 1) - 1) / p的後面幾位是56789
• 再來我們只要去算9 * (p - 1) / 2就會是它的數字和了(wtf!?)

前兩點聽起來很合理，但是第三點是什麼？為什麼這樣就可以算出來數字和呢？ 原因是這樣的，我們知道1/p的循環節長度是p-1，而又因為1/p + (p - 1)/p = 1 = 0.999...，所以我們知道數字和就是9 * (p - 1) / 2，是不是很漂亮呢:p

下面附上程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#!/usr/bin/env python
from euler import is_prime

def is_primitive(num, prime):
    tmp = prime - 1
    idx = 2
    while idx**2 <= tmp:
        if tmp % idx == 0:
            if pow(num, idx, prime) == 1 or pow(num, tmp / idx, prime) == 1:
                return False
        idx += 1
    return True

upper_bound = 729927007
lower_bound = 724709891

for num in xrange(lower_bound, upper_bound, 100000):
    if is_prime(num) and is_primitive(10, num):
        print((num - 1) * 9 / 2)

真是美麗的一題，謝謝Project Euler:)