News for hackers. Stuff that matters.
Re:After centuries, a seemingly simple math problem gets an ... by FartyMcFarter on Thursday December 10, 2020 @03:07PM (#25377907)
I'm struggling to come up with examples.

Maybe the 3n+1 problem? It's definitely easy to understand in a few seconds, and definitely fiendishly hard. I'm not sure if it seems easy to solve though :)

Another one that came to mind is about efficiently computing the permanent of a matrix[1]. Maybe understandable in seconds if you know how determinants work.

[1] https://en.wikipedia.org/wiki/Computing_the_permanent

Re:After centuries, a seemingly simple math problem gets an ... by DataDaoDe on Thursday December 10, 2020 @04:17PM (#25378841)
3n + 1 is interesting because it seems so tantalizingly easy and beautiful at first glance. Its like looking at a stream where you can clearly see the stony bed and it appears to be ankle deep but once you take a step you realize the lighting has fooled you and you fall head over heels into icy waters.
Re:After centuries, a seemingly simple math problem gets an ... by pas on Thursday December 10, 2020 @04:33PM (#25379016)
It's so much more interesting if you happen to know about the "hydra game" (the Goodstein theorem), which is also a question about sequences and their termination at 0.

https://en.wikipedia.org/wiki/Goodstein%27s_theorem

But this is easily proved (using infinite ordinals, but it seems it could be proved just by coming up with a similar concept like the infinite ordinal arithmetic, basically providing an upper bound for each step of the algorithm and showing that there's an eventual maximum to these and then there's a monotonic decrease, and that the number of steps are always finite).