Method for finding efficient algorithms?

Question

TL;DR

What can you recommend to get better at finding efficient solutions to math problems?

Background

The 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 = 999
sum = 0
for i = 1 to target do
if (i mod 3 = 0) or (i mod 5 = 0) then sum := sum + i
output sum

This does give me the correct result, but it becomes exponentially slower the bigger the target is. So then I saw this solution:

target=999
Function SumDivisibleBy(n)
   p = target div n
   return n * (p * (p + 1)) div 2
EndFunction
Output 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?

Answer 1

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 "what is the sum of the multiples of $3$ below $1000$ ?". Obviously, these are $3,6,9,\cdots999$, i.e. $3\cdot1,3\cdot2,3\cdot3,\cdots3\cdot333$, 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 "harder" 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$.

Answer 2

TL;DR: "Efficient solutions to math problems" don't exist. Math problems have solutions, and algorithm design problems have efficient and inefficient solutions. Recognizing which is which can be half the task.

---

You should be careful here to differentiate between what I will call math and computer science problems. What you see above is a math problem. Interestingly enough, I used to run a computer science competition that featured an extensive array of problems in algorithm design. Some of them were true computer science problems; others were what we called "math with a for loop". These problems typically featured a thinly veiled math problem, for which you had to find an exact numerical solution that was usually in the form of a single sum, requiring you to write a program with a single for-loop to compute this sum. Hence, "math with a for loop."

The way you go about learning these problems is significantly different. For "math with a for loop" problems, study math. Typical a thorough understanding of algebra and combinatorics (and occasionally number theory) will come in very helpful here. But this is not so important for real computer science questions. Algorithm design is hard. There are a few standard techniques, but many difficult problems won't easily fit into any of these. Here the solution is just to learn as much as you can, and to practice.

But your problem above is not a computer science problem. It's a math problem. It can very easily be rewritten into

Let $S$ be the set of all multiples of $3$ or $5$, and let $f(n)$ be the sum of the elements of $S$ below $n$. Compute $f(1000)$.

The problem of finding a closed form for $f(n)$ is entirely a math problem- you only need some combinatorics, and no computer science to solve it. Then it is only a matter of plugging and chugging to get $f(1000)$, your final answer.