Close

Heuristic breakthrough

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

yann-guidon-ygdesYann Guidon / YGDES 04/25/2023 at 12:150 Comments

I just had to follow the leads and trust my intuition.

I had noticed that the last digits of the gPEAC moduli had a strange behaviour but I only dared to dig the matter these last days and oh boy was it worth it.

I had already noticed that maximal and perfect orbits had a modulus that excluded 2 and 7 as the last decimal digit so there is some mod5 shenanigan. I separated the maximal and the perfect moduli, using the scan up to 131540. I removed the first hundred (or so) entries to prevent side effects. And I made the computer crunch the numbers : examining which remainders existed (or not) when the modulus is reduced to a given base.

First discovery : the maximal and perfect moduli differ only by one parameter.

Perfect moduli mod 4 are always 2, while maximal ones are 0, 1 or 3 mod 4.

This explains why the count ratio between perfect and maximal orbits is about 2.5 : (0,1,3) / (2)

The 0.5 is due to other, further sieving with further primes.

moduli mod 5 exclude 2. A lot of candidates fail already and this explains why you can't find a modulus ending in 2 or 7. So a previous heuristic is confirmed.

Then I pushed further with other prime factors : primes ending with the decimal digit 3 and 7 are not sieving criteria !

So what remains are primes with 1 and 9 suffixes.

* base=11 : exclude 3 & 7 (coincidence ?)
* base=19 : exclude 4 & 14
* base=29 : exclude 5 & 23
* base=31 : exclude 12 & 18
* base=41 : exclude 6 & 34
* base=59 : exclude 25 & 33
* base=61 : exclude 17 & 43
* base=71 : exclude 8 & 62
* base=79 : exclude 29 & 49
* base=89 : exclude 9 & 79
* base=101 : exclude 22 & 78
* base=109 : exclude 10 & 98
* base=131 : exclude 11 & 119

Notice that the 2 sieving numbers N1 and N2 are such that base=N1+N2+1.

So yes now we have a more precise picture of the sieving that occurs at higher and higher moduli.

I'd like to expand this list but I need more computing power, for example to push to 1 million orbits. That will come later, as the above list already catches a LOT of candidates.

 1 2  perfect
 2 4  maximal
 3 8  maximal
 4 16  maximal
 5 32  %5=2
 6 64  (?)
 7 128  %11=7, %19=14
 8 256  %11=3
 9 512  %5=2
10 1024 maximal
11 2048  (?)
12 4096  %59=25
13 8192  %5=2
14 16384   %101=22
15 32768  (?)
16 65536 maximal
17 131072  %10=2, %11=7, %59=33
18 262144  %11=3
19 524288  (?)
20 1048576  %29=23
21 2097152  %5=2
22 4194308  (?)
23 8388608  (?)
24 16777216  (?)
25 33554432  %5=2, %19=14
26 67108864  perfect
27 134217728  %11=7
28 268435456  %11=3
29 536870912   %5=2
30 1073741824  (?)
31 2147483648  (?)
32 4294967296  (?)
33 8589934592   %5=2
34 17179869184  (?)

(note: base 5 appears every 4 line so there is a cyclic structure at play and a clear sieve)

Only bases up to 131 have been considered so some candidates may be invalid or more bases invalidate the candidate, but with 15 bases to sieve, there are already a big proportion that is eliminated.

sqrt(2^33) =         92681  %4=1
sqrt(2^35) =        185363  %4=3, %79=29
sqrt(2^37) =        370727  %5=2
sqrt(2^39) =        741455  %4=3
sqrt(2^41) =       1482910   (?)
sqrt(2^43) =       2965820  %71=8
sqrt(2^45) =       5931641  %4=1
sqrt(2^47) =      11863283  %11=3
sqrt(2^49) =      23726566   (?)
sqrt(2^51) =      47453132  %5=2
sqrt(2^53) =      94906265  %11=3
sqrt(2^55) =     189812531  %19=4
sqrt(2^57) =     379625062  %11=3
sqrt(2^59) =     759250124   (?)
sqrt(2^61) =    1518500249  %61=43
sqrt(2^63) =    3037000499  %109=98
sqrt(2^65) =    6074000999  %41=34
sqrt(2^67) =   12148001999  %4=3
sqrt(2^69) =   24296003999  %11=3
sqrt(2^71) =   48592007999  %19=4
sqrt(2^73) =   97184015999  %4=3
sqrt(2^75) =  194368031998  %89=79
sqrt(2^77) =  388736063996   (?)
sqrt(2^79) =  777472127993  %71=62
sqrt(2^81) = 1554944255987  %5=2, %19=14

More bases should be tested but this also helps with scanning because we can eliminate many invalid candidates easily now.

Discussions