Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Project Euler 001 the Hard Way

statagroup.com

Post reply on HN
Print view View original

41–46 of 46 posts

Re: Project Euler 001 the Hard Way

#41

Post by chongli »

gordaco wrote: post #4

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 Proj…

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.

Re: Project Euler 001 the Hard Way

#42

Post by Grue3 »

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.

Re: Project Euler 001 the Hard Way

#43

Post by gordaco »

chongli wrote: post #41
gordaco wrote: post #4

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 Proj…

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 ar…

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.

Re: Project Euler 001 the Hard Way

#44

Post by [deleted] »

gordaco wrote: post #43
chongli wrote: post #41

Earlier quoted context omitted.

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 ar…

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]

Re: Project Euler 001 the Hard Way

#45

Post by chongli »

gordaco wrote: post #43
chongli wrote: post #41

Earlier quoted context omitted.

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 ar…

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?

Re: Project Euler 001 the Hard Way

#46

Post by gordaco »

chongli wrote: post #45
gordaco wrote: post #43

Earlier quoted context omitted.

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.
Post reply on HN