Project Euler: Issue 1 (Possible refactoring and run-time optimization)

Question

I heard a lot about Project Euler, so I decided to solve one of the problems in C #. The problem stated on the website is this:

If we list all natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all multiples of 3 or 5 below 1000.

I wrote my code as follows:

class EulerProblem1 { public static void Main() { var totalNum = 1000; var counter = 1; var sum = 0; while (counter < totalNum) { if (DivisibleByThreeOrFive(counter)) sum += counter; counter++; } Console.WriteLine("Total Sum: {0}", sum); Console.ReadKey(); } private static bool DivisibleByThreeOrFive(int counter) { return ((counter % 3 == 0) || (counter % 5 == 0)); } } 

It would be great to get some ideas on alternative implementations with less literature / brushing syntax and better optimization. Ideas can range from fast and dirty to making guns to destroy a mosquito. The goal is to explore the depths of computer science, trying to improve this particularly trivial piece of code.

thanks

Answer 1

With LINQ (updated as noted in the comments)

 static void Main(string[] args) { var total = Enumerable.Range(0,1000) .Where(counter => (counter%3 == 0) || (counter%5 == 0)) .Sum(); Console.WriteLine(total); Console.ReadKey(); } 

Answer 2

Updated to not double the number of counters that are multiples of both 3 and 5:

 int EulerProblem(int totalNum) { int a = (totalNum-1)/3; int b = (totalNum-1)/5; int c = (totalNum-1)/15; int d = a*(a+1)/2; int e = b*(b+1)/2; int f = c*(c+1)/2; return 3*d + 5*e - 15*f; } 

Answer 3

Here's the transliteration of my original F # solution in C #. Edited: This is basically an mbeckish solution as a loop, not a function (and I delete the double count). I like mbeckish better.

 static int Euler1 () { int sum = 0; for (int i=3; i<1000; i+=3) sum+=i; for (int i=5; i<1000; i+=5) sum+=i; for (int i=15; i<1000; i+=15) sum-=i; return sum; } 

Here is the original:

 let euler1 d0 d1 n = (seq {d0..d0..n} |> Seq.sum) + (seq {d1..d1..n} |> Seq.sum) - (seq {d0*d1..d0*d1..n} |> Seq.sum) let result = euler1 3 5 (1000-1) 

Answer 4

I did not write any Java after a while, but this was supposed to solve it in a constant time with little overhead:

 public class EulerProblem1 { private static final int EULER1 = 233168; // Equal to the sum of all natural numbers less than 1000 // which are multiples of 3 or 5, inclusive. public static void main(String[] args) { System.out.println(EULER1); } } 

EDIT: here's an implementation of C if each command considers:

 #define STDOUT 1 #define OUT_LENGTH 8 int main (int argc, char **argv) { const char out[OUT_LENGTH] = "233168\n"; write(STDOUT, out, OUT_LENGTH); } 

Notes:

• There is no error handling when calling write . If true reliability is required, a more sophisticated error handling strategy must be used. Whether the additional complexity is more reliable depends on the needs of the user.
• If you have memory limitations, you can save the byte using a direct char array, rather than a string terminated by an excess null character. In practice, however, out almost certainly be padded to 8 bytes.
• Although declaring an out variable could be avoided by placing the inline string in a write call, any real compiler will remove the declaration.
• The write script is used in the puts preference or the like to avoid additional overhead. Theoretically, you can call a system call directly, possibly saving a few cycles, but this will cause serious portability problems. Your mileage may vary depending on whether this is an acceptable compromise.

Answer 5

@Mbeckish refactoring is a very smart solution:

 public int eulerProblem(int max) { int t1 = f(max, 3); int t2 = f(max, 5); int t3 = f(max, 3 * 5); return t1 + t2 - t3; } private int f(int max, int n) { int a = (max - 1) / n; return n * a * (a + 1) / 2; } 

Answer 6

This is basically the same as I made this problem. I know that there are other solutions (possibly more effective) in the forums for project-euler.

Once you enter your answer, back to the question, you will get the opportunity to go to the forum for this problem. You can look there!

Answer 7

The code in DivisibleByThreeOrFive will be slightly faster if you specify it like this:

 return ((counter % 3 == 0) || (counter % 5 == 0)); 

And if you don't want to rely on the compiler to inline a function call, you can do it yourself by putting this code in the main procedure.

Answer 8

You can find a closed form solution for this. The trick is to look for patterns. Try to specify conditions in the amount of up to ten or twenty, and then use algebra to group them. By making appropriate replacements, you can generalize this to numbers other than ten. Just be careful with edge cases.

Answer 9

Try this, in C. This is a constant time, and there is only one separation (two if the compiler does not optimize the div / mod that it should). I'm sure this can make it more obvious, but it should work.

It basically divides the amount into two parts. Most (for N> = 15) is a simple quadratic function that divides N into exact blocks of 15. The smaller part is the last bit that does not fit into the block. The last bit is messy, but there are only a few possibilities, so the LUT will solve it in no time.

 const unsigned long N = 1000 - 1; const unsigned long q = N / 15; const unsigned long r = N % 15; const unsigned long rc = N - r; unsigned long sum = ((q * 105 + 15) * q) >> 1; switch (r) { case 3 : sum += 3 + 1*rc ; break; case 4 : sum += 3 + 1*rc ; break; case 5 : sum += 8 + 2*rc ; break; case 6 : sum += 14 + 3*rc ; break; case 7 : sum += 14 + 3*rc ; break; case 8 : sum += 14 + 3*rc ; break; case 9 : sum += 23 + 4*rc ; break; case 10 : sum += 33 + 5*rc ; break; case 11 : sum += 33 + 5*rc ; break; case 12 : sum += 45 + 6*rc ; break; case 13 : sum += 45 + 6*rc ; break; case 14 : sum += 45 + 6*rc ; break; } 

Answer 10

You can do something like this:

 Func<int,int> Euler = total=> new List<int>() {3,5} .Select(m => ((int) (total-1) / m) * m * (((int) (total-1) / m) + 1) / 2) .Aggregate( (T, m) => T+=m); 

You still have a double counter problem. I will think about it a little more.

Edit:

Here's a working (if a little inelegant) solution in LINQ:

  var li = new List<int>() { 3, 5 }; Func<int, int, int> Summation = (total, m) => ((int) (total-1) / m) * m * (((int) (total-1) / m) + 1) / 2; Func<int,int> Euler = total=> li .Select(m => Summation(total, m)) .Aggregate((T, m) => T+=m) - Summation(total, li.Aggregate((T, m) => T*=m)); 

Can any of you improve this?

Explanation:

Remember that the summation formula for linear progression is n (n + 1) / 2. In the first case, when you have a multiple of 3.5 <10, you want Sum (3 + 6 + 9.5). Setting total = 10, you make a sequence of integers 1 .. (int) (total-1) / 3, and then sum the sequence and multiply by 3. You can easily see that we just set n = (int) (total- 1) / 3, then using the summation formula and multiplying by 3. A small algebra gives us a formula for the summation functor.

Answer 11

I like the idea of ​​technielogys, here is my modification idea

 static int Euler1 () { int sum = 0; for (int i=3; i<1000; i+=3) { if (i % 5 == 0) continue; sum+=i; } for (int i=5; i<1000; i+=5) sum+=i; return sum; } 

Although it also comes to mind, maybe a minor heuristic, does it make any improvements?

 static int Euler1 () { int sum = 0; for (int i=3; i<1000; i+=3) { if (i % 5 == 0) continue; sum+=i; } for (int i=5; i<250; i+=5) { sum+=i; } for (int i=250; i<500; i+=5) { sum+=i; sum+=i*2; sum+=(i*2)+5; } return sum; } 

Answer 12

 Your approach is brute force apprach, The time complexity of the following approach is O(1), Here we are dividing the given (number-1) by 3, 5 and 15, and store in countNumOf3,countNumOf5, countNumOf15. Now we can say that 3 will make AP, within the range of given (number-1) with difference of 3. suppose you are given number is 16, then 3=> 3, 6, 9, 12, 15= sum1=>45 5=> 5, 10, 15 sum2=> 30 15=> 15 => sum3=15 Add sum= sum1 and sum2 Here 15 is multiple of 3 and 5 so remove sum3 form sum, this will be your answer. **sum=sum- sum3** please check link of my solution on http://ideone.com/beXsam] import java.util.*; class Multiplesof3And5 { public static void main(String [] args){ Scanner scan=new Scanner(System.in); int num=scan.nextInt(); System.out.println(getSum(num)); } public static long getSum(int n){ int countNumOf3=(n-1)/3;// int countNumOf5=(n-1)/5; int countNumOf15=(n-1)/15; long sum=0; sum=sumOfAP(3,countNumOf3,3)+sumOfAP(5,countNumOf5,5)-sumOfAP(15,countNumOf15,15); return sum; } public static int sumOfAP(int a, int n, int d){ return (n*(2*a +(n -1)*d))/2; } } 

Answer 13

 new List<int>{3,5}.SelectMany(n =>Enumerable.Range(1,999/n).Select(i=>i*n)) .Distinct() .Sum() 

[Refresh] (In response to a comment requiring an explanation of this algorithm) This creates a flattened list of multiple values ​​for each base value (3 and 5 in this case), and then removes duplicates (for example, if the multiple is divisible, in this case by 3 * 5 = 15), and then summarizes the remaining values. (It is also easy to generalize in order to have more than two basic IMHO values ​​compared to any of the other solutions I saw here.)