James Pine Has A Blog

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)