28 ms·

Project Euler 001 the Hard Way

98 points by bdg 7y ago

pizzaknife 7y ago
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
- bdg 7y ago
  Thank you. My original version 8 years ago included a short tour into "The Inclusion-exclusion principle" which is how I eventually derived the pattern to use even/odd sums of bits in the ABC=111 encoding. I cut it out because I felt it was distracting for most of my readers. I eventually summarized it this way after a few wordy paragraphs that explained the way the equation worked: > The sum of all the intersections would mean (if we had 4 items, A, B, C, D) adding together A, B and C and D. The second line would mean we subtract the sum of AB, AC, AD, BC, BD, and CD. The third line means we add the sum of ABC, ABD, and BCD, the fourth line means we subtract the value of ABCD. The pattern here is we alternate the operation (adding or subtracting a sum) based on the cardinality (how many items are in a set) of something. Even cardinalities are subtracted, odd cardinalities are added. We sum together all combinations of that cardinality.
gordaco 7y ago
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 https://projecteuler.net/problem=268 [1] https://projecteuler.net/problem=700 https://projecteuler.net/problem=700
- its_dario 7y ago
  > Isn't this like... really, really basic? Yeah, it's reasonably basic. For the problem as stated where there are only 1000 numbers to iterate over, though, I wouldn't have bothered wasting time thinking about it when the naive implementation is fast enough that it doesn't matter. Why start with something more complicated (assuming you're going to program it rather than just solving it outright on paper) when the simple way works?
- fiblye 7y ago
  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. :)
- macintux 7y ago
  Please don’t discourage people who missed that insight. This would have been a much better comment using the 10000 attitude. https://www.xkcd.com/1053/ https://www.xkcd.com/1053/
- deleted 7y ago
  [deleted]
- exdsq 7y ago
  It might be 'basic' but it's the starting point for most people! The fun things with these 'simple' problems is that you can solve them in so many ways. Two of my favourite posts I've recently read where they've solved beginner problems 'the Hard Way' are: FizzBuzz with a domain specific language [1] and the N Queens problem without declaring a value type [2] [1] https://themonadreader.files.wordpress.com/2014/04/fizzbuzz.pdf https://themonadreader.files.wordpress.com/2014/04/fizzbuzz.... [2] https://aphyr.com/posts/342-typing-the-technical-interview https://aphyr.com/posts/342-typing-the-technical-interview
  - sorokod 7y ago
FabHK 7y ago
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?
- Someone 7y ago
  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)
  - FabHK 7y ago
jpxw 7y ago
`sumMultiplesOfTwoAndThree` should probably be `sumMultiplesOfThreeAndFive` right?
Ragib_Zaman 7y ago
>...where I discover the hidden complexity of a simple programming problem. I thought it was very ironic that soon after that sentence, the author claims the arithmeticSum method is O(1) when it is actually O(log(n) log(log(n))). Many people seem to assume that multiplication is a constant time operation. There is actually immense "hidden complexity" in doing multiplication of arbitrarily large integers efficiently. David Harvey proved last year that multiplication of two n bit integers can be done in O(n log n). It is still an open conjecture that this is the best possible.
- dahart 7y ago
  You’re right, and it’s a good point, but I think you’re too hard on the author and other people. > the author claims the arithmeticSum method is O(1) He really claimed that Gauss’ formula is O(1), where it’s reasonable to assume multiplication without a specific implementation is constant. After that he gave an implementation in JavaScript that is O(1). It’s only a larger complexity if you use numeric methods on computers that support arbitrarily large numbers. > Many people seem to assume that multiplication is a constant time operation. Multiplication is constant time for the built-in data types, for any 64-bit ints or doubles. It’s okay to call it constant until you use huge number methods.
  - rwbhn 7y ago
    But the author follows that with "It works the same way for 100 as it does 10e100."
    - dahart 7y ago
      True! That statement does follows the math formula, and by itself the statement is true regardless of complexity. It will work the same way for small numbers as large ones. The 10e100 comment does precede the implementation, and this particular O(1) implementation of course might not support inputs in the range of 10e100 exactly.
  - Ragib_Zaman 7y ago
    I disagree. Why would it be reasonable to assume "multiplication without a specific implementation is constant"? By definition, Big-O complexity describes what happens as a certain parameter gets arbitrarily large. If we say "ok but if we restrict that parameter to common sizes, it's actually O(1)", then everything is O(1). There is some constant C where Bubble sort will sort any array that fits into your RAM within C seconds, so is it okay to call Bubble sort constant time until you use huge array methods that process arrays on your hard drive?
appleiigs 7y ago
If i was shown the fizz buzz question in a job interview, and i answered using the “hard way”, how would they respond? Would they be impressed by the math? Or would they complain about the number of lines of code, readability for code review, etc?
- ubercow13 7y ago
  What's the 'hard way'?
  - appleiigs 7y ago
    The title of the post is the “Euler 001 the Hard Way”. The way i read it, the hard way would be “Solving all combinations with performance”.
- dahart 7y ago
  I think that’s a good question. I’ve interviewed and hired a lot of people, and if someone answered the question this way, I think I would enjoy the ‘hard way’ answer. It would depend on the style and framing of the answer as much as the substance. It’s easy to enjoy as a ‘let’s explore the bounds of this problem’ or a ‘let’s do this in an unnecessarily difficult generalization, just for fun/curiosity’. It would be useful in an interview if the candidate recognizes and states that this might be a bad engineering decision, even if it’s good math. When I’m hiring, I want to find people that can generalize and explore a problem, see the larger picture in an interesting way. This article does that. And, just as important is finding people who know when not to do that in practice, who can recognize when and why it’s important to call something good enough, and move on to other problems.
JakeStone 7y ago
Something similar from 4+ years ago, but in C# https://gist.github.com/RichardVasquez/6780214 https://gist.github.com/RichardVasquez/6780214
deleted 7y ago
[deleted]
master_yoda_1 7y ago
To Author: good for your weekend musing. But please don't torture interviewer with it (with time limit of 45 minutes).
foxes 7y ago
The inclusion/ exclusion idea can actually be useful for harder project euler questions (deriving some sort of closed form sum to compute). Worthwhile to think about. Im also reminded about the "semigroup resonance" way to solve fizzbuzz posted recently on hn [0]. Seems like another interesting method. [0] https://blog.ploeh.dk/2019/12/30/semigroup-resonance-fizzbuzz/ https://blog.ploeh.dk/2019/12/30/semigroup-resonance-fizzbuz...
Grue3 7y ago
It's not the hard way, it's the way you're supposed to "solve" a PE problem. Almost all of them are trivially solvable by brute force and a sufficiently powerful computer. Instead you're supposed to analyze the problem and find a mathematical "trick" that makes it solvable even with pen and paper.

98 points by bdg 7y ago

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

bdg 7y ago
Thank you. My original version 8 years ago included a short tour into "The Inclusion-exclusion principle" which is how I eventually derived the pattern to use even/odd sums of bits in the ABC=111 encoding. I cut it out because I felt it was distracting for most of my readers. I eventually summarized it this way after a few wordy paragraphs that explained the way the equation worked: > The sum of all the intersections would mean (if we had 4 items, A, B, C, D) adding together A, B and C and D. The second line would mean we subtract the sum of AB, AC, AD, BC, BD, and CD. The third line means we add the sum of ABC, ABD, and BCD, the fourth line means we subtract the value of ABCD. The pattern here is we alternate the operation (adding or subtracting a sum) based on the cardinality (how many items are in a set) of something. Even cardinalities are subtracted, odd cardinalities are added. We sum together all combinations of that cardinality.

gordaco 7y ago

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 https://projecteuler.net/problem=268 [1] https://projecteuler.net/problem=700 https://projecteuler.net/problem=700

its_dario 7y ago
> Isn't this like... really, really basic? Yeah, it's reasonably basic. For the problem as stated where there are only 1000 numbers to iterate over, though, I wouldn't have bothered wasting time thinking about it when the naive implementation is fast enough that it doesn't matter. Why start with something more complicated (assuming you're going to program it rather than just solving it outright on paper) when the simple way works?
fiblye 7y ago
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. :)
macintux 7y ago
Please don’t discourage people who missed that insight. This would have been a much better comment using the 10000 attitude. https://www.xkcd.com/1053/ https://www.xkcd.com/1053/
deleted 7y ago
[deleted]
exdsq 7y ago
It might be 'basic' but it's the starting point for most people! The fun things with these 'simple' problems is that you can solve them in so many ways. Two of my favourite posts I've recently read where they've solved beginner problems 'the Hard Way' are: FizzBuzz with a domain specific language [1] and the N Queens problem without declaring a value type [2] [1] https://themonadreader.files.wordpress.com/2014/04/fizzbuzz.pdf https://themonadreader.files.wordpress.com/2014/04/fizzbuzz.... [2] https://aphyr.com/posts/342-typing-the-technical-interview https://aphyr.com/posts/342-typing-the-technical-interview
- sorokod 7y ago

FabHK 7y ago

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?

Someone 7y ago
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)
- FabHK 7y ago

jpxw 7y ago

`sumMultiplesOfTwoAndThree` should probably be `sumMultiplesOfThreeAndFive` right?

Ragib_Zaman 7y ago

>...where I discover the hidden complexity of a simple programming problem. I thought it was very ironic that soon after that sentence, the author claims the arithmeticSum method is O(1) when it is actually O(log(n) log(log(n))). Many people seem to assume that multiplication is a constant time operation. There is actually immense "hidden complexity" in doing multiplication of arbitrarily large integers efficiently. David Harvey proved last year that multiplication of two n bit integers can be done in O(n log n). It is still an open conjecture that this is the best possible.

dahart 7y ago
You’re right, and it’s a good point, but I think you’re too hard on the author and other people. > the author claims the arithmeticSum method is O(1) He really claimed that Gauss’ formula is O(1), where it’s reasonable to assume multiplication without a specific implementation is constant. After that he gave an implementation in JavaScript that is O(1). It’s only a larger complexity if you use numeric methods on computers that support arbitrarily large numbers. > Many people seem to assume that multiplication is a constant time operation. Multiplication is constant time for the built-in data types, for any 64-bit ints or doubles. It’s okay to call it constant until you use huge number methods.
- rwbhn 7y ago
  But the author follows that with "It works the same way for 100 as it does 10e100."
  - dahart 7y ago
    True! That statement does follows the math formula, and by itself the statement is true regardless of complexity. It will work the same way for small numbers as large ones. The 10e100 comment does precede the implementation, and this particular O(1) implementation of course might not support inputs in the range of 10e100 exactly.
- Ragib_Zaman 7y ago
  I disagree. Why would it be reasonable to assume "multiplication without a specific implementation is constant"? By definition, Big-O complexity describes what happens as a certain parameter gets arbitrarily large. If we say "ok but if we restrict that parameter to common sizes, it's actually O(1)", then everything is O(1). There is some constant C where Bubble sort will sort any array that fits into your RAM within C seconds, so is it okay to call Bubble sort constant time until you use huge array methods that process arrays on your hard drive?

appleiigs 7y ago

If i was shown the fizz buzz question in a job interview, and i answered using the “hard way”, how would they respond? Would they be impressed by the math? Or would they complain about the number of lines of code, readability for code review, etc?

ubercow13 7y ago
What's the 'hard way'?
- appleiigs 7y ago
  The title of the post is the “Euler 001 the Hard Way”. The way i read it, the hard way would be “Solving all combinations with performance”.
dahart 7y ago
I think that’s a good question. I’ve interviewed and hired a lot of people, and if someone answered the question this way, I think I would enjoy the ‘hard way’ answer. It would depend on the style and framing of the answer as much as the substance. It’s easy to enjoy as a ‘let’s explore the bounds of this problem’ or a ‘let’s do this in an unnecessarily difficult generalization, just for fun/curiosity’. It would be useful in an interview if the candidate recognizes and states that this might be a bad engineering decision, even if it’s good math. When I’m hiring, I want to find people that can generalize and explore a problem, see the larger picture in an interesting way. This article does that. And, just as important is finding people who know when not to do that in practice, who can recognize when and why it’s important to call something good enough, and move on to other problems.

JakeStone 7y ago

Something similar from 4+ years ago, but in C# https://gist.github.com/RichardVasquez/6780214 https://gist.github.com/RichardVasquez/6780214

deleted 7y ago

[deleted]

master_yoda_1 7y ago

To Author: good for your weekend musing. But please don't torture interviewer with it (with time limit of 45 minutes).

foxes 7y ago

The inclusion/ exclusion idea can actually be useful for harder project euler questions (deriving some sort of closed form sum to compute). Worthwhile to think about. Im also reminded about the "semigroup resonance" way to solve fizzbuzz posted recently on hn [0]. Seems like another interesting method. [0] https://blog.ploeh.dk/2019/12/30/semigroup-resonance-fizzbuzz/ https://blog.ploeh.dk/2019/12/30/semigroup-resonance-fizzbuz...

Grue3 7y ago

It's not the hard way, it's the way you're supposed to "solve" a PE problem. Almost all of them are trivially solvable by brute force and a sufficiently powerful computer. Instead you're supposed to analyze the problem and find a mathematical "trick" that makes it solvable even with pen and paper.