Skip to content

Instantly share code, notes, and snippets.

@syntacticsugar
Forked from pjc/euler9.rb
Created March 11, 2013 03:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save syntacticsugar/5131760 to your computer and use it in GitHub Desktop.
Save syntacticsugar/5131760 to your computer and use it in GitHub Desktop.
# Euclid's formula yields Pythagorean triples for integers m and n with m < n:
# a = m**2 - n**2 ; b = 2*m*n ; c = m**2 + n**2
x = 1000
def euclids upto
result = []
(2..upto).each do |m| # Start at 2 as 1 results nothing anyway
(1...m).each do |n| # Euclid's formula only works for m > n
result << [m**2 - n**2, 2*m*n, m**2 + n**2]
end
end
result
end
# Calling Euclids on n/2 suffices as m + n < x
euclids(x/2).each do |triple|
a, b, c = triple[0], triple[1], triple[2]
if a + b + c == x
puts a * b * c
break
end
end
@darius
Copy link

darius commented Mar 20, 2013

Very nice! I streamlined it a little:

# Euclid's formula yields Pythagorean triples for integers m and n with m < n:
# a = m**2 - n**2 ; b = 2*m*n ; c = m**2 + n**2

x = 1000

def euclids upto
  (2..upto).each do |m| # Start at 2 as 1 results nothing anyway
    (1...m).each do |n| # Euclid's formula only works for m > n
      yield m**2 - n**2, 2*m*n, m**2 + n**2
    end
  end
end

# Calling Euclids on n/2 suffices as m + n < x
euclids(x/2) do |a, b, c|
  if a + b + c == x
    puts a * b * c
    break
  end
end

@syntacticsugar
Copy link
Author

:D

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment