mersenneforum.org

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 20:21.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.