既然要來記解題筆記就來順便記一下時不時會做的 Project Euler 好了。這裡的文章應該會一起排進慣例的週三更新當中，所以看到一篇筆記出來並不代表我剛解完這一題，而可能是好幾天前的事了 XD
我做 Project Euler 主要的工具是 Mathematica，因為很多數學相關的東西可以不用我自己寫；只有在一些資料結構用 MMA 不好寫或很需要效率的時候才會轉用 C++ 來寫的。我的 PE 帳號裡登記的使用語言也是 Mathematica。
另外，為了在全文章模式也作點簡單的防雷，每篇在討論的題目我會放在繼續閱讀之上，然後在前面寫一點這題可以公開的東西，例如簡評或我流翻譯等；在繼續閱讀的前一段我會放上我的 Project Euler 簽名圖，那之下就會來開始放雷了。
#168 – Number Rotations (難度 65%)
簡述這題是這樣的：
142857 這個數字，將其個位數放到最前面 (稱為其右旋轉) 得到 714285，而我們發現 714285 是 142857 的 5 倍整。試問，所有具有此種性質－－一數為其右旋轉的因數－－並且在 10 到 10100 之間的數的總和，其末五位是多少？
這題其實很久以前解過，但因為少考慮了一個東西所以 WA 了不少次，就被我放著了。最近回來重新思考才發現我少考慮的東西是什麼－－而說來有趣，題目用 142857 舉例正是讓我掉進這個陷阱的元兇 XD
就來認真算一下到底是什麼樣的數有這種性質好了。令 \(10a+b\) 是我們要找的數，它有 \(n+1\) 位數，且 \(0\leq b\leq9\)。那這個性質可以表示成：存在正整數 \(k\) 滿足 \(k(10a+b)=b\cdot10^n+a\)。整理一下可得 $$a\cdot(10k-1)=b\cdot(10^n-k)\\a:b=(10^n-k):(10k-1)$$ 我們要找的 \(a\) 和 \(b\) 顯然是整數，但是對 \(k\geq2\) 的狀況 \(10k-1\) 不是一位數，因此我們會需要這個比能夠約分，才能找出我們要的 \(a\) 和 \(b\) 來。雖然題目沒有明寫著限制這個倍數 \(k\) 的範圍，但其實隱藏著是有一個限制在的：不可能是 10 倍或以上；其原因是：因為成為倍數的數是原數的右旋轉，這兩個的位數相同，因此相除的答案不可能超過 10。
以題目舉例的 142857 來說，這個狀況裡 \(a=14285, b=7, k=5, n=5\)；我們有 $$(10^n-k):(10k-1)=(10^5-5):49=99995:49=14285:7$$ 滿足條件。
自然地，要找出所有解就是從上面這條關係式出發，去找 \(10^n-k\) 是 \(10k-1\) 倍數的所有 \(n\) 出來。這是所謂的離散對數問題：我們想找滿足 \(10^n\equiv k\mod (10k-1)\) 的解 \(n\)。這個問題目前並沒有多項式解，因此單純地試過所有 \(n\) 的偽多項式解就已經足夠使用了。
下一個問題是：如果 \(10k-1\) 不是質數的話，有可能上式約一半就可以有讓 \(b\) 是一位數的解了。這其實拿題目舉的例子就可以看得出來：對 \(k=5\) 去求模 49 的話，會求得 \(10^{41}\equiv5\mod 49\)；但若是只要求模 7 的話，就能求得範例的 \(10^{5}\equiv5\mod 7\)。不過這並不是問題，因為我們這樣只有求出 \(n\)，並沒有實際求出 \(a\) 和 \(b\) 來；接下來還是得要算出 \(\frac{10^n-k}{10k-1}\)是多少，再列出所有比例相同的倍數出來。就來列出這個大數吧：$$\frac{10^{41}-5}{49}=2,040,816,326,530,612,244,897,959,183,673,469,387,755$$ 它對應 \(b=1\)，也就是它尾巴黏個 1 就是「答案」。顯然這裡乘以 1 到 9 都是可能的 (a,b) 解，所以這裡的「答案」有：
- 20,408,163,265,306,122,448,979,591,836,734,693,877,551
- 40,816,326,530,612,244,897,959,183,673,469,387,755,102
- 61,224,489,795,918,367,346,938,775,510,204,081,632,653
- 81,632,653,061,224,489,795,918,367,346,938,775,510,204
- 102,040,816,326,530,612,244,897,959,183,673,469,387,755
- 122,448,979,591,836,734,693,877,551,020,408,163,265,306
- 142,857,142,857,142,857,142,857,142,857,142,857,142,857
- 163,265,306,122,448,979,591,836,734,693,877,551,020,408
- 183,673,469,387,755,102,040,816,326,530,612,244,897,959
這裡我們看到了熟悉的 142,857 以重覆了七次的形式出現在這裡了。也就是說，就算先除了 49 找次方，但只要乘上 7 倍還是能找得到除以 7 能找到的答案的 (因為個位就是 7 嘛)。不過這裡還有另一個問題：這九個數中前面四個數其實並不滿足題意。就拿第一個來說吧，它的 \(k=5\) 倍是上面的第五個數，可以看到這並不是直接的右旋轉，而是要在中間插入一個 0。原因很簡單：\(10k-1\) 是兩位數。由於 \(a\) 的值是 \(\frac{10^n-k}{10k-1}\)，十倍加 1 會得到一個約略是 \(\frac{10^n}{k}\) 的數，小於 \(10^n\) 因此不足 \(n+1\) 位。不過既然知道大略是多少，也就知道只要乘以至少 \(k\) 倍就會是位數足夠的答案了。
這裡就可以來提一下我很久以前被誤導的是什麼了：當時的我沒有觀察到上面兩件事，因此擅自認定 \(k=5\) 的狀況特殊到只有 142857 是答案，所以漏算了上面列表中能當答案的五個數中的四個…… orz
上面這組重覆了七次的 142857 也告訴了我們另一件重要的事：如果一個數是答案，那這個數重覆任意多次合併起來也是答案；理由很簡單，想像一下直式乘法就好。因此我們只要對所有這樣找出來位數符合的位數，算一下 100 位可以擺多少次，把後五位乘上那麼多次累計起來就好了。幸運地所有這些數都至少六位，所以直接取模 105 就行了。
But wait, there’s more!
從開篇到現在我有一個討論前提只有提過一次：\(k\geq2\)。
\(k=1\) 的狀況稍微地不太一樣：如果去解那個比的話，因為 \(10k-1=9\)，所有整數 \(n\) 都會滿足 \(10^n-1=999…999\) 是 9 的倍數。一除就知道 \(a\) 是個全部都是 1 的 repdigit，乘上個位數位數就表示所有 repdigit 都是答案－－不過用看的也看得出來 \(k=1\) 倍的數就是所有的 repdigit。它們都是答案的問題在於，我們不能用單一解取後五位，因為這是僅有的一個 \(a\) 除出來不足五位的狀況 (\(a=1\))；不過因為也就僅有這一個，只要另外算出來再加進去就行了－－至少五位的狀況有 96 種，然後再算入 11, 111, 1111, 所以 repdigit 1 總和的後五位是 \(11111\times96+1233\equiv67889\mod10^5\)；其他 repdigit 類推即可。把這些全部加總起來才是最終的答案。實際答案是多少避免直接爆答案的雷就不在這裡寫出來了。