Home > Algorithms, Programming, Uncategorized > Project Euler tips

Project Euler tips


A few years back I started working on Project Euler problems mainly because it was fun from a mathematical point of view, but also to improve my programming skills. After solving about 120 problems I seem to have hit a wall, because the numbers involved in some of the problems were just too big for my simple brute-force algorithms.

Recently, I decided to try and see if I can do some more of these problems. I cannot say that I’ve acquired some new techniques between 2012-2016 concerning the mathematics involved in these problems. My research topics are usually quite different and my day to day programming routines are more about constructing new stuff which works fast enough than optimizing actual code. Nevertheless, I have some experience coding in Matlab, and I realized that nested loops are to be avoided. Vectorizing the code can speed up things 100 fold.

So the point of Project Euler tasks is making things go well for large numbers. Normally all problems are tested and should run within a minute on a regular machine. This brings us to choosing the right algorithms, the right simplifications and finding the complexity of the algorithms involved.

For example if you need to compute a certain sum {\sum_{i=1}^nP(i)} what is the best way to proceed? Computing each {P(i)} in turn and summing them up in a loop gives us an {O(n)} algorithm. This means that computation time is roughly proportional to {n} (this depends also on {P}, but let’s suppose {P} is something which we can compute in {O(1)} time, that is, instantly). Therefore, if {n} is of order {10^8}, this can be done on a regular machine. However, if {n=10^{16}}, it may take, literally, ages for the algorithm to finish. For {n=10^{16}} an algorithm of complexity {O(\sqrt{n})}, which scales with the square root of {n}, should work. However let’s say you have {n=10^{40}} in mind. Then either we find some {O(n^{1/d})} algorithm with {d} large enough or, even better, find a {O(\log n)} algorithm, which scales like {\log n}. Roughly, if the algorithm works for {n=10}, it should only take {40} times more time to reach {10^{40}}. Best of all, if you can find a direct formula for the sum, then you have an “instant” {O(1)} algorithm (whether this is instant or not depends on the formula you got…).

Maybe this could become more clear using some examples.

1. {P(n) = n^2}. The basic summation is {O(n)} time, but using the formula {\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6} gives an {O(1)} algorithm. Basically, you can compute this sum for any {n} you want by doing a couple of elementary operations.

2. Let’s complicate things a bit. What if {P(n)} is {\sigma(n)}: the sum of all the divisors of {n}? First let’s note that computing {\sigma(n)} alone is not immediately computable. One can imagine a basic {O(n)} algorithm, testing all integers {1\leq d \leq n/2} if {d|n} and summing them. If we know the factorization of {n} we have a formula for {\sigma(n)} in terms of prime factors and their powers. Prime factorization’s complexity is {O(\log n)} provided we have already made a sieve of primes (that’s other thing to think about). So we reach a {O(n\log n)} complexity for {\sum_{i=1}^n \sigma(n)}. This is not enough if we want to sum things up to {n=10^{16}}, for example. It turns out there’s a simple idea for a less complex algorithm.

We want to compute

\displaystyle \sum_{i=1}^n \sum_{d | i} d.

Now what if we invert the sums? How do we do this? The summation indices satisfy {1\leq d \ | i \leq n}. Thus, if we want to sum over {d} instead of {i}, then {i} would be a multiple of {d} all the time. So we find the alternative sum

\displaystyle \sum_{d=1}^n \sum_{d|i,\ i\leq n}d=\sum_{d=1}^n d \sum_{d|i, i \leq n}=\sum_{d=1}^n d \left\lfloor \frac{n}{d} \right\rfloor

where the last equality is valid since the number of multiples of {d} less than {n} is exactly {\lfloor n/d\rfloor}. This already gives an {O(n)} complexity. Better than before, no factorizations involved, quite nice.

It turns out we can do even better. Looking at terms of the form {\lfloor n/d \rfloor} we see that they take the same value multiple times. For example {\lfloor n/d\rfloor =k} implies

\displaystyle \frac{n}{k+1} \leq d < \frac{n}{k}

Thus, summing on this interval we have

\displaystyle \sum_{ \frac{n}{k+1} \leq d < \frac{n}{k}} d\lfloor n/d \rfloor = k\sum_{ \frac{n}{k+1} \leq d < \frac{n}{k}} d

where the last sum has an explicit value since we sum consecutive terms of an arithmetic progression. Now we can switch to a summation over {k} instead of {d}. Note that we only need to go to {k} high enough such that between {n/(k+1)} and {n/k} there is at least one integer. This is equivalent to {k(k+1) \leq n} so {k} is {O(\sqrt{n})}. For {k} larger than this value, we cannot guarantee the existence of an integer {d} in our interval, so we’ll just compute the sums up to this {k} and then sum the remaining terms which are again of order {O(\sqrt{n})}. This gives us a final {O(\sqrt{n})} algorithm.

Now, it is clear that if we need to compute our sum of sums of divisors up to {n=10^{16}}, for example, only an algorithm like the last one can lead us to the result in reasonable time. Now you can solve Problem 401 in no time 🙂 (replacing the sum of divisors with sum of squares doesn’t make much difference here, or does it?)

I hope this will motivate others to gain or regain interest in Project Euler problems. I solved over 120 problems in the last two months by learning to adapt algorithms and doing the necessary research when it is needed. Almost always, after solving a problem, you’ll find someone in the solution thread which has a better solution than yours. Look it up and continue improving your skills.

Project Euler problems don’t require only maths… Sometime more complex computer science stuff is needed. I learned the basics of dynamic programming and recursion solving some of the problems. I learned using lists, queues, combinatorial stuff, probabilities (still learning that though; lots of probability related stuff among PE problems). Not to mention that I learned to work quite well in some different languages, like Pari GP or Julia. It also forced me to compile and use some Java or Python codes.

It is a globally enriching quest: keep up with your maths, learn to do research online, improve programming skills, find new algorithms, choose right programming language to solve your problem efficiently, etc. It’s a hobby worth having.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: