Problem 243

分子が分母より小さい分数を真分数と呼ぶ。
どのような分母dを選んでも、d-1個の真分数がある。例えばd = 12とすると、
1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12
分数のうち、約分できないものをresilient(弾性のある)分数と呼ぶことにする。
さらに、分母dについて、真分数の中でresilient分数の割合をresilient(弾性)と呼ぶことにし、R(d)で表す。例えば、
R(12) = 4/11
なお、d = 12はR(d) < 4/10を満たす最小の分母である。
R(d) < 15499/94744を満たす最小のdを見つけよ。
Problem 243 - Project Euler

オイラーのφ関数をφ(n)とすると、R(n) = φ(n)/(n-1)である。
なので、φ(n)を列挙してから計算しても答えは出るが、時間がかかる。
φ(n)はnが素数だと大きな値となるので、因子を多く持つ必要がある。
φ(n)/nについて少し考えると、nの冪に対して値が変わらないことが分かる。なので、φ(n)/(n-1)はnの冪を順に入れていくと、φ(n)/nに近づくもののそれ以上は小さくならない。よって、複数の素因数が必要ということが分かる。
条件を満たすまで素因数を増やしたら、そこから一つ素因数を削って探索を開始する。

library(gmp)
euler.phi <- function(n){
  p <- unique(as.numeric(factorize(n)))
  n * prod((p - 1)/p)
}
R <- function(n){
  euler.phi(n)/(n-1)
}
## euler.phi(n)/nの値は、nの冪に対して一定である
## R(n^i)は、iを大きくするとeuler.phi(n)/nに近づく
## R(n)を小さくするには、素因数を増やすしか無い。
## 素数リスト
limit <- 100
plist <- 1:limit
sieve <- logical(limit)
sieve[1] <- TRUE
sieve[seq(4, limit, 2)] <- TRUE
for(i in seq(3, sqrt(limit), 2)){
  sieve[seq(i * 2, limit, i)] <- TRUE
}
plist <- (1:limit)[!sieve]
## 条件を満たすまで素因数を増やし続ける
for(i in 1:length(plist)){
  if(R(prod(plist[1:i])) < 15499/94744) break
}
## prod(p_(i-1))から、prod(p_i)までの間に解がある
num <- prod(plist[1:(i-1)])
for(j in 2:plist[i]){
  if(R(num * j) < 15499/94744){
    print(num * j)
    break
  }
}