 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-16, 14:39 #23 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23A316 Posts Were these the droids you were looking for? 216^16384+109^16384   2018-03-16, 15:08   #24
JeppeSN

"Jeppe"
Jan 2016
Denmark

25×5 Posts Quote:
 Originally Posted by Batalov 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   2018-03-16, 16:30   #25
paulunderwood

Sep 2002
Database er0rr

22·859 Posts Quote:
 Originally Posted by Batalov 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   2018-03-16, 16:30 #26 Dr Sardonicus   Feb 2017 Nowhere 3×7×132 Posts 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   2018-03-16, 16:52   #27
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts Quote:
 Originally Posted by JeppeSN 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.   2018-03-16, 17:15 #28 ATH Einyen   Dec 2003 Denmark 5×593 Posts 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   2018-03-16, 17:41   #29
axn

Jun 2003

470610 Posts Quote:
 Originally Posted by Batalov 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   2018-03-16, 18:28 #30 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100011101000112 Posts A typo, this command-line is already prepared for m=15. :-)   2018-03-16, 18:49 #31 science_man_88   "Forget I exist" Jul 2009 Dumbassville 8,369 Posts 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   2018-03-16, 19:36   #32
CRGreathouse

Aug 2006

134468 Posts Quote:
 Originally Posted by science_man_88 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).   2018-03-16, 20:00 #33 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,041 Posts Another droid crossed my path. 260^32768+179^32768 Not proven minimal yet, though.   Thread Tools Show Printable Version Email this Page 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 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