mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-03-15, 17:26   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D6C16 Posts
Default

Quote:
Originally Posted by JeppeSN View Post

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:

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

Last fiddled with by paulunderwood on 2018-03-15 at 18:24
paulunderwood is offline   Reply With Quote
Old 2018-03-15, 19:00   #13
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
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
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.
science_man_88 is offline   Reply With Quote
Old 2018-03-16, 06:18   #14
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2408 Posts
Smile

Quote:
Originally Posted by paulunderwood View Post
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
JeppeSN is offline   Reply With Quote
Old 2018-03-16, 08:30   #15
axn
 
axn's Avatar
 
Jun 2003

2·13·181 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
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.

Last fiddled with by axn on 2018-03-16 at 08:33
axn is offline   Reply With Quote
Old 2018-03-16, 10:33   #16
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·859 Posts
Default

Quote:
Originally Posted by axn View Post
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
paulunderwood is offline   Reply With Quote
Old 2018-03-16, 10:36   #17
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

25·5 Posts
Wink

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
JeppeSN is offline   Reply With Quote
Old 2018-03-16, 12:19   #18
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

B9516 Posts
Default

Quote:
Originally Posted by axn View Post
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.
ATH is offline   Reply With Quote
Old 2018-03-16, 13:15   #19
axn
 
axn's Avatar
 
Jun 2003

2·13·181 Posts
Default

Quote:
Originally Posted by ATH View Post
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.

Quote:
Originally Posted by ATH View Post
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

Last fiddled with by axn on 2018-03-16 at 13:15
axn is offline   Reply With Quote
Old 2018-03-16, 13:51   #20
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

19·101 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2018-03-16, 13:53   #21
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

25×5 Posts
Default

Quote:
Originally Posted by axn View Post
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:
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)
.                                          .
.                                                .
.                                                      .
it is best to search from the top and down, not from left to right.

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2018-03-16, 14:21   #22
axn
 
axn's Avatar
 
Jun 2003

2×13×181 Posts
Default

Quote:
Originally Posted by axn View Post
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.
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is there a prime of the form...... PawnProver44 Miscellaneous Math 9 2016-03-19 22:11
OEIS A071580: Smallest prime of the form k*a(n-1)*a(n-2)*...*a(1)+1 arbooker And now for something completely different 14 2015-05-22 23:18
Smallest prime with a digit sum of 911 Stargate38 Puzzles 6 2014-09-29 14:18
Smallest floor of k for cullen prime Citrix Prime Cullen Prime 12 2007-04-26 19:52
Smallest ten-million-digit prime Heck Factoring 9 2004-10-28 11:34

All times are UTC. The time now is 00:34.

Tue Oct 20 00:34:36 UTC 2020 up 39 days, 21:45, 0 users, load averages: 2.42, 2.56, 2.35

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.