And now for something else. Some hobby math problem.
https://www.wired.com/story/super-slow-computer-programs-reveal-maths-fundamental-limits/For the whole version but here is the short version.
The general introduction:
Super Slow Computer Programs Reveal Math's Fundamental Limits
The goal of the “busy beaver” game is to find the longest-running computer program. Its pursuit has surprising connections to profound questions in math.
PROGRAMMERS NORMALLY WANT to minimize the time their code takes to execute. But in 1962, the Hungarian mathematician Tibor Radó posed the opposite problem. He asked: How long can a simple computer program possibly run before it terminates? Radó nicknamed these maximally inefficient but still functional programs “busy beavers.”
...
An Uncomputable Computer Game
The busy beaver game is all about the behavior of Turing machines—the primitive, idealized computers conceived by Alan Turing in 1936. A Turing machine performs actions on an endless strip of tape divided into squares. It does so according to a list of rules. The first rule might say:
If the square contains a 0, replace it with a 1, move one square to the right and consult rule 2. If the square contains a 1, leave the 1, move one square to the left and consult rule 3.
...
As Turing noted in 1936, in order to compute something, a Turing machine must eventually halt—it can’t get trapped in an infinite loop. But he also proved that there’s no reliable, repeatable method for distinguishing machines that halt from machines that simply run forever—a fact known as the halting problem.
The busy beaver game asks: Given a certain number of rules, what’s the maximum number of steps that a Turing machine can take before halting?
For instance, if you’re only allowed one rule, and you want to ensure that the Turing machine halts, you’re forced to include the halt instruction right away. The busy beaver number of a one-rule machine, or BB(1), is therefore 1.
But adding just a few more rules instantly blows up the number of machines to consider. Of 6,561 possible machines with two rules, the one that runs the longest—six steps—before halting is the busy beaver. But some others simply run forever. None of these are the busy beaver, but how do you definitively rule them out? Turing proved that there’s no way to automatically tell whether a machine that runs for a thousand or a million steps won’t eventually terminate.
...
Proving that BB(2) = 6 and that BB(3) = 107 was difficult enough that Radó’s student Shen Lin earned a doctorate for the work in 1965. Radó considered BB(4) “entirely hopeless,” but the case was finally solved in 1983. Beyond that, the values virtually explode; researchers have identified a five-rule Turing machine, for instance, that runs for 47,176,870 steps before stopping, so BB(5) is at least that big. BB(6) is at least 7.4 × 1036,534. Proving the exact values “will need new ideas and new insights, if it can be done at all,” said Aaronson.
I hope that the general concept is a bit clear.
Then they get at one of those applications which are a great time waster at least for me. The Goldbach conjecture. It´s true but how to prove it.
So here is the slow program approach:
The Goldbach conjecture, for instance, asks whether every even integer greater than 2 is the sum of two primes. Proving the conjecture true or false would be an epochal event in number theory, allowing mathematicians to better understand the distribution of prime numbers. In 2015, an anonymous GitHub user named Code Golf Addict published code for a 27-rule Turing machine that halts if—and only if—the Goldbach conjecture is false. It works by counting upward through all even integers greater than 4; for each one, it grinds through all the possible ways to get that integer by adding two others, checking whether the pair is prime. When it finds a suitable pair of primes, it moves up to the next even integer and repeats the process. If it finds an even integer that can’t be summed by a pair of prime numbers, it halts.
Running this mindless machine isn’t a practical way to solve the conjecture, because we can’t know if it will ever halt until it does. But the busy beaver game sheds some light on the problem. If it were possible to compute BB(27), that would provide a ceiling on how long we’d have to wait for the Goldbach conjecture to be settled automatically. That’s because BB(27) corresponds to the maximum number of steps this 27-rule Turing machine would have to execute in order to halt (if it ever did). If we knew that number, we could run the Turing machine for exactly that many steps. If it halted by that point, we’d know the Goldbach conjecture was false. But if it went that many steps and didn’t halt, we’d know for certain that it never would—thus proving the conjecture true.
So this is a funny program. It should never halt just really , really slow down with the bigger numbers.
This is triggers some other questions. Can you write a 27 that terminates. Possibly, but not this one.
What i really like about this design is that this is really just the brute force counting up.
Not sure how you condense that to only 27 steps but i will look at that later.
Every even integer greater than 2 is the sum of two primes.
This is a result of using sieves. The statement can be translated to lets look at all natural numbers and then we divide relation between the boring stuff which is the multiples of two and the primes which are the numbers escaping the sieve if you build it up.
If you make an infinite page with all numbers going 10 per row and then strike out all the even numbers you have columns.
Then you snap your fingers and every number divisible by 3 gets struck out. Now you have 16,66% less holes. Multiples of 5 you only have to do if they are multiples odd numbers because all others lie on the 10 line. And then it gets messy.
Next up 7. You do not have to check for multiples of 2,3 or 5.
11 add 7 to that list.
The even numbers and primes all grow with a 2 factor. Evens go up by 2 all the time but the uneven ones don´t.
3 5 7 works
but 9 falls to 3
11 13
15 falls to 3
17 19
21 to 3
23
25 falls to 5
27 to 3
29 31 ok
33 falls to 3 etc.
The odd numbers as a broad class grow with +2 too. Primes are just a special subclass of that so they always do that too. They are just the subclass that grow that way and that are not divisible by smaller primes.
So the program should keep running.