Problem 552 「連立合同式 2」

数列 A を次のように定める。

Ai = (1 ≦ k ≦ i で Ai mod pi = i となるような最小の自然数) とする。

例えば, A2 = 5 である。 なぜなら,

  &tex{A_{2}}; mod 2 = 1
  &tex{A_{2}}; mod 3 = 2

を満たし, かつこれが最小だからである。

また, A3 = 23 である。 なぜなら,

  &tex{A_{3}}; mod 2 = 1
  &tex{A_{3}}; mod 3 = 2
  &tex{A_{3}}; mod 5 = 3

を満たし, かつこれが最小だからである。

また, A4 = 53, A5 = 1523 である。また, A10 = 5765999453 である。

そこで, S(n) = (1 ≦ i ≦ n (i は素数) で 数列 A の中に i で割り切れるものが1つ以上あるような整数 i の個数) とする。 例えば, S(50) = 5 + 23 + 41 = 69 です。 なぜなら, 5 は A2 = 5 を割ることができ, 23 は A3 = 23 を割ることができ, 41 は A10 = 5765999453 を割ることができるからである。 また, 50以下の5, 23, 41ではない他の12個の素数は, Aに入っているいずれの整数も割ることができない。

そのとき, S(300000) を求めなさい。


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-08-07 (日) 00:52:05 (231d)