A Brief Guide to Project Euler
Or maybe not so brief, but it's a guide!
Perhaps you have read my earlier piece and want to participate in Project Euler. Or perhaps you've dipped your toes in, but are unsure how to get the most out of it, are intimidated by the sheer number of problems, or just want to know how you can even get started on some of the many difficult problems on the site.
If this is the case, this guide is for you! In the first part, I'll talk about how to approach Project Euler in general: how you can get the most benefit from the site, how to select problems to work on, and some general advice for participating in Project Euler for the long haul. In the second, I'll discuss how to approach actually solving a difficult Project Euler problem, including the lifecycle of a typical solution and tips for conquering the many challenging problems that Project Euler has to offer.
How to get the most out of Project Euler
Know why Project Euler exists
Many people bounce off of Project Euler because their expectations are misaligned with its primary purposes. Project Euler has two main goals:
To provide a set of high-quality problems, across a variety of mathematical topics and a wide range of difficulties, whose solution involves exploration and creativity (rather than merely applying a memorized technique). The problems are intended to be fun to solve.
To guide the solvers of the problems in learning interesting mathematics, whether as a prerequisite to solving a problem, or as part of the exploration that leads to a solution. The mathematical knowledge gained in solving easier (or earlier-released, which is not always the same thing) problems is then built on for harder (or later-released) problems.
Project Euler is not intended as a way to practice programming or as exercises for learning a new programming language. It's not even, primarily, intended as a competition — there is an optional competitive aspect, with fastest-solvers lists on new problems, but this is not truly essential to its purpose.
This should shape how you engage with Project Euler. To get the most of the site, you should approach problems as opportunities to challenge yourself and to learn, not as tasks to complete. And you should expect many difficult problems to feel "unfair" at first, demanding a lot of effort to crack, and often requiring knowledge and ideas you may not have been exposed to before starting. You will probably need to accept that there are quite a few problems that you cannot yet solve, even with many hours of work. You may need to step away from a problem, and leave it unsolved until you can come back to it months or even years later, armed with more knowledge and a fresh perspective.
Don't be afraid to solve problems out of order
You really, really don't need to solve problems in numerical order, or in order of increasing difficulty, or any other order. Sometimes a particular problem is too difficult for you right now. Sometimes you want to solve a problem about a particular topic — or take a break from problems about a particular topic. Sometimes you just aren't vibing with a particular problem. Sometimes you want to try an easier problem, or a harder problem. Sometimes you want to try a new problem, or an old classic. Any of these are valid reasons to skip around and do problems out of order.
Also, most of the later problems are higher quality and more fun than many of the first 100, where quality is a bit more uneven. So if you find the early problems boring, try some later ones!
Solve early problems the hard way
There are many early problems which can be solved by calling functions from easily-installed libraries, or even built in functions, in some popular programming languages. And many of them can be purely "brute-forced" in an inefficient way, and still finish relatively quickly. It's worth your time to try to find efficient solutions on your own, rather than calling these functions or just running an obvious brute force. This is not so much because calling library functions is "cheating", but rather because you can learn quite a lot from figuring out and implementing things yourself.
Pay attention to difficulties, but don't take them too seriously
Each problem in the archives has a difficulty rating on a 20-point scale, 5% through 100% in 5% increments, with 100% being the hardest difficulty. Sorting by difficulty in the archives also reveals some ordering within the difficulty bands.
These can be a rough guide to the difficulty of a problem, but they are not perfect and shouldn't be treated as such. Difficulty can be a very personal thing, depending on things like your background knowledge, how you think, and even whether you happen to get a lucky insight relatively early in working on a problem. Moreover, many relatively early (numbered up to 300) problems have greatly inflated difficulty relative to more recent problems, making comparison trickier.
Nevertheless, it's probably a good idea to take the reported difficulty into account when deciding what problems to work on, especially as you are starting out. Lower-difficulty problems usually have less in the way of required prerequisite knowledge, and tend to be more approachable in general, while high-difficulty problems are usually substantial challenges even for very knowledgeable and experienced solvers. Keep an eye on how the difficulty of problems matches up to the trouble you had in solving them, and look to work on problems that are at the limit of your current knowledge and ability rather than far beyond it.
Remember that if you haven't solved a problem, you may not know why
A common mistake beginners make is to think that because they can think of some algorithm to compute the answer a problem, even if it will take hours, days, or longer to complete, that they have solved the core of the problem and any needed speedup is just some finicky implementation trick and isn't "really" part of the problem. This is almost always false. If your algorithm won't finish in a reasonable amount of time, you are likely to be missing a key insight that is actually core to the real problem. Moreover, this missing piece may be purely mathematical, purely algorithmic, or some combination of the two. If you don't have a working, fast program, you need to keep an open mind and not assume that your current idea is actually a viable solution.
Don't be afraid to fail
Sometimes you won't be able to solve a problem. You might be missing some important bit of background, or you might not have hit on a necessary insight to make the problem tractable. You may have been working on the problem for hours or days with no real progress, and not see how to proceed. This is okay! Sometimes you need to admit defeat and move on. Take a break. Solve some other problems. You can come back to the problem later, with a fresh mind and more experience.
When you set a problem aside unsolved, remember that failure to solve a problem on this attempt is not a permanent forfeit, it is a strategic retreat. You may not be ready to conquer this problem yet, but who knows about the future? If you find yourself tempted to cheat (by looking for another's solution, asking for a solution from AI, or the like), just step away from the problem; don't deprive your future self of the experience of solving it under your own steam. The problem will still be waiting for you when you are ready for it.
How to solve a Project Euler problem
Many Project Euler problems have a similar structure and presentation. You are given a setup, and some function (usually of integers) related to that setup is defined. At least one, and generally two or three, values of the function are given. Finally, you are requested to compute the value of the function for a much larger input, possibly modulo some given integer. All of these pieces can be useful in solving the problem.
Understand the problem
The first step in solving a problem is to understand it. Work carefully through the problem statement and any examples, making sure that you fully understand any definitions. Very frequently, the smallest given value of the function-to-compute can be used to validate your understanding: you can often compute it by hand, or with a small, straightforward program, if you understand the definitions in the problem.
You need to understand the problem before trying to solve it. It may sound silly to say this, but surprisingly often people will try to jump in to coding before they have taken the time to be clear on exactly what the setup is and what is being asked for. Don't fall into this trap.
Work small examples by hand, or by using simple, straightforward code
You can usually work out some small examples with pencil and paper, or by writing some inefficient, but straightforward code. Any code you write now will be very unlikely to be used in your final solution, but that's not the point here. Your goal is primarily to generate data: you want to be able to validate the correctness of other, less obvious algorithms you may come up with later, and you want as much data as you can get to try to find patterns.
If the function-to-compute in the problem is a composite (for instance, a sum of values of another defined function), you may want to write code to calculate values of the simpler function(s) as well. Sometimes patterns will be clearer when looking at these related function values.
Look up keywords in the problem
If the problem title or problem statement contains something that seems like a name, or some terminology you don't recognize, it can be worth looking this up (say, in Wikipedia) even if you otherwise understand the problem statement. These are often deliberate bread crumbs left by the problem writers to lead you to some mathematical background that might be useful to solving the problem. While you shouldn't try to find others' solutions to the exact problem at hand, you are encouraged to do research on the problem's topic when working on your solution. Project Euler is a journey of exploration, not a closed-book test.
At this point, you may have several options for making more progress. Try any of the next four that seem useful:
Apply standard mathematical transformations
Be on the lookout for ways to mathematically transform the function-to-compute and potentially simplify it or unlock other methods of computing it. One of the most common transformations is reversing the order of summation: take a double sum, switch the inner and outer sums, then try to simplify the new inner sum. This can work even when you have a single sum, if you can re-express the function being summed as a sum itself. Look to try this especially on number theory and combinatorics problems.
Change the problem domain
Often, the problem can be re-interpreted, after some calculation or simplification, as a problem in another domain entirely. The most common way this happens is that a problem which is not obviously a number theory problem can be transformed into a sum of number-theoretic functions or into a problem of counting or computing the solutions to a Diophantine equation. A surprisingly large fraction of plane geometry problems are actually problems about Diophantine equations in disguise; the thing to look for is integer values for segment lengths or areas.
But there are other possible transformations as well. It's worth trying to brainstorm ways that the problem in front of you could secretly be a problem of an entirely different type; getting the right transformation can often be a key step of a solution.
Look for numerical patterns
If you have numerical data from some earlier work by hand or a simple program (and you usually should!), you can look for patterns in the data. Do values of the function seem to be related to each other, or to some other function you are familiar with, in some way? Can you find some recursive relationship? Are the values divisible by some surprising integer? Can you find any other unexpected patterns in the data?
Let your pattern-finding intuition run wild here. Write down all the ideas you have; they don't have to be formulas, or even have any obvious way that they might lead to a solution to the problem. Sometimes, an odd, unexplained pattern can be the loose thread that causes the problem to unravel, but you will have to pull on it, exploring why the odd thing happens, before it's even clear how it might be related to a solution at all.
Of course, not all apparent patterns are borne out; you will need to validate them, possibly by computing further values of your function. Beware of the "law of small numbers": with only a few small values, you'll have as many spurious patterns as real ones. So once you think you've found a pattern, it's important to validate it, either by generating enough data that you can be quite sure of it, or actually coming up with a proof.
The Online Encyclopedia of Integer Sequences can be quite useful here, though I'd advise against using it for most early problems, as doing so could short-circuit your own explorations if the exact sequence you need is already present, complete with formulas, in the database.
Work backwards from what is required
You can sometimes get a hint to a problem from the nature of the thing you need to compute. The most obvious way to do this is based on the size of the required test case. For instance, if you need to compute f(n) for n = 109, then a solution that is slower than linear (or in the worst case, O(n log n) ) is going to be too slow, so you know that a solution at least that fast must exist, which can give some hints as to the form it needs to take. Similarly, larger values of n mean that a sublinear solution is required, and n = 1018 (or similar) indicates that a logarithmic (or polylogarithmic) solution is intended. Going the other way, n = 106 is large enough that the intended solution must be faster than quadratic, perhaps O(n1.5) or even O(n log n); n = 104 is indicative of a quadratic solution, and so on. Of course, you can't conclude that an even faster solution is impossible (some problems request only small values but have a logarithmic solution), but these considerations can still guide your search, in addition to indicating when you might have found a viable solution.
But other things can be part of the problem as well. Many problems involve using a modulus, because the actual function value is quite large and requiring it is unrealistic. Often, computing the full function value in such cases is actually impossible, and using a modulus is necessary. But the value of the modulus itself can be a hint. Prime number moduli around 109 are common, because they allow products to fit in a 64-bit integer, and also allow finding arbitrary inverses. If the modulus is much larger, or if it is not prime, this may be a hint about what operations are required. (It could also be a source of some of the difficulty in the problem, though. Be careful what you assume!) Also, prime moduli of special forms, such as q2n + 1 for a relatively large value of n, can hint that an efficient solution exists which uses certain advanced techniques (in this case, probably the Number Theoretic Transform). On the other hand, just because a modulus other than 109 + 7 (the most common value) is chosen doesn't mean that there's some deep secret; sometimes, it's just picked so that its digits thematically reflect the problem in some way, or because the problem setter wanted to mix things up.
Other aspects of the problem can be hints, too. If the requested value of f(n) has n itself a prime, or has n highly divisible (say, by powers of many small prime factors), or something like this, this could be a hint: perhaps the problem is far more difficult (or even impossible) for n of a similar size without such properties.
If this seems like too much metagaming, you can usually ignore these strategies and just try to understand the mathematics first, and worry about how all these considerations factor in only when you need to code up your final computation. But it's not at all cheating to work these angles. Indeed, the fact that the problem is posed at all is a clear hint: you know that it can actually be solved, which is an immense leg up to finding a solution!
Rinse and repeat
Sometimes these investigations do not quite lead to a solution efficient enough to actually solve the problem. Perhaps you can do some simplification, but not enough to compute the required value; perhaps you need more data to find useful patterns. It's often worth taking what you can get here and turning it into a more efficient algorithm, even if it's not yet fast enough to solve the problem. You can code it up anyway, validate it against the data you already have, and generate more data, looking for more patterns. You can also use it as a launchpad for trying more manipulations and transformations of the problem.
On some problems I've gone through as many as four or five iterations of better and better solutions, each incorporating more ideas and insights that I found when experimenting or thinking about previous solutions, until I've put enough pieces together to hit on one that is fast enough to actually compute the requested test case of the problem. Coming to a good solution at the end of this process is quite satisfying.
Take a walk, go to sleep, or take a break
If you've worked on a problem for a long while, it's often a good idea to take your conscious mind off it for a while and get some rest. I've been frequently surprised when having a nice walk, or going to bed for the night, leads to some unexpected insights when I return to the problem later. And, of course, sometimes it's correct to just take a break from a problem indefinitely. You might not be ready to solve this one yet, and that's okay. You're here to learn and have fun, not to beat your head against a brick wall for days on end, so try some other problems instead, and come back when you're ready.