mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-03-20, 16:24   #67
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10111110011002 Posts
Default

I looked at the exponent e = 2^14. Rather than compute the gcd's of pairs of numbers a^e + b^e -- which would have been a godawful amount of computation -- I did the following: I used my list of primes p == 1 (mod 2^15) up to 2^26, and went through all the pairs [a,b] with a < b, a+b odd, gcd(a,b) = 1, and b < 201. For each prime p, I simply counted the number of pairs for which a^e + b^e was divisible by p (employing Batalov's b/a trick). This took seconds, not minutes.

What I found was, the first prime on my list, p = 65537, divided over 2,000 of the numbers a^e + b^e -- nearly a quarter of them. The number of a^e + b^e divisible by p decreased rapidly with p, but IIRC was at least 2 for the first 120 primes on the list, at least 3 for the first 103 primes on the list, and at least 4 for the first 63 primes on the list.
Dr Sardonicus is offline   Reply With Quote
Old 2018-03-21, 14:26   #68
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×1,523 Posts
Default

Once upon a time, long long ago -- here in fact -- I posted the following ineptly-written script, along with its running time:

Quote:
? k=1;v=vector(s);for(j=2,200,for(i=1,j-1,if((i+j)%2==1&&gcd(i,j)==1,v[k]=[i,j];k++)))
time = 47 ms.
It suddenly occurred to me -- D'OH! -- that I could insure that i + j was odd in more or less the same way I had kept track of parity in my script computing the number s of pairs (i,j) in advance. (Hey, I said I'm not very good at writing scripts!) This really helps, because it halves the number of steps in the inner loop.

? k=1;v=vector(s);f=0;for(j=2,200,forstep(i=f+1,j-1,2,if(gcd(i,j)==1,v[k]=[i,j];k++));f=!f)
time = 23 ms.

Half the steps, half the time...

For e = 2^14 I also looked at how many p == 1 (mod 2*e), p < 2^26, divide the numbers a^e + b^e. The champion pair was (116,127); 116^e + 127^e is divisible by 65537, 1146881, 1179649, 17367041, and 46497793.
Dr Sardonicus is offline   Reply With Quote
Old 2018-03-22, 16:52   #69
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2668 Posts
Default

The entry A291944 is public now. /JeppeSN
JeppeSN is offline   Reply With Quote
Old 2018-03-22, 18:15   #70
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5·1,997 Posts
Default

a(17) > 412
and sieved to a<=600 up to 52 bits (and higher in some ranges)
Batalov is offline   Reply With Quote
Old 2018-03-22, 20:50   #71
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
The entry A291944 is public now. /JeppeSN
Very nice!
CRGreathouse is offline   Reply With Quote
Old 2018-03-23, 15:34   #72
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·1,523 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
The entry A291944 is public now. /JeppeSN
That's pretty good. Since x^(2^N) + y^(2^N) is a "non-full form" for N > 1, there isn't much theory to guide estimates of the size of the minimal prime of that form, etc. So, numerical computation seems to be the way to go. (If someone knows any decent heuristic estimates, though, please post them, or a link).

It occurred to me that, for a given N, odd (pseudo)primes of the form a^(2^N) + b^(2^N) are of two types: smaller number is odd, and smaller number is even. I computed the smallest of both types up to the limit N = 10, without doing any sieving, because it would have taken me longer to set up the sieving, than it took the clunky test-all-pairs scripts to run. (Pressing on to N = 11 and higher, though, it would definitely be worth the effort of doing a LOT of sieving.)

My default assumption is that the minimal [a, b] are of each type (approximately) equally often as the upper bound for N increases. I have no idea how much larger the minimal pair of the other type may be compared to the minimal pair; whether there may be several pairs of the same type as the minimal pair which smaller than the minimal pair of the other type; etc.

N = 1: [1, 2], [2, 3]
N = 2; [1, 2], [2, 3]
N = 3; [1, 2], [2, 13]
N = 4; [1, 2], [6, 7]
N = 5; [8, 9], [13, 18]
N = 6; [8, 11], [7, 16]
N = 7; [20, 27], [31, 32]
N = 8; [5, 14], [34, 43]
N = 9; [2, 13], [35, 38]
N = 10; [26, 47], [39, 56]
N = 11; [3, 22], ??
N = 12; [2, 53], ??
N = 13; [43, 72], ??
N = 14; [109, 216], ??
N = 15; [179, 260], ??
N = 16; [57,124], ??

Finally, the "two types" issue doesn't occur for the (pseudo)primes (a^(2^N) + b^(2^N))/2 with a and b both odd.
Dr Sardonicus is offline   Reply With Quote
Old 2018-03-23, 17:42   #73
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5·1,997 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
(If someone knows any decent heuristic estimates, though, please post them, or a link).
Clearly there is no precise estimate, just like with any Poisson process. The estimate with 70%confidence interval will be +- 100% of the trend value. (and the 95% CI will be from 0 to several times trend.)

Trend value's estimate is very easy. Nearly all candidates will have an equal chance to be prime which only depends on their size which is almost exactly the same in bits. So, one will have to try on the order of ~γ * 2m pairs, and you have ~0.2 * a^2 pairs up to a, hence:
a(m) ~ 1.15 * 2m/2
Plot the values and you will find great concordance with this estimate.
Batalov is offline   Reply With Quote
Old 2018-03-24, 04:15   #74
axn
 
axn's Avatar
 
Jun 2003

34×67 Posts
Default

Quote:
Originally Posted by Batalov View Post
Here is an unpolished sieve (and a lazy one - I didin't implement the pseudocode above fully; that is, - I am simply exponentiating all a's). It is really ugly but it works. I am sieving m=17 case to 50-51 bits with this.

( PFGW -f{...} essentially sieves to 44.5-45 bits de facto, so this is a bit of an improvement above simply prefactoring with PFGW. )
So I got bored, and modified your source to add the missing bits. And some bells and whistles.

This one uses explicit k values in cmdline (instead of bits). Also reads/writes files instead of stdin/stdout. Reads sieve.txt for candidates, appends factor.txt for factors, and at the end of the range, writes sieve.txt back with survivors. It also self starts -- if you give starting k as 1, it will generate the initial sieve itself instead of reading from file (but in this case, a third parameter maxa needs to be specified to define the sieve region).

The algorithm is O(maxa), and so it is best to just sieve as large a region as you want from the start (rather than trying to increase it later).

EDIT:- Right now, hard coded to N=17. Change the NN #define, and you're set.
Attached Files
File Type: 7z xGFNsieve_hash.c.7z (2.5 KB, 89 views)

Last fiddled with by axn on 2018-03-24 at 04:20
axn is offline   Reply With Quote
Old 2018-03-24, 08:22   #75
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×1,997 Posts
Default

Neat!
...Now time for a quick cuda sieve facelift, based on gfnsieve? ^_^
Batalov is offline   Reply With Quote
Old 2018-03-24, 13:48   #76
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2×7×13 Posts
Default

For both a and b odd, the first primes are (as others already found but did not post):

Code:
(3^1+1^1)/2
(3^2+1^2)/2
(3^4+1^4)/2
(5^8+3^8)/2
(3^16+1^16)/2
(3^32+1^32)/2
(3^64+1^64)/2
(49^128+9^128)/2
(7^256+3^256)/2
(35^512+9^512)/2
(67^1024+57^1024)/2
It is interesting that the exponent 128 gives a number that is identical to that for 256, i.e. \[\frac{49^{128}+9^{128}}{2}=\frac{7^{256}+3^{256}}{2}\]
JeppeSN is offline   Reply With Quote
Old 2018-03-24, 13:53   #77
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
It is interesting that the exponent 128 gives a number that is identical to that for 256, i.e. \[\frac{49^{128}+9^{128}}{2}=\frac{7^{256}+3^{256}}{2}\]
. Not really, it happens any time both bases are squares.
science_man_88 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 16:35.


Sun Nov 27 16:35:57 UTC 2022 up 101 days, 14:04, 0 users, load averages: 2.06, 1.42, 1.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔