News for hackers. Stuff that matters.
Re:Project Euler 001 the Hard Way by FabHK on Sunday February 02, 2020 @08:38AM (#22216846)
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 <M numbers> below <N>", 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?

Re:Project Euler 001 the Hard Way by Someone on Sunday February 02, 2020 @09:31AM (#22217059)
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)

Re:Project Euler 001 the Hard Way by FabHK on Sunday February 02, 2020 @09:54AM (#22217166)
> The solution for this is to replace “product of n and m” bij “least common multiple of n and m”

Nice, and it works for my example, too:

    Number of multiples of either 3 or 6
    = Number of multiples of 3
    + Number of multiples of 6
    - Number of multiples of lcm(3,6) = 6
    = Number of multiples of 3
Cool. How to extend to more than 2 numbers?
Re:Project Euler 001 the Hard Way by jarekkruk on Sunday February 02, 2020 @01:52PM (#22218577)
You could do it like in article, so for every nonempty element in powerset (combinations for each length) of those numbers calculate their lcm and add or subtract amount of multiplies of lcm according to length of element.

So for A, B, C you have (M-number of multipliers) M(lcm(A)) + M(lcm(B)) + M(lcm(C)) - M(lcm(B,C)) - M(lcm(A,C)) - M(lcm(A,B)) + M(lcm(A,B,C))

Re:Project Euler 001 the Hard Way by kevinventullo on Sunday February 02, 2020 @12:27PM (#22218035)
The inclusion-exclusion algorithm can be made more efficient by observing that you can stop as soon as the lcm's of your subsets exceed N. That should happen fairly early on assuming e.g. N << 2^M.
Re:Project Euler 001 the Hard Way by chupasaurus on Sunday February 02, 2020 @06:45PM (#22220290)
> you can stop as soon as the lcm's of your subsets exceed N

Actually if N < 2 * lcm, because you can't use the fact that the distribution of multiples is the same on (1, lcm) and (k * lcm+1, lcm(k+1)) while you still have to count on (N - N mod lcm + 1, N).