分子が分母より小さい分数を真分数と呼ぶ。
どのような分母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 } }