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

[JeppeSN]

Originally Posted by science_man_88

. Not really, it happens any time both bases are squares.

Of course, but I conjecture this is the only instance where, for a given \(n\), the smallest prime of form \(F_n'(a,b)=\frac{a^{2^n}+b^{2^n}}{2}\) has \(a\) and \(b\) both perfect squares. /JeppeSN

[Dr Sardonicus]

Originally Posted by JeppeSN

For both a and b odd, the first primes are (as others already found but did not post):

[snip]
(5^8+3^8)/2
[snip]
(67^1024+57^1024)/2

Sheesh, I don't know HOW I messed that one up. I had posted here (1^8 + 9^8)/2. But (3^8 + 5^8)/2 is correct.

I also posted, for e = 2^11, n = (49^e + 75^e)/2.

[Batalov]

Originally Posted by JeppeSN

Of course, but I conjecture this is the only instance where, for a given \(n\), the smallest prime of form \(F_n'(a,b)=\frac{a^{2^n}+b^{2^n}}{2}\) has \(a\) and \(b\) both perfect squares. /JeppeSN

Not necessarily. It is the other way around - if the hit for the F_n+1(a,b) happens very early, then it will decide the fate of the minimum in F_n(a²,b²).

Here, in sequence https://oeis.org/A246119, the same happened three time already.

[Dr Sardonicus]

Originally Posted by Batalov

Not necessarily. It is the other way around - if the hit for the F_n+1(a,b) happens very early, then it will decide the fate of the minimum in F_n(a²,b²).

Here, in sequence https://oeis.org/A246119, the same happened three time already.

Squares are rare, so if either a or b is a square it is worthy of note. And, lo and behold, for m = 11 (though my results should be checked), one of the numbers (49, 75) is a square. So I wouldn't dismiss the possibility of another instance of both being squares out of hand.

Alas, the number of cases any of us will ever know of is, likely, quite small.

[science_man_88]

Originally Posted by Dr Sardonicus

Squares are rare, so if either a or b is a square it is worthy of note. And, lo and behold, for m = 11 (though my results should be checked), one of the numbers (49, 75) is a square. So I wouldn't dismiss the possibility of another instance of both being squares out of hand.

Alas, the number of cases any of us will ever know of is, likely, quite small.

They are more common, than the solutions to the next stage up... I think you mean minimal ones are of note.

[JeppeSN]

Originally Posted by Dr Sardonicus

Sheesh, I don't know HOW I messed that one up. I had posted here (1^8 + 9^8)/2. But (3^8 + 5^8)/2 is correct.

I also posted, for e = 2^11, n = (49^e + 75^e)/2.

Apparently I forgot your post. Sorry. I agree on exponent 2^11.

In the search for the next one, I find:

(157^(2^12)+83^(2^12))/2 is 3-PRP! (4.1038s+1.9638s)
(157^(2^12)+111^(2^12))/2 is 3-PRP! (4.0938s+3.3192s)
(161^(2^12)+157^(2^12))/2 is 3-PRP! (4.1053s+1.9778s)

/JeppeSN

[JeppeSN]

Originally Posted by Batalov

Not necessarily. It is the other way around - if the hit for the F_n+1(a,b) happens very early, then it will decide the fate of the minimum in F_n(a²,b²).

Here, in sequence https://oeis.org/A246119, the same happened three time already.

Yes, also interesting. I could be wrong, of course. With two "free parameters" \(a,b\) in \(F_n'(a,b)\) is it likely to occur again for \(n>11\)? I do not think so.

The form in A246119, \(k^{2^n} (k^{2^n}-1)+1\), has only one parameter \(k\). I still think this square phenomenon should occur only finitely many times?

/JeppeSN

[JeppeSN]

Originally Posted by JeppeSN

Apparently I forgot your post. Sorry. I agree on exponent 2^11.

In the search for the next one, I find:

(157^(2^12)+83^(2^12))/2 is 3-PRP! (4.1038s+1.9638s)
(157^(2^12)+111^(2^12))/2 is 3-PRP! (4.0938s+3.3192s)
(161^(2^12)+157^(2^12))/2 is 3-PRP! (4.1053s+1.9778s)

/JeppeSN

EDIT The below numbers are not primes. PFGW picks an "unlucky" base:

And then:

(3^(2^13)+1^(2^13))/2 is 3-PRP! (0.6454s+0.4075s)

EDIT: And again:

(3^(2^14)+1^(2^14))/2 is 3-PRP! (2.8285s+1.3930s)

And:

(9^(2^15)+1^(2^15))/2 is 3-PRP! (57.8865s+21.0036s)

So easy(?):

(3^(2^16)+1^(2^16))/2 is 3-PRP! (57.7878s+24.4478s)

/JeppeSN

[Batalov]

Use base 2, obviously

[JeppeSN]

Originally Posted by JeppeSN

Apparently I forgot your post. Sorry. I agree on exponent 2^11.

In the search for the next one, I find:

(157^(2^12)+83^(2^12))/2 is 3-PRP! (4.1038s+1.9638s)
(157^(2^12)+111^(2^12))/2 is 3-PRP! (4.0938s+3.3192s)
(161^(2^12)+157^(2^12))/2 is 3-PRP! (4.1053s+1.9778s)

/JeppeSN

For exponent 2^13, we have:

(107^(2^13)+69^(2^13))/2

/JeppeSN

[Dr Sardonicus]

Originally Posted by JeppeSN

EDIT The below numbers are not primes. PFGW picks an "unlucky" base:

(3^(2^13)+1^(2^13))/2 is 3-PRP! (0.6454s+0.4075s)

(3^(2^14)+1^(2^14))/2 is 3-PRP! (2.8285s+1.3930s)

(9^(2^15)+1^(2^15))/2 is 3-PRP! (57.8865s+21.0036s)

(3^(2^16)+1^(2^16))/2 is 3-PRP! (57.7878s+24.4478s)

Hardly surprising. We have

3^2 == 1 (mod 2^3). Therefore,

3^(2^k) == 1 (mod 2^(k+2)) for every positive integer k.

Now, let k be a positive integer, and N = (3^(2^k) + 1)/2. Then N - 1 = (3^(2^k) - 1)/2. By the above, we have

2^(k+1) divides N - 1, so

3^(2^(k+1)) - 1 divides 3^(N - 1) - 1. Since

3^(2^(k+1)) - 1 = (3^(2^k) - 1)*(3^(2^k) + 1), and (3^(2^k) + 1)/2 = N, we have

N divides 3^(N-1) - 1. That is, N = 3^(2^k) + 1 is a base-3 pseudoprime for every positive integer k.

I haven't checked the Rabin-Miller criterion in this case, though.

(The present instance is reminiscent of the fact that, if p is prime, 2^p - 1 is a base-2 pseudoprime, regardless of whether it's prime or composite.)