Problem 134

Problem 134 - Project Euler

連続する2つの素数p1 = 19とp2 = 23を考える。1219は、末尾の桁にp1を含み、かつp2で割り切れるような最小の数である。
実際のところ、p1 = 3, p2 = 5の場合をのぞく全ての連続する素数p2 > p1についてこのような数nが存在する。nのうち最小のものをSとする。
5 ≦ p1 ≦ 1000000であるようなp1の全てについてSを求め、Sの総和を答えよ。

全然分からなかったのでググッたら

などで拡張ユークリッドの互除法を使うとかなんとか言われてたけど拡張ユークリッドの互除法自体がさっぱり分からなかったので調べて一つ前のエントリにまとめときました(ユークリッドの互除法とその拡張 - もうカツ丼でいいよな)。
さて、問題は素数p1, p2について
   (ただし )
を満たすxを求められれば解決する。
p2と10^dに対して拡張ユークリッドの互除法を適用すると、p2と10^dは互いに素であるから

となる整数a, bが求められる(p2が2, 5の場合は最大公約数が1とならないが、問題の範囲からは除外されているので考えない)。この式から

であることも分かる。ここで最初の式にaをかけると、

上式より

従って

library(gmp)

limit <- 1e6 * 2
sieve <- logical(limit)
sieve[c(1, seq(4, limit, by=2))] <- TRUE
for(i in seq(3, sqrt(limit), by=2)){
  if(!sieve[i]) sieve[seq(i * 2, limit, by = i)] <- TRUE
}
p.list <- (1:limit)[!sieve]

euclid <- function(m, n){
  a <- 0; aa <- 1; C <- m               # E1.
  b <- 1; bb <- 0; d <- n
  repeat{
    q <- C %/% d; r <- C %% d           # E2.
    if(r == 0) return(c(a = a, b = b, d = d)) # E3.
    C <- d; d <- r                      # E4.
    t <- aa; aa <- a; a <- t - q * a
    t <- bb; bb <- b; b <- t - q * b
  }
}

find.S <- function(p1, p2){
  d <- floor(log(p1, 10))+1
  ((euclid(p2, 10^d)["a"] * p1) %% 10^d) * p2
}

ans <- as.bigz(0)
for(i in 3:(length(p.list[p.list < 1e6]))){
  ans <- ans + find.S(p.list[i], p.list[i+1])
}
ans

12.7秒。