I am researching a very weird anomaly.

From [URL]https://oeis.org/A275530[/URL] inquiring minds can find out that a(15) > 10,000.
Or in other words, there are no small prps of the GFN' form [B](a^32768+1)/2[/B].

Now, from what I checked with PFGW, a(15) appears to be either > 160,000 (or even >200,000, which is unreasonably high), or there is a bug in libgwnum. I checked with pfgw, llr, p95 but the speed and results are similar (and the underlying lib is the same). All programs chose the special FFT of size 32K. Changing FFT size to a larger one doesn't help to find a PRP yet. Very strange.

[QUOTE=Batalov;483733]I am researching a very weird anomaly.

From [URL]https://oeis.org/A275530[/URL] inquiring minds can find out that a(15) > 10,000.
Or in other words, there are no small prps of the GFN' form [B](a^32768+1)/2[/B].

Now, from what I checked with PFGW, a(15) appears to be either > 160,000 (or even >200,000, which is unreasonably high), or there is a bug in libgwnum. I checked with pfgw, llr, p95 but the speed and results are similar (and the underlying lib is the same). All programs chose the special FFT of size 32K. Changing FFT size to a larger one doesn't help to find a PRP yet. Very strange.[/QUOTE]
Well, the main one ([url]http://oeis.org/A226530[/url]) has first three as 70906, 167176, 204462. So > 200k, while low probability, is not _that_ unexpected.

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=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.

[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.

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.

[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

[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

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

How are you sieving these suckers?

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.

[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

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=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]

[QUOTE=axn;483415][CODE](3^2+1^2)/2
(3^4+1^4)/2
(5^8+3^8)/2
(3^16+1^16)/2
(3^32+1^32)/2
(3^64+1^64)/2
(179^128+177^128)/2
(169^256+167^256)/2
(935^512+933^512)/2
(663^1024+661^1024)/2[/CODE][/QUOTE]

Submitted as [URL="https://oeis.org/A302387"]A302387[/URL] (not approved yet). /JeppeSN

[QUOTE=Batalov;482574]Aw well, m=16 was too easy. Even a pair for the good measure:
124^65536+57^65536
143^65536+106^65536[/QUOTE]

I just discovered these are duplicates at the PRP Top site. If you [URL="http://www.primenumbers.net/prptop/searchform.php?form=x%5E%282%5E16%29%2By%5E%282%5E16%29&action=Search"]search for x^(2^16)+y^(2^16)[/URL], the same two numbers were found by Valeryi Kuryshev in Feb 2011.

/JeppeSN

Yes, there are many more; I've seen duplicates in other classes before. (Because there are similarly different ways to write values, e.g. using Phi(), or gcd() ... for primitive parts or Aurifeuillean parts. PRP owners [I]should better have[/I] an in-take evaluator and checker.

The bracketed form is hard to search for. You can use "x^?+y^?" and then filter, but that's not the first form that comes to mind.

OK. And still no trace of [URL="https://oeis.org/A291944"]A291944[/URL](17), the smallest PRP of form xGF(17, a, b) = a^131072 + b^131072. /JeppeSN

How far did anybody search?