絶滅

どうでもいい

Project Euler - Problem 168

f:id:my316g:20170801170253p:plain

状況です

長らく放置している間にDifficultyソートが出現

f:id:my316g:20170731093836p:plain

ということで低難易度から順に解こうとしたのですが,どうやら問題IDがでかい(挑戦者が少ない)と生存バイアスがやばいらしく撃沈が続きました.

大人しく若い番号で解けそうなものから潰していく,そういうわけでProblem 168です.



Number Rotations

Problem 168

数 142857 について考える.末尾の数字 (7) を先頭に持ってくると 714285 が得られる.
この操作を"右回転"と呼ぶ.
714285 = 5 * 142857 である.
これは 142857 という数の珍しい性質を表している.すなわち,
"ある数 n について,n を右回転したものが n で割り切れる"

このような性質を持つ整数 n (10 < n < 10100) について,その総和の下位五桁を答えよ.



雑な和訳おわり

巡回数の問題か~と早とちりして素数の逆数とか循環小数の循環節の長さとかダラダラ調べ続けて変な論文読んだりしてたら時間がドブ川に流れていった.思考が脇道に逸れすぎた人間の末路は碌なものにならないので,あまり複雑に考えず一からやっていくのが正しい.


数 n の右回転を Rot(n) で表す.つまり Rot(142857) = 714285.
末尾の数字とそれ以外を分けて考えるとなんか見えてくる.

142857 = 10 * 14285 + 7
Rot(142857) = 714285 = 105 * 7 + 14285


つまり,

n = 10 m + r
Rot(n) = 10d-1 r + m


d は n の桁数.r は 一桁の自然数, m は d-1 桁の自然数になる.

問題文より Rot(n) は n で割り切れるとあるので,一桁の自然数 k を用いて

Rot(n) = n k


と書ける.先程の式を代入すれば,

10d-1r + m = (10 m + r) k


これを m について解くと,

$\displaystyle m = \frac{ 10^{d - 1} - k }{ 10 k - 1 } r$


もとの n に代入すれば,

$\displaystyle n = 10m + r = 10 \cdot \frac{ 10^{d - 1} - k }{ 10 k - 1 } r + r = \frac{ r(10^{d} - 1) }{ 10k - 1 } $


ここで

$\displaystyle 10^{d} - 1 = \underbrace{999 \cdots 999}_{d} = 9 R(d)$


より,

$\displaystyle n = \frac{ 9 r }{ 10k - 1 } R(d)$


となる.R(d) は 1 が d 個連続するレピュニット(repunit)と呼ばれる数で,Project Euler ではたびたび登場する (e.g. Problem 129).

102 < n < 10100より 1 < d < 100.それと 1 ≦ k ≦ 9,1 ≦ r ≦ 9 なので,この 3 つの変数についてループを回し,n が d 桁の整数となる場合を拾っていけばいい.

具体的には,k と r を先に決めて 9r / (10k - 1) を約分して,得られた分母が R(d) を割り切るかどうか 1 < d < 100 について調べていく.最後に n が d 桁となっているか確認.

R(d) の a による剰余を求めるのは意外と簡単でたとえば a = 7 とすると,

\begin{align} 1 &\equiv 1 \\\ 10 &\equiv 1 \times 10 \equiv 3 \\\ 100 &\equiv 3 \times 10 \equiv 2 \\\ 1000 &\equiv 2 \times 10 \equiv 6 \\\ 10000 &\equiv 6 \times 10 \equiv 4 \text{ (mod 7) }\\\ & \ \ \vdots \end{align}


これを 1 行目から d 行目まで足し合わせればよい.


解答形式は下位五桁ということでオーバーフローしない美しい方法がありそうですが,だるいので Python3.x で適当にやりました.臨機応変にいきたい.

import math

def gcd(a, b):
    na = a; nb = b
    while a % b != 0:
        a = a % b; tmp = a; a = b; b = tmp
    return b
    
def repunit(n):
    ret = 0
    for i in range(n):
        ret *= 10
        ret += 1
    return ret
    
def PE0251():
    ans = 0
    for k in range(1,10):
        for r in range(1,10):
            p = 9 * r
            q = 10 * k - 1
            g = gcd(p, q)
            p /= g; q /= g
            rem = 1
            remsum = 1
            for d in range(2, 101):
                rem *= 10
                rem %= q
                remsum += rem
                remsum %= q
                if remsum == 0:
                    n = 9 * r * repunit(d) // (10 * k - 1)
                    if d - math.log10(n) <= 1:
                        ans += n
    ans %= 100000
    print(ans)
                        
PE0251()

初心者が付け焼き刃で書いたコードなのでアレです.というか python キモいくらい便利だな…