mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Smallest prime of the form a^2^m + b^2^m, m>=14 (https://www.mersenneforum.org/showthread.php?t=23160)

 Batalov 2018-03-29 14:35

Perhaps, so. I was concerned that there may be some giant_mod bug or a carry count bug similar to one a few years ago.

Anyway, found one ... at a(15) = 220221 (!!)

 Dr Sardonicus 2018-03-29 14:53

[QUOTE=Batalov;483757]Perhaps, so. I was concerned that there may be some giant_mod bug or a carry count bug similar to one a few years ago.

Anyway, found one ... at a(15) = 220221 (!!)[/QUOTE]

Congratulations!

How many candidates for a(15) were sieved out?

BTW, it's another "interesting anomaly" that

a(4) = a(3)^2 and a(14) = a(13)^2.

 axn 2018-03-29 16:11

[QUOTE=Batalov;483757]Perhaps, so. I was concerned that there may be some giant_mod bug or a carry count bug similar to one a few years ago.

Anyway, found one ... at a(15) = 220221 (!!)[/QUOTE]

Hmmm... Unfortunately, we can't really rule out s/w issues with regular double check. BTW, does LLR, P95 & PFGW produce comparable residues on these type of numbers?. Perhaps a Gerbicz Error Check implementation for non base-2 PRP could be made. It will be much slower (50%?) but atleast could be used to spot check.

 Batalov 2018-03-29 19:32

Here is my eval of what usually happens in all three tools.
This is a special form. In LLR there is an input ABC template [c]ABC (\$a*\$b^\$c\$d)/\$e[/c]; in P95, [c]PRP=1,b,n,1,"2"[/c], and PFGW understands the ABC form as well as recognizes the special form at parse stage.

All three tools have adapted over time to do the following on it:[LIST][*]the main exponentiation loop is done over mod (b^n+1) (not general mod! therefore, fast!)[*]the last residue is folded mod (b^n+1)/e and compared to 1 (this is done using giants)[/LIST]
I am tempted to modify the source for this special case e=2, because giant mod is not needed, just compare two values (1 or (b^n+1)/2+1 -these should look just fine in limbs of b how they are likely internally stored) -- (or multiply by 2 and compare to 2). ...Thus avoiding giants.

Another test that I did in limited range: use [c]-a1, -a2[/c] in pfgw (or similar in other tools); this is not a little bit, but a lot slower, because the special arrangement of exactly 32K b-limbs is destroyed.

Let's see what happens. I'll tinker with this on the weekends.

 JeppeSN 2018-03-29 23:49

[QUOTE=JeppeSN;483411]To appear as [URL="https://oeis.org/A301738"]A301738[/URL] (until it is approved, see History to see the proposed versions). /JeppeSN[/QUOTE]

Now approved.

I will contribute the new sequence quite soon.

Serge Batalov, good work on A275530.

/JeppeSN

 Batalov 2018-03-31 02:05

[QUOTE=Batalov;483757]Perhaps, so. I was concerned that there may be some giant_mod bug or a carry count bug similar to one a few years ago.

Anyway, found one ... at a(15) = 220221 (!!)[/QUOTE]
Found a(16), too

 axn 2018-03-31 03:03

[QUOTE=Batalov;483847]Found a(16), too[/QUOTE]

How are you sieving these suckers?

 Batalov 2018-03-31 04:35

These are too small to sieve, -- PFGW's ~45-bit pre-factoring looks fine to me.
It would be a different story for m=17, but I am taking a break for now.

 Dr Sardonicus 2018-03-31 13:15

[QUOTE=Dr Sardonicus;483759]Congratulations!
BTW, it's another "interesting anomaly" that

a(4) = a(3)^2 and a(14) = a(13)^2.[/QUOTE]
!sdrawkcab ti tog I ,tibbangaD

I should have said, a(13) = a(14)^2 and a(3) = a(4)^2

 Batalov 2018-04-01 17:07

And [URL="https://oeis.org/A275530"]A275530[/URL](17) is now found!

(11559^131072+1)/2 is a 532535-digit PRP.

[SPOILER]Now it is time to revisit the a(15) with a different FFT size throughout.[/SPOILER]

 paulunderwood 2018-04-01 17:51

[QUOTE=Batalov;483940]And [URL="https://oeis.org/A275530"]A275530[/URL](17) is now found!

(11559^131072+1)/2 is a 532535-digit PRP.

[SPOILER]Now it is time to revisit the a(15) with a different FFT size throughout.[/SPOILER][/QUOTE]

Congrats Serge. Here is my Lucas test of it:

[CODE]time ./pfgw64 -k -f0 -od -q"(11559^131072+1)/2" | ../../coding/gwnum/lucasPRP - 1 11559 131072 1

Lucas testing on x^2 - 4*x + 1 ...
Is Lucas PRP!

real 20m21.514s
user 48m14.480s
sys 3m17.668s[/CODE]

All times are UTC. The time now is 12:25.