3 ms·

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

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.

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.