{"id":169,"date":"2009-10-07T20:52:41","date_gmt":"2009-10-08T04:52:41","guid":{"rendered":"http:\/\/www.madpickles.org\/rokjoo\/?p=169"},"modified":"2010-02-18T13:26:31","modified_gmt":"2010-02-18T21:26:31","slug":"project-euler-problems-6-7-8","status":"publish","type":"post","link":"https:\/\/www.madpickles.org\/rokjoo\/2009\/10\/07\/project-euler-problems-6-7-8\/","title":{"rendered":"Project Euler Problems #6, #7, #8"},"content":{"rendered":"

I took a break from projecteuler<\/a> to whip up a webOS application<\/a> before my Tahoe Rim Trail Thru-hike<\/a>. Upon returning I started skiming some technical books and started playing around with the Facebook Puzzles<\/a>. 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.<\/p>\n

Problem #6
\nFind 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:<\/p>\n

\r\ndef p6(r):\r\n return sum(r)** 2 - sum([x** 2 for x in r])\r\n\r\nprint p6(range(101))\r\n<\/pre>\n
After reading the forums, as one might expect, there are mathematical formulas for these summations which don’t require iterating through the entire list…<\/p>\n
Problem #7
\nFind the 10001st<\/sup> 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<\/p>\n
\r\nimport sys\r\nmax = int(sys.argv[1])\r\nmaxM = max - 2\r\nr = range(2,max)\r\nc = 1\r\nfor n in r:\r\n m = n - 2\r\n if r[m] != 0:\r\n  print \"prime %d is %d\" % (c,n)\r\n  c += 1\r\n  m += n\r\n  while m < maxM:\r\n   r[m] = 0\r\n   m += n\r\n<\/pre>\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).<\/p>\n
Problem #8
\nFind the greatest product of five consecutive digits in the 1000-digit number<\/p>\n
73167176531330624919225119674426574742355349194934
\n96983520312774506326239578318016984801869478851843
\n85861560789112949495459501737958331952853208805511
\n12540698747158523863050715693290963295227443043557
\n66896648950445244523161731856403098711121722383113
\n62229893423380308135336276614282806444486645238749
\n30358907296290491560440772390713810515859307960866
\n70172427121883998797908792274921901699720888093776
\n65727333001053367881220235421809751254540594752243
\n52584907711670556013604839586446706324415722155397
\n53697817977846174064955149290862569321978468622482
\n83972241375657056057490261407972968652414535100474
\n82166370484403199890008895243450658541227588666881
\n16427171479924442928230863465674813919123162824586
\n17866458359124566529476545682848912883142607690042
\n24219022671055626321111109370544217506941658960408
\n07198403850962455444362981230987879927244284909188
\n84580156166097919133875499200524063689912560717606
\n05886116467109405077541002256983155200055935729725
\n71636269561882670428252483600823257530420752963450<\/p>\n
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:<\/p>\n
\r\nline = \"\"\r\nfile = open(\"problem0008.txt\",\"r\")\r\nwhile True:\r\n temp = file.readline()\r\n if not temp:\r\n  break\r\n line += temp[:-1]\r\nfile.close()\r\n<\/pre>\n
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:<\/p>\n
\r\ndef findLargestProduct(span,line):\r\n no0 = line.split('0')\r\n m = 0\r\n for x in filter((lambda x: len(x) >= span),no0):\r\n  nums = list(x)\r\n  while len(nums) >= span:\r\n   m = max(m,reduce((lambda x, y: int(x) * int(y)),nums[:span]))\r\n   del nums[0]\r\n return m\r\n<\/pre>\n
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.<\/p>\n
Then this finds the answer: print findLargestProduct(5,line)<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[18,11,19,17],"_links":{"self":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/169"}],"collection":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/comments?post=169"}],"version-history":[{"count":4,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/169\/revisions"}],"predecessor-version":[{"id":220,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/169\/revisions\/220"}],"wp:attachment":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/media?parent=169"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/categories?post=169"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/tags?post=169"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}