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

この記事の所要時間：約 2分5秒

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 を用意しました.

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))

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))

計算時間は 0.00013sec でした.

答えはこの下にあります. 反転してください.

A. 1617243

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

No.601 Divisibility streaks

問題.

考え方とプログラム例.

共有:

関連

関連記事