 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Smallest prime of the form a^2^m + b^2^m, m>=14 (https://www.mersenneforum.org/showthread.php?t=23160)

 JeppeSN 2018-03-24 14:19

[QUOTE=science_man_88;483253]. Not really, it happens any time both bases are squares.[/QUOTE]

Of course, but I conjecture this is the only instance where, for a given [$]n[/$], the [I]smallest[/I] 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 2018-03-24 14:49

[QUOTE=JeppeSN;483252]For both a and b odd, the first primes are (as others already found but did not post):

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

Sheesh, I don't know HOW I messed that one up. I had posted [url=http://www.mersenneforum.org/showpost.php?p=482841&postcount=63]here[/url] (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 2018-03-24 17:04

[QUOTE=JeppeSN;483260]Of course, but I conjecture this is the only instance where, for a given [$]n[/$], the [I]smallest[/I] prime of form [$]F_n'(a,b)=\frac{a^{2^n}+b^{2^n}}{2}[/$] has [$]a[/$] and [$]b[/$] both perfect squares. /JeppeSN[/QUOTE]
Not necessarily. It is the other way around - if the hit for the F[SUB]n+1[/SUB](a,b) happens very early, then it will decide the fate of the minimum in F[SUB]n[/SUB](a[SUP]2[/SUP],b[SUP]2[/SUP]).

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

 Dr Sardonicus 2018-03-24 17:37

[QUOTE=Batalov;483280]Not necessarily. It is the other way around - if the hit for the F[SUB]n+1[/SUB](a,b) happens very early, then it will decide the fate of the minimum in F[SUB]n[/SUB](a[SUP]2[/SUP],b[SUP]2[/SUP]).

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

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 [i]both[/i] being squares out of hand.

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

 science_man_88 2018-03-24 18:08

[QUOTE=Dr Sardonicus;483283]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 [i]both[/i] being squares out of hand.

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

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

 JeppeSN 2018-03-24 21:31

[QUOTE=Dr Sardonicus;483269]Sheesh, I don't know HOW I messed that one up. I had posted [url=http://www.mersenneforum.org/showpost.php?p=482841&postcount=63]here[/url] (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.[/QUOTE]

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

In the search for the next one, I find:

[CODE](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)[/CODE]

/JeppeSN

 JeppeSN 2018-03-24 21:42

[QUOTE=Batalov;483280]Not necessarily. It is the other way around - if the hit for the F[SUB]n+1[/SUB](a,b) happens very early, then it will decide the fate of the minimum in F[SUB]n[/SUB](a[SUP]2[/SUP],b[SUP]2[/SUP]).

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

Yes, also interesting. I could be wrong, of course. With [I]two[/I] "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 2018-03-24 21:56

[QUOTE=JeppeSN;483297]Apparently I forgot your post. Sorry. I agree on exponent 2^11.

In the search for the next one, I find:

[CODE](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)[/CODE]

/JeppeSN[/QUOTE]

[B]EDIT[/B] The below numbers are not primes. PFGW picks an "unlucky" base:

And then:

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

EDIT: And again:

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

And:

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

So easy(?):

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

/JeppeSN

 Batalov 2018-03-24 23:03

Use base 2, obviously

 JeppeSN 2018-03-25 06:38

[QUOTE=JeppeSN;483297]Apparently I forgot your post. Sorry. I agree on exponent 2^11.

In the search for the next one, I find:

[CODE](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)[/CODE]

/JeppeSN[/QUOTE]

For exponent 2^13, we have:

[CODE](107^(2^13)+69^(2^13))/2[/CODE]

/JeppeSN

 Dr Sardonicus 2018-03-25 16:00

[QUOTE=JeppeSN;483302][B]EDIT[/B] The below numbers are not primes. PFGW picks an "unlucky" base:

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

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

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

[CODE](3^(2^16)+1^(2^16))/2 is 3-PRP! (57.7878s+24.4478s)[/CODE]
[/QUOTE]
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.)

All times are UTC. The time now is 12:56.