{"id":741,"date":"2012-02-12T18:57:16","date_gmt":"2012-02-12T18:57:16","guid":{"rendered":"http:\/\/41j.com\/blog\/?p=741"},"modified":"2012-02-12T19:02:07","modified_gmt":"2012-02-12T19:02:07","slug":"euler-problem-1-python-solution","status":"publish","type":"post","link":"https:\/\/41j.com\/blog\/2012\/02\/euler-problem-1-python-solution\/","title":{"rendered":"Euler Problem 1 Python Solution"},"content":{"rendered":"

I wanted to start playing with python a bit more so I thought I’d take a look at the project Euler<\/a> problems. The first problem is to find the sum of all numbers between 1 and 999 that are divisible by 3 or 5.<\/p>\n

After solving it and looking on the forums I was kind of shocked that most solutions used loops, iterating over every number between 1 and 1000. A more efficient solution is to use the sum of an arithmetic progression<\/a>. Which I would have thought is high school Maths (I still needed Wikipedia to prompt me, ho hum). Anyway Here’s my solution:<\/p>\n

\nmax = 999\n\nmaxthree = ((max\/3)*3) + 0.0\nmaxfive = ((max\/5)*5) + 0.0\nmaxfifteen = ((max\/15)*15) + 0.0\n\nmulthree = ((maxthree\/3)\/2)*(3+maxthree)\nmulfive = ((maxfive\/5)\/2)*(5+maxfive)\nmulfifteen = ((maxfifteen\/15)\/2)*(15+maxfifteen)\n\nprint multhree + mulfive - mulfifteen\n<\/pre>\n
I’d guess about 95% of the solutions used loops.
\nThis is my favourite solution from the forum:<\/p>\n
Here is a solution that is reasonably efficient but it works for any list of possible factors, without being overcomplicated (in Java). It took me about 50 minutes to write it.<\/p>\n
\nimport java.io.*;\nimport java.util.*;\nimport java.lang.Math;\n\n\n\npublic class Euler1 {\n\n\n   public static void main(String[] args) {\n\n      \/\/ Eueler project problem 1\n      \/\/ find the sum of all numbers less than N (1000) that are multiples of a given list of factors (3 and 5)\n      \/\/ the program seeks a balance between speed, memory use, generality and program simplicity\n\n      int[] factors = {3,5};\n      int N = 1000;\n\n      int sum = computeSum (factors, N);\n\n      System.err.println(sum);\n\n   }\n\n\n   public static int computeSum (int[] factors, int N) {\n\n      \/\/ efficient calculation using the fact that the pattern of multiples repeats\n      \/\/ use the produce of the factors as the period length, \n      \/\/ the least common multiple would be more efficient but complicates the program\n\n      int M = 1;\n      for(int j=0; j<factors.length; j++) {\n         int f = factors[j];\n         M *= f;\n      }\n\n      int k = (N-1)\/M;    \/\/ number of repeated periods\n      int r = (N-1)%M+1;  \/\/ remaining length;\n\n      \/\/ use average of sum over first and last period time k, plus sum over the remaining numbers \n\n      int sum = (bruteSum(factors, 1, M+1)+bruteSum(factors,(k-1)*M+1,k*M+1))*k\/2 + bruteSum(factors, k*M+1, N);\n\n      return sum;\n   }\n\n   public static int bruteSum(int[] factors, int N0, int N1) {\n\n      \/\/ computes the answer using a straightforward but inefficient brute force method \n\n      int sum = 0;\n      \n      for(int i=N0; i<N1; i++) {\n         boolean isAMultiple = false;\n         for(int j=0; j<factors.length; j++) {\n            int f = factors[j];\n            if(i%f == 0) isAMultiple = true;\n         }\n\n         if(isAMultiple) {\n            sum += i;\n         }\n\n      }\n\n      return sum;\n         \n   }\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
I wanted to start playing with python a bit more so I thought I’d take a look at the project Euler problems. The first problem is to find the sum of all numbers between 1 and 999 that are divisible by 3 or 5. After solving it and looking on the forums I was kind […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-741","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-bX","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/741","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=741"}],"version-history":[{"count":4,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/741\/revisions"}],"predecessor-version":[{"id":745,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/741\/revisions\/745"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=741"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=741"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=741"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}