Verification, generation code
This is golfing down the excellent solution of Max Kubierschky, who said they will no longer spend time updating their answer. See their answer for an explanation of the strategy. The formula here is largely the same, but was shortened by removing repetition and introducing cancellations.
The main improvement is the arithmetic formula used to branch on a condition:
if b1: t1
Previously, this was done as
b1*t1+(1-b1)*t2. This meant the condition
b1 needed to be repeated twice, which was costly because the condition of Fermat-primality used a relatively long formula.
We instead regroup
b1*(t1-t2)+t2. Instead of repeating the condition
b1, we repeat the output
t2. So, we arrange to make `t2 be short.
As used, one of the branches just gives a number (the successfully found prime), which the other branches into further conditions to continue the search.
if b1: t1
if b2: t2
if b3: t3
Our method has the no-result
t2 repeated twice rather than
t1, but we can fix this by negating the condition
b2 so that we can interchange
We make it so that the twice-repeated
t1 is just a number, while the once-repeated
t2 is the long branch. We do this by negative the condition
b to checking non-primality rather than primality. This is done by replacing the
1/stuff check for
stuff==1 to instead be
stuff!=1 (in both cases, we know
Doing this recursive expansion, we further find that it has terms like
t1-t2 that subtract two potential outputs. These can be simplified. Because each possible output has form
30*n+d, we can cancel like
(30*n+17)-(30*n+23)==-6, saving many instances of writing
We use a variation of an idea suggested by Arnauld to fix the faulty cases in a shorter way, using 32 characters not counting parens.
There are four non-prime outputs, and a brute-force search finds that adding
702 to each one makes them prime and distinct from all other outputs. We use an indicator function of being in those four cases, and adding
702 times that indicator. The indication function uses
0^ to check
==0 for a product of
n-k for each failed input
k. (If we can't rely on
0^0==1, we can use
1/(1+_) as a slightly longer alternative for ``0^_`.)
Other potential approaches might hide errors in a more efficient way by adaptively adjusting the numbers checked and the base of the pseudoprime, as suggested by in comments by Max Kubierschky.
This includes some hand-found optimizations. First, the faulty cases are checked in a shorter way found by Sisyphus, as
0^(n%941%654%523%360). This evaluates to
1 exactly for the exceptional inputs
360, 523, 654, 941 and zero otherwise. This mod chain works because each value happens to be less than double the previous one, including if we append
1000 to the end.
Other misc fixes uses that some values could be written shorter in base 10. Some of the expressions within the primality checks like
2^(n*30+16) could be shortened like
4^(n*15+8). The various difference values were all even and could be written halved with a
*2 later. A
+stuff*(-18) was changed to