4 ms·

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;

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
  "These queens can stab in eight directions. You always assumed that was a metaphor" Excellent.
fctorial 7y ago
From the problem 700: Consider the sequence 1504170715041707n mod 4503599627370517 Could you explain what 'n mod' means? Google doesn't seem to know what that is.
- stevelosh 7y ago
  `n` is the position in the sequence: n=1 = (mod (* 1504170715041707 1) 4503599627370517) = 1504170715041707 n=2 = (mod (* 1504170715041707 2) 4503599627370517) = 3008341430083414 n=3 = (mod (* 1504170715041707 3) 4503599627370517) = 8912517754604
- philiplu 7y ago
  The problem is a bit underspecified, perhaps. 'n' is a positive integer, so 1, 2, 3, .... So the sequence is found by multiplying 1504170715041707 by 1, 2, 3, ... sequentially, then finding the remainder when you divide each of those products by 4503599627370517.
chongli 7y ago
which is an easy one if you know basic modular arithmetic Have you solved it? It looks nontrivial to me. 4503599627370517 is a prime number which means you’re dealing with a cyclic group generated by all nonzero elements up to 4503599627370516. Since the problem chose 1504170715041707 as the generator, any number less than that is potentially an Eulercoin. Of course, only those in decreasing order within the cycle are allowed. The smallest Eulercoin my naïve C loop could find was 19471 after over 5 minutes of CPU time, with the time to find each one increasing exponentially. This was compiled with clang -O3, running on my 2017 MacBook Pro. Since we’re dealing with an additive cyclic group, the smallest element will be 0, which is the last Eulercoin. Finding the second-last (the smallest positive element) does not seem to be something you can brute force, as searching the entire cyclic group (4503599627370517 elements including 0) would take my laptop approximately 178 days.
- gordaco 7y ago
  Yes, I solved it, but not by that method. When I talked about "basic modular arithmetic" I didn't mean repeated addition and the usage of "mod"; I mean that I used certain basic operation which gets taught in any introductory discrete math program. Sorry if I don't get very specific, I don't want to spoil it :). A suggestion: think about the end of the sequence and move backwards from there.
  - deleted 7y ago
    [deleted]
  - chongli 7y ago
    I solved it. My solution was pretty ugly. I ended up brute-forcing it from both directions after finding the multiplicative inverse. Did you have a more elegant solution?
    - gordaco 7y ago
      No, my solution was also mostly "brute-forcing from both directions". In the problem thread you can find more elegant solutions that rely on calculating increments, but my approach was very fast (0.3 seconds) so it's good enough for me.

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
"These queens can stab in eight directions. You always assumed that was a metaphor" Excellent.

fctorial 7y ago

From the problem 700: Consider the sequence 1504170715041707n mod 4503599627370517 Could you explain what 'n mod' means? Google doesn't seem to know what that is.

stevelosh 7y ago
`n` is the position in the sequence: n=1 = (mod (* 1504170715041707 1) 4503599627370517) = 1504170715041707 n=2 = (mod (* 1504170715041707 2) 4503599627370517) = 3008341430083414 n=3 = (mod (* 1504170715041707 3) 4503599627370517) = 8912517754604
philiplu 7y ago
The problem is a bit underspecified, perhaps. 'n' is a positive integer, so 1, 2, 3, .... So the sequence is found by multiplying 1504170715041707 by 1, 2, 3, ... sequentially, then finding the remainder when you divide each of those products by 4503599627370517.

chongli 7y ago

which is an easy one if you know basic modular arithmetic Have you solved it? It looks nontrivial to me. 4503599627370517 is a prime number which means you’re dealing with a cyclic group generated by all nonzero elements up to 4503599627370516. Since the problem chose 1504170715041707 as the generator, any number less than that is potentially an Eulercoin. Of course, only those in decreasing order within the cycle are allowed. The smallest Eulercoin my naïve C loop could find was 19471 after over 5 minutes of CPU time, with the time to find each one increasing exponentially. This was compiled with clang -O3, running on my 2017 MacBook Pro. Since we’re dealing with an additive cyclic group, the smallest element will be 0, which is the last Eulercoin. Finding the second-last (the smallest positive element) does not seem to be something you can brute force, as searching the entire cyclic group (4503599627370517 elements including 0) would take my laptop approximately 178 days.

gordaco 7y ago
Yes, I solved it, but not by that method. When I talked about "basic modular arithmetic" I didn't mean repeated addition and the usage of "mod"; I mean that I used certain basic operation which gets taught in any introductory discrete math program. Sorry if I don't get very specific, I don't want to spoil it :). A suggestion: think about the end of the sequence and move backwards from there.
- deleted 7y ago
  [deleted]
- chongli 7y ago
  I solved it. My solution was pretty ugly. I ended up brute-forcing it from both directions after finding the multiplicative inverse. Did you have a more elegant solution?
  - gordaco 7y ago
    No, my solution was also mostly "brute-forcing from both directions". In the problem thread you can find more elegant solutions that rely on calculating increments, but my approach was very fast (0.3 seconds) so it's good enough for me.