Method for finding efficient algorithms?TL;DRWhat can you recommend to get better at finding efficient solutions to math problems?BackgroundThe first challenge on Project Euler says:Find the sum of all the multiples of 3 or 5 below 1000.The first, and only solution that I could think of was the brute force way:target = 999sum = 0for i = 1 to target doif (i mod 3 = 0) or (i mod 5 = 0) then sum := sum + ioutput sumThis does give me the correct result, but it becomes exponentially slower the bigger the target is. So then I saw this solution:target=999Function SumDivisibleBy(n) p = target div n return n * (p * (p + 1)) div 2EndFunctionOutput SumDivisibleBy(3) + SumDivisibleBy(5) - SumDivisibleBy(15)I don't have trouble understanding how this math works, and upon seeing it I feel as though I could have realised that myself. The problem is just that I never do. I always end up with some exponential, brute force like solution.Obviously there is a huge difference between understanding a presented solution, and actually realising that solution yourself. And I'm not asking how to be Euler himself.What I do ask tho is, are there methods and or steps, you can apply to solve math problems to find the best (or at least a good) solution?If yes, can you guys recommend any books/videos/lectures that teach these methods? And what do you do yourself when attempting to find such solutions?

Question

Method for finding efficient algorithms?TL;DRWhat can you recommend to get better at finding efficient solutions to math problems?BackgroundThe first challenge on Project Euler says:Find the sum of all the multiples of 3 or 5 below 1000.The first, and only solution that I could think of was the brute force way:target = 999sum = 0for i = 1 to target doif (i mod 3 = 0) or (i mod 5 = 0) then sum := sum + ioutput sumThis does give me the correct result, but it becomes exponentially slower the bigger the target is. So then I saw this solution:target=999Function SumDivisibleBy(n)   p = target div n   return n * (p * (p + 1)) div 2EndFunctionOutput SumDivisibleBy(3) + SumDivisibleBy(5) - SumDivisibleBy(15)I don&#039;t have trouble understanding how this math works, and upon seeing it I feel as though I could have realised that myself. The problem is just that I never do. I always end up with some exponential, brute force like solution.Obviously there is a huge difference between understanding a presented solution, and actually realising that solution yourself. And I&#039;m not asking how to be Euler himself.What I do ask tho is, are there methods and or steps, you can apply to solve math problems to find the best (or at least a good) solution?If yes, can you guys recommend any books/videos/lectures that teach these methods? And what do you do yourself when attempting to find such solutions?

Jaylin Wheeler · Accepted Answer

There is no general method to find efficient algorithms, as there is no method to solve math problems in general. Besides practice and culture.In the problem at hand, you might first simplify and ask yourself &quot;what is the sum of the multiples of 3 below 1000 ?&quot;. Obviously, these are   3  ,  6  ,  9  ,  ⋯  999 i.e.   3  ⋅  1  ,  3  ⋅  2  ,  3  ⋅  3  ,  ⋯  3  ⋅  333 and the sum is thrice the sum of integers from 1 to 1000/3, for which a formula is known (triangular numbers). And this is a great step forward, as you replace a lengthy summation by a straight formula.Now if you switch to the &quot;harder&quot; case of multiples of 3 or 5, you can repeat the above reasoning for the multiples of 5. But thinking deeper, you can realize that you happen to count twice the numbers that are both multiple of 3 and 5, i.e the multiples of 15. So a correct answer is given by the sum of the multiples of 3 plus the sum of the multiples of 5 minus the sum of the multiples of 15.

Answered question

Answer & Explanation

New Questions in High school statistics