 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)

 paulunderwood 2018-03-15 17:26

[QUOTE=JeppeSN;482422]

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

/JeppeSN[/QUOTE]

Are you computing with PFGW :question:

Edit:

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

[CODE]cat Jeppe.abc2
ABC2 \$a^16384+\$b^16384
a: from 2 to 50 step 2
b: from 3 to 50 step 2
[/CODE]
[CODE]./pfgw64 -f -N Jeppe.abc2[/CODE]

 science_man_88 2018-03-15 19:00

[QUOTE=JeppeSN;482422]Me:

To be explicit, this is what brute force finds:

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

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

/JeppeSN[/QUOTE]
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 2018-03-16 06:18

[QUOTE=paulunderwood;482426]Are you computing with PFGW :question:
[/QUOTE]
See [URL="https://oeis.org/A291944"]A291944 in OEIS[/URL]; it is not public yet, so see its history.

I used PARI/GP [FONT="Fixedsys"]ispseudoprime[/FONT] 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 2018-03-16 08:30

[QUOTE=JeppeSN;482473]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.[/QUOTE]

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 2018-03-16 10:33

[QUOTE=axn;482479]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.[/QUOTE]

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

 JeppeSN 2018-03-16 10:36

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 2018-03-16 12:19

[QUOTE=axn;482479]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.[/QUOTE]

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 2018-03-16 13:15

[QUOTE=ATH;482490]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.[/quote]
Cool. But a custom sieve will be much more efficient. Hopefully that will be useful for >= 15.

[QUOTE=ATH;482490]I'm running pfgw while continuing to trial factor. So far no PRP in 2<=b<=16 and b<a<=1000.[/QUOTE]
Since the objective is to find the smallest, you should test in a different order.

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

 a1call 2018-03-16 13:51

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.:smile:

 JeppeSN 2018-03-16 13:53

[QUOTE=axn;482493]Since the objective is to find the smallest, you should test in a different order.[/QUOTE]

I was about to say just that. If the (a,b) space is visualized as this triangle:
[CODE]
(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)
. .
. .
. .
[/CODE]
it is best to search from the top and down, not from left to right.

/JeppeSN

 axn 2018-03-16 14:21

[QUOTE=axn;482493]But a custom sieve will be much more efficient.[/QUOTE]

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.

All times are UTC. The time now is 13:29.