PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 601 / Divisibility streaks

正の整数 n に対して関数 streak(n)=kを「n+k が k+1で割り切れないような最小の正の整数 k」で定義する。たとえば streak(13)=4である。

  • 13 は1で割り切れる
  • 14 は2で割り切れる
  • 15 は3で割り切れる
  • 16 は4で割り切れる
  • 17 は5で割り切れない

同様に

  • 120 は1で割り切れる
  • 121 は2で割り切れない

から streak(120)=1 である。

streak(n)=s (1< n< N)をみたす整数 n の個数を P(s,N) とする。
P(3,14)=1, P(6,10^6)=14286 である。

1以上31以下の i に対する P(i,4^i) の和を求めよ。

Problem 601 - Project Euler


a, b の最大公約数を (a, b) であらわすとして
(n+k, k+1)=(n-1, k+1)

これが1になるような k が streak(n) です。

streak(13)=(12を割り切らない最小の自然数 - 1)=5-1=4

While や SelectFirst でも求められますが,階乗(!)を使うと速いです。

[1, 2, ..., k で割り切れる」≒「k! で割り切れる」です。ダブリ分を除いて正確な形に直すとこうなります。

[1, 2, ..., k で割り切れる」=「LCM(1, 2, ..., k)! で割り切れる」

「n は LCM(1, 2, ..., k)! で割り切れるが,LCM(1, 2, ..., k+1)! では割り切れない」となる最小の自然数 k が streak(n) です。

たとえば「100以下の自然数のうち 5! で割り切れるが,6! では割り切れない数の個数を求めよ」と言われたら,ガウス記号を使って
[100/5!] - [100/6!]
とするでしょう。P(s, N) も同じ方法で求められます。

後は微調整です。最初,s=1 の処理を間違えて答えが1つずれてしまいました*1

*1:最近の問題なので答えの数値は省略します。