Smallest prime of the form a^2^m + b^2^m, m>=14

[Batalov]

Originally Posted by a1call

There is not much saving if any, in doing more than one such test.

That's right.
You will spend time better doing trial factoring mod k*2^m+1+1.
You do realize that gcd() is nothing other than a bunch of divisions?

[a1call]

I meant per candidate. Trial by division is very efficient for filtering out candidates with small factors. GCD of the form I suggest can probably knock out a handful of candidates with much larger factors. Any little bit should help when you have very expensive PRP testing to do.

[science_man_88]

Originally Posted by a1call

I meant per candidate. Trial by division is very efficient for filtering out candidates with small factors. GCD of the form I suggest can probably knock out a handful of candidates with much larger factors. Any little bit should help when you have very expensive PRP testing to do.

But k and k' can't be arbitrary, if a and b are opposite parity then a+k has same parity as b+k' if both pairs are opposite parity pairs. If they are both same parity pairs then the whole expression value is even ( as is the previous case as well). So really with the parity check already in place we have done this for mod 2. And the gcd knocks out other factors. It's because additive inverses can't easily be done that we can't really do that much with it.

[a1call]

You need to generate testing pairs which are Mod (1,q) including their odd factors.
Correct me if I wrong but the ks are arbitrary.

For the same of GCD the generated partner does not need to be odd, just appropriately large. Not t0o large to contradict the time saved.
Now I am out to attend the Noruz party.
Will check in later
ETA I think if your for steps generate say odd a and even b then the ks will have to be both odd. The point is they could be any positive or negative odd addends.

[Dr Sardonicus]

For the sieving part, you need, presumably, the primes p == 1 (mod 2*e), e = 2^m, up to some limit. My stick-pokes at the problem indicate that the limit will be much, much larger than that for precomputed tables of primes. So, you have to roll your own. This would be another initial computation. The question is, what's a reasonable limit for a given exponent e = 2^m?

I note that, if you proceed from exponent 2^m to exponent 2^(m+1), you can cull the list of primes p == 1 (mod 2^(m+1)) for at least the first part of your list of primes p == 1 (mod 2^(m+2)); but I'm guessing that the larger the exponent e = 2^m, the higher your limit on primes will be.

Another thing occurs to me: The numbers a^e + b^e being sieved here are, as noted in the OP to this thread, divisible only by primes congruent to 1 (mod 2*e). The number of such numbers less than or equal to X is, asymptotically^*, c*X*log(X)^(1/e - 1); I'm too lazy to work out the value of c. Anyhow, this might affect how well sieving is likely to work.

^*Bateman, Paul T. and Diamond, Harold G. Analytic Number Theory An Introductory Course Theorem 10.1.

Note: The link I posted here to a pdf of the book now, alas, gives the dreaded message "Not Found" (Error 404).

The intrepid web surfer might try here.

[science_man_88]

Originally Posted by a1call

ETA I think if your for steps generate say odd a and even b then the ks will have to be both odd. The point is they could be any positive or negative odd addends.

No, because of mod 3 etc. if you have a and b, both 0 mod 3, then both k's can't be without leading to a number the GCD we already do would eliminate. If a and b are additive inverses mod 3 adding k that are additive inverse pairs causing additive inverse pairs also cause a number gcd would eliminate already.

[Batalov]

Set n = limit of search for a; e = 2^m.

Initialize an array of all eligible pairs (a,b), 0 < b < a <= n, gcd(a,b)=1.
Allocate array uint64_t s[n].

For each prime p == 1 (mod 2*e) up to 63 bits {
    For each small prime q < n { s[q] = q^e by powmod }
    then all composite s[b] as a prod of s[q]
    for each surviving pair of (a,b): remove pair from list if s[a]+s[b] == p
}

Up to 63 bits, the above code will work - even without gmp.
There are multiple existing cuda sieves that could be adapted to the above code.

[Dr Sardonicus]

Originally Posted by Batalov

Set n = limit of search for a; e = 2^m.
[snip]
For each prime p == 1 (mod 2*e) up to 63 bits
[snip]

Hmm, use primes up to 63 bits. I guess "sieve as much as possible" is indeed the way to go. Alas, my computing resources are limited.

Meanwhile, out of curiosity, I looked at pairs (a, b) with a < b, gcd(a, b) = 1, and a and b both odd. Of course, a^e + b^e is even, but with e = 2^m, (a^e + b^e)/2 is odd. The following are the smallest a and b I found for which (a^e +b^e)/2 is a pseudoprime.

With e = 2^3 and e = 2^7, I got an unexpected bonus! At e = 2^12, my Pari script seems to have hit the wall. It will either grind through my set of pairs (a,b) without result, or it will find a pseudoprime. Either way, I'm done with this variant.

e = 2^1: a = 1, b = 3

e = 2^2: a = 1, b = 3

e = 2^3: a = 1, b = 9

e = 2^4: a = 1 , b = 3

e = 2^5: a = 1, b = 3

e = 2^6: a = 1, b = 3

e = 2^7: a = 9, b = 49

e = 2^8: a = 3, b = 7

e = 2^9: a = 9, b = 35

e = 2^10: a = 57, b = 67

e = 2^11: a = 49, b = 75

[Batalov]

The odd b GFNs were kept on a close backburner for many years already:
http://www.prothsearch.com/GFN03.html
http://www.prothsearch.com/GFN05.html
http://www.prothsearch.com/GFN07.html
http://www.prothsearch.com/GFN11.html
All of them are (b^2^n+1)/2. There are some primes there (for b<12) and tons of PRPs, of course.

If you replace b by b/a (with gcd(a.b)=1), the modular divisibility is not changing and intrinsic factor 2 is sticking around. ...There is a 217-digit prime (7^2^8+3^2^8)/2 between small xGFNs.

[Batalov]

Here is an unpolished sieve (and a lazy one - I didin't implement the pseudocode above fully; that is, - I am simply exponentiating all a's). It is really ugly but it works. I am sieving m=17 case to 50-51 bits with this.

( PFGW -f{...} essentially sieves to 44.5-45 bits de facto, so this is a bit of an improvement above simply prefactoring with PFGW. )

[Dr Sardonicus]

Originally Posted by Batalov

[snip] If you replace b by b/a (with gcd(a.b)=1), the modular divisibility is not changing and intrinsic factor 2 is sticking around. ...There is a 217-digit prime (7^2^8+3^2^8)/2 between small xGFNs.

Thanks for the URLs. That b/a trick is nice for the "homogeneous" GFN's, saves a powmod every time while sieving.

Yesirree, (3^256 + 7^256)/2 is indeed prime. I'd checked it using isprime(), since it wasn't so awfully big. Took many times longer than ispseudoprime(), but only seconds, not minutes.

EDIT: I have now checked (9^512 + 35^512)/2 with isprime(), which took minutes. Also prime.

If someone wants to check (57^1024 + 67^1024)/2 and (49^2048 + 75^2048)/2, you're welcome to it. The manual has convinced me that isprime() would take a very long time trying to deal with these.