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

[Batalov]

Were these the droids you were looking for?
216^16384+109^16384

[JeppeSN]

Originally Posted by Batalov

Were these the droids you were looking for?
216^16384+109^16384

Yes! And is it certain that 216^16384+109^16384 is minimal?

Did you search and find this now, or was it something that was known (to you) in advance?

Of course, now I want then minimal odd prime a^(2^m)+b^(2^m) for all the next m values

/JeppeSN

[paulunderwood]

Originally Posted by Batalov

Were these the droids you were looking for?
216^16384+109^16384

For added confidence in Serge's result:

time ./pfgw64 -k -f0 -od -q"216^16384+109^16384" | ../../coding/gwnum/hybrid -
                              
Testing (x + 1)^(n + 1) == 2 + 3 (mod n, x^2 - 3*x + 1)...
Likely prime!

real	1m45.793s
user	2m36.120s
sys	0m55.244s

[Dr Sardonicus]

If one wanted to check exponents 2^m for several values of m, one might want to compile a table of pairs (a,b) with a < b, b <= N (given upper bound), gcd(a, b) = 1, and a + b odd. This isn't entirely trivial. And I'm quite poor at this sort of thing.

Without the condition that a + b be odd, it would be equivalent to calculating the Farey sequence of order N. Perhaps the way to go is to calculate the Farey sequence, and then skip pairs where a and b are both odd.

One idea I considered by rejected was, for even b, find the positive integers r < b with gcd(r, b) = 1, then fill in the entries (b, r + k*b) with r + k*b not exceeding N. Alas, you would have to make sure, for each r, that the multiplier k was relatively prime to r...

Of course, viewing table computation as a preliminary calculation, it probably makes little difference how clumsily it is compiled, if N isn't very big. For large exponents, the value of b will be a good indicator of the size of a^(2^m) + b^(2^m)

The idea of sieving out multiples of "small" primes p congruent to 1 (mod 2^(m+1)) makes sense. Each pair (a, b) sieved out as giving a multiple of p means you can skip a PRP test. I looked at the primes p congruent to 1 (mod 2^15) up to the limit 50 million. There are 174 such primes. Grasping at straws(*), I computed the product (1 - 2^14/p) over these primes, and got .507+ which would be great if it meant eliminating almost half the pairs (a, b) actually under consideration.

(*) I reckoned that the relevant thing here was the 2^14 solutions to Mod(r,p)^(2^14) + 1 = Mod(0,p). Each pair (Mod(a,p), Mod(r, p)*Mod(a,p)) gives a multiple of p. This ignores the question of which such pairs might reduce to pairs of small coprime integers (a, b) of different parity. But hey -- any PRP test you can skip cheaply is to the good, right?

I did a quick check of the idea with the exponent 16. I looked at the smallest prime (p = 97) congruent to 1 (mod 32), and easily found from the root Mod(19,97) to

x^16 + 1 = Mod(0,97)

that 5^16 + 2^16 is a multiple of 97.

[Batalov]

Originally Posted by JeppeSN

Yes! And is it certain that 216^16384+109^16384 is minimal?

Did you search and find this now, or was it something that was known (to you) in advance?

Of course, now I want then minimal odd prime a^(2^m)+b^(2^m) for all the next m values

/JeppeSN

It is minimal.
What puzzles me is why is this taking others so long to find the same? It only took overnight on 8 cores. The workflow is very simple: generate (a,b)s in 1 second with a trivial Pari script (opposite parity, gcd > 1, say, up to a<=400), then split into a few workfiles (hawever many cores you have) and run pfgw -f"{65536}" -N -k -l input on each chunk, periodically check, ..., done!

For m=15, it is perhaps best to sieve, but for m=14, this -f parameter takes care of the small factors just well enough.

[ATH]

It is just a question of resources. For this random question I only used 1 core for sieving and 1 core for pfgw, I had no need to use more, rest is running Prime95 on this machine, it is not like we had to find the answer within a certain time limit.

I only tried briefly using pfgw for trial factoring long ago, and my impression was it was horribly slow at it, so I have not tried again, I might try next time I need it.


Edit: and yes I should have sorted the list so it ran pfgw on candidates by size, but I made this quick program last night before I went to bed, and I only got 4-5 hours of sleep before work.

[axn]

Originally Posted by Batalov

run pfgw -f"{65536}" -N -k -l input on each chunk, periodically check, ..., done!

The should be f{32768}. You will miss a prolific factor 10*16384+1

[Batalov]

A typo, this command-line is already prepared for m=15. :-)

[science_man_88]

Technically if a and b are squares you find one for the next level up as well.

[CRGreathouse]

Originally Posted by science_man_88

Technically if a and b are squares you find one for the next level up as well.

Yes, but 216 and 109 aren't (though the former is a cube).

[Batalov]

Another droid crossed my path. 260^32768+179^32768
Not proven minimal yet, though.