mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-03-16, 14:39   #23
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A316 Posts
Default

Were these the droids you were looking for?
216^16384+109^16384
Batalov is offline   Reply With Quote
Old 2018-03-16, 15:08   #24
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

25×5 Posts
Lightbulb

Quote:
Originally Posted by Batalov View Post
Were these the droids you were looking for?
216^16384+109^16384
Yes! And is it certain that 216^16384+109^16384 is minimal?

Did you search and find this now, or was it something that was known (to you) in advance?

Of course, now I want then minimal odd prime a^(2^m)+b^(2^m) for all the next m values

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2018-03-16, 16:30   #25
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·859 Posts
Default

Quote:
Originally Posted by Batalov View Post
Were these the droids you were looking for?
216^16384+109^16384
For added confidence in Serge's result:

Code:
time ./pfgw64 -k -f0 -od -q"216^16384+109^16384" | ../../coding/gwnum/hybrid -
                              
Testing (x + 1)^(n + 1) == 2 + 3 (mod n, x^2 - 3*x + 1)...
Likely prime!

real	1m45.793s
user	2m36.120s
sys	0m55.244s
paulunderwood is offline   Reply With Quote
Old 2018-03-16, 16:30   #26
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×7×132 Posts
Default

If one wanted to check exponents 2^m for several values of m, one might want to compile a table of pairs (a,b) with a < b, b <= N (given upper bound), gcd(a, b) = 1, and a + b odd. This isn't entirely trivial. And I'm quite poor at this sort of thing.

Without the condition that a + b be odd, it would be equivalent to calculating the Farey sequence of order N. Perhaps the way to go is to calculate the Farey sequence, and then skip pairs where a and b are both odd.

One idea I considered by rejected was, for even b, find the positive integers r < b with gcd(r, b) = 1, then fill in the entries (b, r + k*b) with r + k*b not exceeding N. Alas, you would have to make sure, for each r, that the multiplier k was relatively prime to r...

Of course, viewing table computation as a preliminary calculation, it probably makes little difference how clumsily it is compiled, if N isn't very big. For large exponents, the value of b will be a good indicator of the size of a^(2^m) + b^(2^m)

The idea of sieving out multiples of "small" primes p congruent to 1 (mod 2^(m+1)) makes sense. Each pair (a, b) sieved out as giving a multiple of p means you can skip a PRP test. I looked at the primes p congruent to 1 (mod 2^15) up to the limit 50 million. There are 174 such primes. Grasping at straws(*), I computed the product (1 - 2^14/p) over these primes, and got .507+ which would be great if it meant eliminating almost half the pairs (a, b) actually under consideration.

(*) I reckoned that the relevant thing here was the 2^14 solutions to Mod(r,p)^(2^14) + 1 = Mod(0,p). Each pair (Mod(a,p), Mod(r, p)*Mod(a,p)) gives a multiple of p. This ignores the question of which such pairs might reduce to pairs of small coprime integers (a, b) of different parity. But hey -- any PRP test you can skip cheaply is to the good, right?

I did a quick check of the idea with the exponent 16. I looked at the smallest prime (p = 97) congruent to 1 (mod 32), and easily found from the root Mod(19,97) to

x^16 + 1 = Mod(0,97)

that 5^16 + 2^16 is a multiple of 97.

Last fiddled with by Dr Sardonicus on 2018-03-16 at 16:31 Reason: Fixing typos
Dr Sardonicus is online now   Reply With Quote
Old 2018-03-16, 16:52   #27
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
Yes! And is it certain that 216^16384+109^16384 is minimal?

Did you search and find this now, or was it something that was known (to you) in advance?

Of course, now I want then minimal odd prime a^(2^m)+b^(2^m) for all the next m values

/JeppeSN
It is minimal.
What puzzles me is why is this taking others so long to find the same? It only took overnight on 8 cores. The workflow is very simple: generate (a,b)s in 1 second with a trivial Pari script (opposite parity, gcd > 1, say, up to a<=400), then split into a few workfiles (hawever many cores you have) and run pfgw -f"{65536}" -N -k -l input on each chunk, periodically check, ..., done!

For m=15, it is perhaps best to sieve, but for m=14, this -f parameter takes care of the small factors just well enough.
Batalov is offline   Reply With Quote
Old 2018-03-16, 17:15   #28
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5×593 Posts
Default

It is just a question of resources. For this random question I only used 1 core for sieving and 1 core for pfgw, I had no need to use more, rest is running Prime95 on this machine, it is not like we had to find the answer within a certain time limit.

I only tried briefly using pfgw for trial factoring long ago, and my impression was it was horribly slow at it, so I have not tried again, I might try next time I need it.


Edit: and yes I should have sorted the list so it ran pfgw on candidates by size, but I made this quick program last night before I went to bed, and I only got 4-5 hours of sleep before work.

Last fiddled with by ATH on 2018-03-16 at 17:17
ATH is offline   Reply With Quote
Old 2018-03-16, 17:41   #29
axn
 
axn's Avatar
 
Jun 2003

470610 Posts
Default

Quote:
Originally Posted by Batalov View Post
run pfgw -f"{65536}" -N -k -l input on each chunk, periodically check, ..., done!
The should be f{32768}. You will miss a prolific factor 10*16384+1
axn is offline   Reply With Quote
Old 2018-03-16, 18:28   #30
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011101000112 Posts
Default

A typo, this command-line is already prepared for m=15. :-)
Batalov is offline   Reply With Quote
Old 2018-03-16, 18:49   #31
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Technically if a and b are squares you find one for the next level up as well.

Last fiddled with by science_man_88 on 2018-03-16 at 18:50
science_man_88 is offline   Reply With Quote
Old 2018-03-16, 19:36   #32
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134468 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Technically if a and b are squares you find one for the next level up as well.
Yes, but 216 and 109 aren't (though the former is a cube).
CRGreathouse is offline   Reply With Quote
Old 2018-03-16, 20:00   #33
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,041 Posts
Default

Another droid crossed my path. 260^32768+179^32768
Not proven minimal yet, though.
Batalov 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 23:48.

Mon Oct 19 23:48:22 UTC 2020 up 39 days, 20:59, 0 users, load averages: 1.71, 2.01, 2.23

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.