Wednesday, October 7th, 2009...20:52

Project Euler Problems #6, #7, #8

Jump to Comments

I took a break from projecteuler to whip up a webOS application before my Tahoe Rim Trail Thru-hike. Upon returning I started skiming some technical books and started playing around with the Facebook Puzzles. In general, starting lots of threads is exciting and gives me the feeling that I am learning a lot; however, I believe it’s also important to finish (most) of what one starts. I never got my webOS application to a state where I felt comfortable placing it in the app store, but I did get it to the point where it was usable during my hike. Perhaps I should have continued working on it as there are at least two apps in the store which provide similar functionality. I finished the TRT, and now it’s time to start making more progress with Project Euler.

Problem #6
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum. This didn’t seem like a very interesting problem. I did learn about python’s ** operator which can raise any value to the power of another value. This made it easy to answer the question with a 1 line function:

def p6(r):
 return sum(r)** 2 - sum([x** 2 for x in r])

print p6(range(101))

After reading the forums, as one might expect, there are mathematical formulas for these summations which don’t require iterating through the entire list…

Problem #7
Find the 10001st prime number. I sure any mathematician would balk at this, but my gut feeling is that there’s a prime on average every 10 numbers. So I whipped up a quick version of the Sieve of Eratosthenes and set the limit to 100000. In less than a second on my little Eee PC I had printed the first 9592 primes. It turned out I needed to raise the limit a bit, closer to 105000

import sys
max = int(sys.argv[1])
maxM = max - 2
r = range(2,max)
c = 1
for n in r:
 m = n - 2
 if r[m] != 0:
  print "prime %d is %d" % (c,n)
  c += 1
  m += n
  while m < maxM:
   r[m] = 0
   m += n

Then run it as python 105000. Just for kicks I tried setting the limit to 1000000 and in under 10 seconds found the first 78498 primes (the last one being 999983).

Problem #8
Find the greatest product of five consecutive digits in the 1000-digit number


The first thing I did was copy the number into a file and write some code that would concatonate the numbers into a single string with no line breaks:

line = ""
file = open("problem0008.txt","r")
while True:
 temp = file.readline()
 if not temp:
 line += temp[:-1]

Then even though there's a bunch of unecessary multiplication, I wrote this function that can find the largest product of any n consecutive numbers:

def findLargestProduct(span,line):
 no0 = line.split('0')
 m = 0
 for x in filter((lambda x: len(x) >= span),no0):
  nums = list(x)
  while len(nums) >= span:
   m = max(m,reduce((lambda x, y: int(x) * int(y)),nums[:span]))
   del nums[0]
 return m

I put in one optimization to only work with sub-strings equal to or longer the requested span, in this case 5, that do not contain a zero.

Then this finds the answer: print findLargestProduct(5,line)

Comments are closed.