数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

プロジェクトオイラー601. ~ Divisibility streaks ~


スポンサードリンク

No.601 Divisibility streaks

問題.

正の数  n に対して,  n+k k+1 で割り切れないような最小の整数  k をもって関数  streak(n)=k と定義しよう.

例えば:

13 は 1 で割り切れる

14 は 2 で割り切れる

15 は 3 で割り切れる

16 は 4 で割り切れる

17 は 5 で割り切れない

よって,  streak(13)=4.

同様に,

120 は 1 で割り切れる

121 は 2 で割り切れない

よって,  streak(120)=1

 1 < n < N を満たし,  streak(n)=s である整数  n の個数を  P(s, N) と定義する.

例えば,  P(3, 14)=1, P(6, 10^6)=14286 となる.

では,  i が 1 から 31 の範囲にあるときの  P(i, 4^i) の和を求めよ.

 

 

考え方とプログラム例(python3).

 n+k k+1 で割り切れる  \Leftrightarrow  n-1 k+1 で割り切れる

なので,

 streak(n)=k  \Leftrightarrow  n-1 k 以下のすべての自然数で割り切れて,  k+1 では割り切れない

と言い換えることができます.


そこで, g0 を  1, 2, \ldots, k の最小公倍数, g1 を  1, 2, \ldots, k, k+1 の最小公倍数とすると,  P(k, N) N 未満の整数のうち, g0 で割り切れて g1 で割り切れないものの個数となります.


今回は最大公約数を求める gcd をユークリッドの互除法で実装し, それを用いて最小公倍数 lcm を用意しました.

 

def gcd(a, b):
    if a < b:
        c = b
        b = a
        a = c
    if b == 0:
        return a
    return gcd(b, a % b)
def lcm(a, b):
    g = gcd(a, b)
    if g == 0:
        return 0
    else:
        return a * b / g
g0 = 1
g1 = 1
P = []
for i in range(1, 32):
    g0 = g1
    g1 = lcm(g0, i+1)
    N = 4 ** i - 2
    P.append((N // g0) - (N // g1))
print(sum(P))