整数問題 3 題

Q1. 数列 F(n) を以下の漸化式で定義する。
F(0) = 3, F(1) = 0, F(2) = 2,
F(n) = F(n-2) + F(n-3) (n>2のとき)
このような数列において，n > 1 かつ F(n) の値が n が割り切れる場合を考える。
たとえば，n = 2, 3, 5, 7, 11, 13, 17, 19 のとき，F(n) の値はそれぞれ n で割り切れる。
19 は，このような性質を持つ 8 番目に小さな n で，この n に対する F(n) の値は 209 である。
このような性質を持つ 30 番目に小さな n に対する F(n) の値 P を求めよ。

Q2. 整数 n に対し，n の素因数のうちで最大のものを G(n) とする。たとえば，G(123456) = 643である。
G(P) の値 Q を求めよ。

Q3. 2, 3, 5, 7 はそれぞれ 1 番目，2 番目，3 番目，4 番目の素数である。k 番目の素数 p に対し，k もまた素数である場合に，p を「素数番目の素数」と呼ぶことにする。たとえば，3 と 5 は素数番目の素数であるが、2 と 7 はそうではない。
整数 n に対し，n 以下の素数番目の素数の和を H(n) と定義する。たとえば，H(100) = 317, H(1000) = 15489 である。
H(Q) の値 R を求めよ。

system.time({
  F = function(term) {
    a = 3
    b = 0
    c = 2
    n = 2
    count = 1
    repeat {
      n = n + 1
      d = a + b
      if (d %% n == 0 && (count = count + 1) == term) return(d)
      a = b
      b = c
      c = d
    }
  }
  P = F(30)

  G = function(n) {
    div = function(n) {
      if (n%%2 == 0) return(2)
      else if (n%%3 == 0) return(3)
      maxitr = floor(sqrt(n))
      i = 1
      repeat {
        i = i + 4
        if (i > maxitr) return(n)
        else if (n%%i == 0) return(i)
        i = i + 2
        if (i > maxitr) return(n)
        else if (n%%i == 0) return(i)
      }
    }
    result = NULL
    repeat {
      d = div(n)
      result = append(result, d)
      n = n/d
      if (n == 1) break
    }
    return(max(result))
  }
  Q = G(P)

  H = function(n) {
    tbl = 1:n
    tbl[1] = 0
    for (i in 2:floor(sqrt(n))) {
      if (tbl[i]) tbl[2:(n%/%i) * i] = 0
    }
    prime = tbl[tbl > 0]
    sum(prime[prime[!is.na(prime[prime])]])
  }
  R = H(Q)

  cat(sprintf("P = %.f, Q = %.f, R = %.f\n", P, Q, R))
})

実行例

P = 63088012960224, Q = 120739, R = 72834276
   ユーザ   システム       経過  
     0.117      0.000      0.126