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