News for hackers. Stuff that matters.
Re:Project Euler 001 the Hard Way by gordaco on Sunday February 02, 2020 @07:03AM (#22216571)
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

[1] https://projecteuler.net/problem=700

Re:Project Euler 001 the Hard Way by fiblye on Sunday February 02, 2020 @08:01AM (#22216726)
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. :)

Re:Project Euler 001 the Hard Way by its_dario on Sunday February 02, 2020 @07:44AM (#22216685)
> 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?

Re:Project Euler 001 the Hard Way by exdsq on Sunday February 02, 2020 @09:59AM (#22217182)
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

Re:Project Euler 001 the Hard Way by sorokod on Sunday February 02, 2020 @11:07AM (#22217558)
"These queens can stab in eight directions. You always assumed that was a metaphor"

Excellent.

Re:Project Euler 001 the Hard Way by chongli on Monday February 03, 2020 @02:27AM (#22222129)
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 by gordaco on Monday February 03, 2020 @11:12AM (#22225455)
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 by chongli on Tuesday February 04, 2020 @12:43AM (#22232775)
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 by gordaco on Tuesday February 04, 2020 @10:55AM (#22236987)
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.
Re:Project Euler 001 the Hard Way by macintux on Sunday February 02, 2020 @08:14AM (#22216763)
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/

Re:Project Euler 001 the Hard Way by fctorial on Sunday February 02, 2020 @12:16PM (#22217974)
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.
Re:Project Euler 001 the Hard Way by philiplu on Sunday February 02, 2020 @12:40PM (#22218115)
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.
Re:Project Euler 001 the Hard Way by stevelosh on Sunday February 02, 2020 @12:38PM (#22218102)
`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