Problem 142

Problem 142 - Project Euler

x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となるような自然数x > y > z > 0について、最小のx + y + zを求めよ。

x、y、zについてforループを作成しても終わらないので、式を変形する。
まず式を各々次のようにおく。






このとき、問題の条件を考慮すると

であり、a、c、d以外の3つについては



のようにして求められるから、a、c、dについてforループを作成すればよい。
また、x、y、zは次のように求められる。


issquare <- function(x) as.integer(sqrt(x))^2 == x

find.ans <- function(){
  a <- c <- d <- 1
  repeat{
    for(c in 1:a){
      f2 <- a^2 - c^2
      if(f2 < 1 || !issquare(f2)) next
      for(d in 1:c){
        e2 <- a^2 - d^2
        if(e2 < 1 || !issquare(e2)) next
        b2 <- d^2 - f2
        if(b2 > 0 && issquare(b2)){
          x <- (a^2 + b2)/2
          y <- (a^2 - b2)/2
          z <- (c^2 - d^2)/2
          if(x %% 1 == 0 && y %% 1 == 0 && z %% 1 == 0)
            return(x + y + z)
        }
      }
    }
    a <- a + 1
  }
}
find.ans()

6秒。