mersenneforum.org > Math Smallest prime of the form a^2^m + b^2^m, m>=14
 Register FAQ Search Today's Posts Mark Forums Read

2018-03-15, 17:26   #12
paulunderwood

Sep 2002
Database er0rr

D6C16 Posts

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

2018-03-15, 19:00   #13
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

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

2018-03-16, 06:18   #14
JeppeSN

"Jeppe"
Jan 2016
Denmark

2408 Posts

Quote:
 Originally Posted by paulunderwood 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

2018-03-16, 08:30   #15
axn

Jun 2003

2·13·181 Posts

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

2018-03-16, 10:33   #16
paulunderwood

Sep 2002
Database er0rr

22·859 Posts

Quote:
 Originally Posted by axn 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

 2018-03-16, 10:36 #17 JeppeSN     "Jeppe" Jan 2016 Denmark 25·5 Posts 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
2018-03-16, 12:19   #18
ATH
Einyen

Dec 2003
Denmark

B9516 Posts

Quote:
 Originally Posted by axn 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.

2018-03-16, 13:15   #19
axn

Jun 2003

2·13·181 Posts

Quote:
 Originally Posted by ATH I'm already working on a=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 I'm running pfgw while continuing to trial factor. So far no PRP in 2<=b<=16 and b
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

 2018-03-16, 13:51 #20 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 19·101 Posts 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.
2018-03-16, 13:53   #21
JeppeSN

"Jeppe"
Jan 2016
Denmark

25×5 Posts

Quote:
 Originally Posted by axn 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

2018-03-16, 14:21   #22
axn

Jun 2003

2×13×181 Posts

Quote:
 Originally Posted by axn 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post PawnProver44 Miscellaneous Math 9 2016-03-19 22:11 arbooker And now for something completely different 14 2015-05-22 23:18 Stargate38 Puzzles 6 2014-09-29 14:18 Citrix Prime Cullen Prime 12 2007-04-26 19:52 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

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.