Project Euler 9: Special Pythagorean Triplet

A Pythagorean triplet is a set of three natural numbers, \(a < b < c\), for which, \(a^2 + b^2 = c^2\).

For example, \(3^2 + 4^2 = 9 + 16 = 25 = 5^2\).

There exists exactly one Pythagorean triplet for which \(a + b + c = 1000\).

Find the product \(abc\).

This solution uses brute force and checks all combinations of \(a\), \(b\) and \(c\). To limit the solution space, I used the fact that \(a < b < c\), which implies that \(a < s/3\), and \(a < b < s/2\), where s is the sum of the three sides.

ProjectEuler

  ## Project Euler 9: Special Pythagorean Triplet
  a <- 0
  b <- 0
  c <- 0
  s <- 1000
  found <- FALSE
  for (a in 1:floor((s / 3))) {
      for (b in (a + 1):floor(s / 2)) {
          c <- s - a - b
          if (a^2 + b^2 == c^2) {
              found <- TRUE
              break
          }
      }
      if (found) break
  }
  answer <- a * b * c
  print(answer)

Alan Jordan provided a faster brute force method. Since \(min(a)=1\) and \(max(b)=499\), we can walk \(a\) and \(b\) towards each other. That way there’s a max of 498 possibilities instead of 292*497 in the first solution.

  # Improved Brute Force
  a <- 1
  b <- 499
  repeat{
      c <- sqrt(a^2 + b^2) 
      if (a + b + c > 1000) {b <- b - 1}
      else if (a + b + c < 1000) {a <- a + 1}
      else if (a + b + c == 1000) {break}
  }
  answer <- a * b * c
  print(answer)

Euclid’s formula generates Pythagorean triples for an arbitrary pair of integers m and n with \(m > n > 0\). The formula states that the integers \(a = m^2 - n^2, b = 2mn, c = m^2 = n^2\) form a Pythagorean triple.

  ## Euclid's Method
  abc_sum <- 1000
  x <- abc_sum / 2
  min <- floor(sqrt(x / 2))
  max <- ceiling(sqrt(x))
  m <- min:max
  m <- m[x %% m == 0]
  n <- ((x / m) - m)
  a <- 2 * m * n
  b <- m^2 - n^2
  c <- m^2 + n^2
  answer <- a * b * c
  print(answer)