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

## Project Euler Problems #6, #7, #8

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 10001^{st} 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 problem0007.py 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

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

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: break line += temp[:-1] file.close()

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.