6
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ You might benefit from George Polya's classic book, How to Solve It. $\endgroup$ – Barry Cipra Oct 31 '18 at 13:54
  • 3
    $\begingroup$ Your solution is not exponentially slower as the target gets bigger. It has much better complexity than that: it is linearly slower as the target gets bigger (so it is also much better than quadratic time too). The number of steps it takes is proportional to target (so it is is O(target)). Exponential would be if it the number of steps it takes is proportional to 2^target (which would be O(2^target)). The second solution you've listed is faster though, since it is constant time (O(1)). $\endgroup$ – David Oct 31 '18 at 16:20
  • 2
    $\begingroup$ Try going through project Euler without the aid of a computer. This forces you to come up with less computation-heavy approaches. Of course, having seen a lot of tricks (e.g. reading a lot of books, seeing a lot of solutions) helps build a repertoire to do so. Disclaimer: You might want to skip a few problems here and there. $\endgroup$ – Servaes Oct 31 '18 at 17:11
6
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ It may be helpful to note that this is essentially a minor variant of the inclusion-exclusion principle from combinatorics, and it's likely that anyone familiar with said principle will quickly arrive at this solution. $\endgroup$ – AlexanderJ93 Oct 31 '18 at 16:53
  • $\begingroup$ There are some interesting ways in which your opening sentence is false: see Levin's universal search and Hutter's variant of it, described e.g. at scholarpedia.org/article/Universal_search $\endgroup$ – Robin Saunders Oct 31 '18 at 18:10
  • $\begingroup$ @RobinSaunders: this is by no means a general method, it is specific to this inversion problem. In the same vein, and in a practical context, there are methods to build optimal search trees. But again, these methods are quite ad-hoc. $\endgroup$ – Yves Daoust Oct 31 '18 at 18:14
  • $\begingroup$ Well, but a great many problems can be formulated as inversion problems: for example, the domain could be the set of all valid chains of deduction (in some formal system) and the function assigns to each chain of deduction its concluding statement. Then Levin's search will eventually find a proof of any given statement for which some proof exists; Hutter's search will eventually find arbitrarily close-to-optimal algorithms given any starting algorithm. The catch is the word "eventually". $\endgroup$ – Robin Saunders Oct 31 '18 at 18:23
  • 1
    $\begingroup$ @RobinSaunders: you should enter this as an answer. $\endgroup$ – Yves Daoust Oct 31 '18 at 18:33
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Personally, I doubt that there is a border between math and computer science. Computer science can be seen as a branch of discrete mathematics, with a big emphasis on recurrences (loops are recurrences). $\endgroup$ – Yves Daoust Oct 31 '18 at 14:46
  • 1
    $\begingroup$ @YvesDaoust while this may be technically true, I don't agree with what I think you may be implying here. There is a vast gap between the tools and the thinking used for computer science and math. $\endgroup$ – DreamConspiracy Oct 31 '18 at 14:49
  • $\begingroup$ @YvesDaoust I maybe should have been more clear. Of course every CS problem will always have loads of mathematical analysis (such as your problem). But the distinction that I'm making is in the high level approaches. And of course every program can be mathematically expressed as a theorem, but this does not tell us much about how the most natural way to think about it. Coincidentally, I can give you an example from my morning. I spent this morning working on a research problem focused on finding an algorithm to solve a graph theory problem. Of course I could look at this algorithm as a $\endgroup$ – DreamConspiracy Oct 31 '18 at 15:03
  • $\begingroup$ (cont.) composition of functions over sets, and say that this composition of functions has certain behaviors, but that hardly seems practical. Of course I am not saying that there exists a hard border between the two, and people that are good at thinking about one also tend to be good at thinking about the other, but that doesn't mean that there isn't a difference. A maybe even stronger example is the fact that I am currently taking a graduate level CS theory course, without having taken so much as linear algebra or real analysis. Idk if this explanation is better, but hopefully it helps $\endgroup$ – DreamConspiracy Oct 31 '18 at 15:11
  • $\begingroup$ Speaking as someone with a maths background, mathematicians do not think of an algorithm as merely the function that it defines, and much of maths can be rewritten in the language of algorithms - indeed, doing so is often of benefit to mathematicians (this is roughly the program of constructive mathematics). $\endgroup$ – Robin Saunders Oct 31 '18 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.