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)\) の和を求めよ.
考え方とプログラム例.
\(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 を用意しました.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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)) |
