Problem 70

Problem 70 - Project Euler
ううむ。2分かかる。
n/\varphi(n)を最小化という条件から、

  • 素因数は少ない
  • 素因数は大きい

また、nが素数のとき\varphi(n)=n-1なので

  • nは2つ以上の素因数を持つ

ことが分かる。
なので探索は2つの素数の積、かつ素数\sqrt{10^7}よりいくらか大きいもの以下に限った。

といっても2千万通りくらい調べるので時間がかかる…うーん。\sqrt{10^7}\pm1000くらいを探索したらいいんだろうっていうのは想像できるけど根拠がなにもないし。

limit <- sqrt(10^7)*2
sievebound <- (limit-1)/2
sieve <- logical(sievebound)
crosslimit <- (floor(sqrt(limit))-1)/2
for(i in 1:crosslimit){
  if(!sieve[i]){
    for(j in seq(2*i*(i+1), sievebound, 2*i+1)){
      sieve[j] <- TRUE
    }
  }
}
p.lis <- c(2, 2*(1:sievebound)[!sieve]+1)

euler.phi <- function(n, m){
  n*m*(1-1/n)*(1-1/m)
}

toNum.r <- function(n){
  sum(n*10^(0:(length(n)-1)))
}
options(scipen=3)
toDig.sort <- function(n){
  toNum.r(as.numeric(sort((strsplit(as.character(n),"")[[1]]))))
}

ans <- 0
n.div.phi <- 10^7
for(i in p.lis){
  for(j in p.lis[p.lis < i]){
    e.phi <- euler.phi(i,j)
    cand <- i*j
    if(cand > 10^7) next
    if(toDig.sort(e.phi)==toDig.sort(cand)){
      dphi.cand <- cand/e.phi
      if(n.div.phi > dphi.cand){
        ans <- cand
        n.div.phi <- dphi.cand
        n <- i
        m <- j
      }
    }
  }
}