Archive | September, 2011

Problem Ten

8 Sep

Here’s problem ten:

Question: Find the sum of all the primes below two million.

This problem was fairly easy, at least when implementing my inelegant brute force solution. Ninety percent of the work was already done, in the form of a prime testing function that I created for problem seven. I just copied and pasted the function, and wrote a short while loop to find the solution.

Here’s the code:

def isPrime(x): 
	
	divisor = 3 
	limit = int(x**0.5) + 1

	while divisor < limit:
		if x % divisor == 0:
			return False
		else:
			divisor += 2 

	return True

i = 3
sum = 0

while i < 2000000:
	if isPrime(i):
		sum += i
	i += 2 # add two to skip evens

print(sum+2)

I’m not going to explain the isPrime() function again; if you’re curious about how it works, you can read my post about question seven. We initialize i to 3 and set sum to 0. While the current value of i is less than 2,000,000, we test to see if it’s prime. If true, we add it to sum. After prime testing we add two to i, which allows us to skip the even numbers. Finally we print sum, but since we skipped the prime number 2, we add it to sum before printing.

This was relatively inefficient, and took around 16 seconds to run. There’s an algorithm called the sieve of Eratosthenes, which finds primes remarkably fast. However, school just started, so in the interest of time (for doing homework D:), I didn’t research this method much. But if the ancient Greeks could come up with this method, how complicated could it be? Google it if you’re curious and see what you can come up with.

Answer: 142913828922

Problem Nine

3 Sep

On to problem nine:

Question: There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

There’s two ways that I could potentially solve this problem. One is to use brute force and test a lot of combinations of numbers to find the solution. Another is to somehow generate a stream of pythagorean triples and test only those, which would likely be faster. However, I could not find a reliable method to do this, so in the end I used brute force.

Here’s my solution:

for a in range(1, 1000): 
	for b in range(1, 1000):
		c = 1000 - a - b 
		if a**2 + b**2 == c**2:
			print(a,b,c, a*b*c) 

It’s five lines and runs in 3.5 seconds, not bad for brute force. We test all a‘s and b‘s in the arbitrary range of 1-1000, and set c equal to 1000 – a – b , since it’s given in the problem that a + b + c = 1000. For each set of a, b, and c‘s, we check to see if it’s a pythagorean triplet by plugging it into the pythagorean theorem. If the numbers all work, we print them and their product.

As for formulas to generate pythagorean triples, I found three of them (that I could understand) from a couple of google searches. I’ll summarize them here.

The first I found was a strange little formula with several names and definitions. This was actually derived from the second formula I found, but the two are distinct enough to treat separately. To the best of my knowledge, Pythagoras came up with this formula first, which is a = m , b =((m2 – 1)/2), c = ((m2 + 1)/2). Wikipedia has a version of this formula where (since a = m)  a is substituted into the last two equations. There is also a version where all of these are raised to the power of two (I’m pretty sure the former is more accurate, since it is referenced in both Wikipedia and MathWorld).

However, this formula has limitations, mainly that m has to be odd. So Plato came up with another formula (this is where it gets tricky, there’s actually differing accounts of what this formula is). Wikipedia states that Plato created a formula for only even integers, which was a = m , b = (m/2)2 – 1, c = (m/2)2 + 1. Wikipedia actually substitutes a for m, but I’ll stick with m for the sake of consistency. Another website states that Plato actually came up with a formula for all natural numbers, not just even ones. It’s: a = (2m)2, b = (m2 – 1)2, c = (m2 + 1)2 (slightly modified for consistency). MathWorld also has a formula very similar to this: a = 2m, b = (m2 – 1), c = (m2 + 1). However, this version, as you can see, does not contain the outer exponents and is also not accredited to Plato; instead they claim that it was made by Pythagoras and the Babylonians! There are some serious contradictions here.

I decided not to use these first couple of formulas since they were very inconsistent, and, even overlooking this fact, they do not generate all pythagorean triples. Quick note here: a primitive pythagorean triple is one where its greatest common divisor is one. It is only necessary to find all primitive pythagorean triples, since the rest can be found by multiplying them by any integer.

The second formula I found could actually generate all primitive pythagorean triples. It’s called Euclid’s formula and was stated as: a = v2 – u2, b = 2vu, c = v2 + u2. However, this is only true if v and u are of opposite parity and coprime (i.e. gcf is one). Since it generates all primitive pythagorean triples, we can find all non-primitive triples by multiplying by an arbitrary integer k. However, the constraints for v and u make this impractical to write out in code, so I decided not to use this formula either.

The third formula I found was utilized a sequence of Fibonacci numbers. However, the very fact that it uses Fibonacci numbers makes it impractical to code, and furthermore it does not generate all primitive pythagorean triples. Therefore I couldn’t use the third formula either.

So in the end, I still had to revert to using brute force.

If you’re curious, here are my sources:
http://mathworld.wolfram.com/PythagoreanTriple.html
http://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples
http://jwilson.coe.uga.edu/EMT668/EMT668.Folders.F97/Edenfield/Pythtriples/Pythriples.html

Answer: 31875000 (200*375*425)