Hacker News Reader

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. :)

> 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?

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....

[2] https://aphyr.com/posts/342-typing-the-technical-interview

"These queens can stab in eight directions. You always assumed that was a metaphor"

Excellent.

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.

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.

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?

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.

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/

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.

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.

`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