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;
          
   }
}

Leave a Reply