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

[paulunderwood]

Originally Posted by JeppeSN

The next line takes more time. The question is: Hasn't this been considered before?!

/JeppeSN

Are you computing with PFGW

Edit:

I ran PFGW for bases less than or equal to 50 and found no PRP:

cat Jeppe.abc2 
ABC2 $a^16384+$b^16384
a: from 2 to 50 step 2
b: from 3 to 50 step 2

./pfgw64 -f -N Jeppe.abc2

[science_man_88]

Originally Posted by JeppeSN

Me:

To be explicit, this is what brute force finds:

m=0,  2^1 + 1^1
m=1,  2^2 + 1^2
m=2,  2^4 + 1^4
m=3,  2^8 + 1^8
m=4,  2^16 + 1^16
m=5,  9^32 + 8^32
m=6,  11^64 + 8^64
m=7,  27^128 + 20^128
m=8,  14^256 + 5^256
m=9,  13^512 + 2^512
m=10, 47^1024 + 26^1024
m=11, 22^2048 + 3^2048
m=12, 53^4096 + 2^4096
m=13, 72^8192 + 43^8192

The next line takes more time. The question is: Hasn't this been considered before?!

/JeppeSN

Probably has, think modular tricks like fermats little theorem and extentions. Mod 8 it becomes a^0+b^0 for example, mod 9 it's a^4+b^4 these work for all bases coprime to 8 or 9 respectively.

[JeppeSN]

Originally Posted by paulunderwood

Are you computing with PFGW

See A291944 in OEIS; it is not public yet, so see its history.

I used PARI/GP ispseudoprime in a loop, like the code shown there, and I suspect Robert G. Wilson v used Mathematica. Maybe PFGW is faster?

There is no point in all of us running the same tests, except whoever uses the best tools will "win" the competition. I just thought maybe this had been established already.

/JeppeSN

[axn]

Originally Posted by JeppeSN

There is no point in all of us running the same tests, except whoever uses the best tools will "win" the competition. I just thought maybe this had been established already.

I will try to write a custom sieve during the weekend. After that I can post the sieve output here, so that interested people can test ranges.

PFGW should indeed be faster than Pari or Mathematica.

EDIT:- Testing 71^16384+46^16384, PFGW took about 20s, while Pari took 2mins and change. So PFGW is about 6x faster.

[paulunderwood]

Originally Posted by axn

I will try to write a custom sieve during the weekend. After that I can post the sieve output here, so that interested people can test ranges.

PFGW should indeed be faster than Pari or Mathematica.

EDIT:- Testing 71^16384+46^16384, PFGW took about 20s, while Pari took 2mins and change. So PFGW is about 6x faster.

PFGW will be more than 6x faster with much bigger numbers

[JeppeSN]

Something to note:

Use here the convention \(a > b > 0\). There is a slight chance that the smallest odd prime \(a^{16384}+b^{16384}\) does not minimize \(a\).

As an example, \(677 < 678\), but still \(677^{128}+670^{128} > 678^{128}+97^{128}\) (both of these sums of like powers are prime).

However, for the smallest one with that exponent, \(27^{128}+20^{128}\), the value \(a=27\) is also minimal. And I think this will be the case generally, because the bases \(a\) and \(b\) will be relatively small (I conjecture). But we will check for that with 16384 once axn's excellent initiative has come to fruition.

/JeppeSN

[ATH]

Originally Posted by axn

I will try to write a custom sieve during the weekend. After that I can post the sieve output here, so that interested people can test ranges.

PFGW should indeed be faster than Pari or Mathematica.

EDIT:- Testing 71^16384+46^16384, PFGW took about 20s, while Pari took 2mins and change. So PFGW is about 6x faster.

I'm already working on a<b<=1000, or b<a<=1000 which ever convention you use

I used fbncsieve to sieve the factors k*2^14+1. It took only ~2min up to k=10^9.

Then I used these prime factors in a quickly written GMP program to sieve an array 1000x1000 of a,b. First I removed all values where b>=a, a<2, b<2, a%2=b%2 (both odd or both even), and gcd(a,b)>1. Down to 61K candidates at k=462M.

I'm running pfgw while continuing to trial factor. So far no PRP in 2<=b<=16 and b<a<=1000.

[axn]

Originally Posted by ATH

I'm already working on a<b<=1000, or b<a<=1000 which ever convention you use

I used fbncsieve to sieve the factors k*2^14+1. It took only ~2min up to k=10^9.

Then I used these prime factors in a quickly written GMP program to sieve an array 1000x1000 of a,b. First I removed all values where b>=a, a<2, b<2, a%2=b%2 (both odd or both even), and gcd(a,b)>1. Down to 61K candidates at k=462M.

Cool. But a custom sieve will be much more efficient. Hopefully that will be useful for >= 15.

Originally Posted by ATH

I'm running pfgw while continuing to trial factor. So far no PRP in 2<=b<=16 and b<a<=1000.

Since the objective is to find the smallest, you should test in a different order.

2<=a<=1000, 1<=b<a

[a1call]

Stating the obvious for the sake of having it stated

a+b | a^q + b^q for all odd q

And

a+bi | a^q + b^q for all even q

So the result will be definitely not prime over the imaginary field.

Corrections are welcome.

[JeppeSN]

Originally Posted by axn

Since the objective is to find the smallest, you should test in a different order.

I was about to say just that. If the (a,b) space is visualized as this triangle:

(2,1)
      (3,2)
(4,1)       (4,3)
      (5,2)       (5,4)
(6,1)       (6,3)       (6,5)
      (7,2)       (7,4)       (7,6)
(8,1)       (8,3)       (8,5)       (8,7)
.                                          .
.                                                .
.                                                      .

it is best to search from the top and down, not from left to right.

/JeppeSN

[axn]

Originally Posted by axn

But a custom sieve will be much more efficient.

That was somewhat presumptuous of me. What is the rate at which your sieve is progressing thru the factor candidates?

If you can post your sieve source, I can use that as a starting point.