Project Euler 001 the Hard Way

very cool write up. to me what it really illustrates is that dealing with arguably simple data and requirements, has different tiers of how to deal with the scaling quantity. At some point, a different language (math) becomes the required dialect, as programming language expressions become outmoded. Neat

Isn't this like... really, really basic? I would have never considered iterating over all the numbers, not even when I first entered Project Euler back in 2011; inclusion-exclusion always was the obvious way. I'm probably biased since I'm a big Project Euler fan and I probably have a much more math-oriented way of thinking than the average software developer, so take my opinion with a grain of salt.

Most serious Project Euler problems require finding ways to reduce the problem complexity into something manageable. For example, problem 268 is a more complex and challenging version of problem 1, which can't be solved by brute force in a reasonable amount of time [0]. Also, whenever you solve a problem, don't forget to check the problem thread, accessible only to solvers, for many mathematical insights (for example, here's a hint: buried somewhere in problem 10's thread, in what I believe to be the highest rated comment found in any problem thread all over Project Euler, you can find a very useful function that can be used to solve a few, much later, problems).

Also, just yesterday Project Euler released the 700th problem (which is an easy one if you know basic modular arithmetic) [1].

[0] https://projecteuler.net/problem=268

[1] https://projecteuler.net/problem=700

Some people find Project Euler when they're new programmers. There are also plenty of programmers who lack a strong math background and do these challenges as a way to grow and learn.

I'm not sure what your standing was back in 2011, but when I first found Project Euler, I was a lowly high school student in a rural town with a horrible math system. I was also just beginning to learn programming. I iterated through every number. :)

Two quick remarks:

> Looking at the code it’s quite obvious 3 and 5 are replaceable with any set of other numbers.

What's not obvious to me (I'm not a mathematician) is that both solutions answer the question correctly when the set of numbers is not pairwise coprime. For example, "Find the sum of all the multiples of 3 or 6 below 1000" is clearly just the same as "Find the sum of all the multiples of 3 below 1000", while the inclusion-exclusion algorithm will probably deliver a different answer. So, the set will need some pre-processing to remove common factors, which will then require adjusting the answers.

Next, for the problem "Find the sum of all the multiples of below ", the naive algorithm seems to have runtime of about O(NM), while the "sophisticated" algorithm seems to have runtime O(2^M) at least - so, as we increase M (the size of the test set), the "naive" algorithm will soon be faster, or not?

What's not obvious to me (I'm not a mathematician) is that both solutions answer the question correctly when the set of numbers is not pairwise coprime. For example, "Find the sum of all the multiples of 3 or 6 below 1000" is clearly just the same as "Find the sum of all the multiples of 3 below 1000", while the inclusion-exclusion algorithm will probably deliver a different answer.

You’re right. The solution for this is to replace “product of n and m” bij “least common multiple of n and m”. So, you would get (using 4 and 6 as an example that’s slightly better than 3 and 6):

   Number of multiples of either 4 or 6
    = Number of multiples of 4
    + Number of multiples of 6
    - Number of multiples of lcm(4,6) = 12

and yes, if M gets larger enough, the “naive” algorithm can get faster. It will help if you bail out once you have found _a_ divisor, and, if your numbers are ‘large enough’ (1), to do division testing in some specific order (2).

(1) what is ‘large’ will be system dependent. In general, once you need bigint’s, but if your CPU doesn’t have a division instruction, it can come earlier.

(2) in general, smallest to largest, but if one of your test divisors is a power of 2, move those up front. Also, if you’re forced to use bigint’s, divisors of “2^register size +/- 1 and their factors may be easier (just as testing divisibility by 9 or 11 or 9’s factor 3 is easier in decimal written integers)