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

この記事の所要時間: 156

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

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加