Euler Problem 1 Python Solution
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 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. Which I would have thought is high school Maths (I still needed Wikipedia to prompt me, ho hum). Anyway Here’s my solution:
1 2 3 4 5 6 7 8 9 10 11 | max = 999 maxthree = (( max / 3 ) * 3 ) + 0.0 maxfive = (( max / 5 ) * 5 ) + 0.0 maxfifteen = (( max / 15 ) * 15 ) + 0.0 multhree = ((maxthree / 3 ) / 2 ) * ( 3 + maxthree) mulfive = ((maxfive / 5 ) / 2 ) * ( 5 + maxfive) mulfifteen = ((maxfifteen / 15 ) / 2 ) * ( 15 + maxfifteen) print multhree + mulfive - mulfifteen |
I’d guess about 95% of the solutions used loops.
This is my favourite solution from the forum:
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | import java.io.*; import java.util.*; import java.lang.Math; public class Euler1 { public static void main(String[] args) { // Eueler project problem 1 // find the sum of all numbers less than N (1000) that are multiples of a given list of factors (3 and 5) // the program seeks a balance between speed, memory use, generality and program simplicity int [] factors = { 3 , 5 }; int N = 1000 ; int sum = computeSum (factors, N); System.err.println(sum); } public static int computeSum ( int [] factors, int N) { // efficient calculation using the fact that the pattern of multiples repeats // use the produce of the factors as the period length, // the least common multiple would be more efficient but complicates the program int M = 1 ; for ( int j= 0 ; j<factors.length; j++) { int f = factors[j]; M *= f; } int k = (N- 1 )/M; // number of repeated periods int r = (N- 1 )%M+ 1 ; // remaining length; // use average of sum over first and last period time k, plus sum over the remaining numbers int sum = (bruteSum(factors, 1 , M+ 1 )+bruteSum(factors,(k- 1 )*M+ 1 ,k*M+ 1 ))*k/ 2 + bruteSum(factors, k*M+ 1 , N); return sum; } public static int bruteSum( int [] factors, int N0, int N1) { // computes the answer using a straightforward but inefficient brute force method int sum = 0 ; for ( int i=N0; i<N1; i++) { boolean isAMultiple = false ; for ( int j= 0 ; j<factors.length; j++) { int f = factors[j]; if (i%f == 0 ) isAMultiple = true ; } if (isAMultiple) { sum += i; } } return sum; } } |