![]() |
![]() |
#1 |
Dec 2008
you know...around...
25×29 Posts |
![]()
This started out as a search for gaps between cyclic or full-reptend primes, where 10 is a primitive root mod p (A001913):
Code:
gap p 2 17 4 19 6 23 8 491 10 7 12 47 14 419 16 577 18 29 20 - 22 1789 ... ... If 10 is not a square mod p and p-20 or p+20 is a prime, then 10 is a square mod p-20 or p+20 respectively. In general, for primes p where r is a primitive root mod p, these gaps are all inadmissible: Code:
r gaps congruent to 2 4 (mod 8) 3 4,6,8 (mod 12) 5 2,8 (mod 10) 6 8,12,16 (mod 24) 7 14 (mod 28) 8 2,4,8,10,12,14,16,20,22 (mod 24) 10 20 (mod 40) 11 22 (mod 44) 12 4,6,8 (mod 12) 13 none 14 28 (mod 56) 15 20,30,40 (mod 60) 17 none 18 4 (mod 8) 19 38 (mod 76) 20 2,8 (mod 10) Next, looking for record gaps between Wieferich primes... ![]() Last fiddled with by mart_r on 2020-01-18 at 11:56 |
![]() |
![]() |
![]() |
#2 | |
Feb 2017
Nowhere
61×107 Posts |
![]() Quote:
If d is not congruent to 1 (mod 4), d = 4*d. Now, d is a "fundamental discriminant," and (apart from primes that may have divided r to even powers), is the least modulus for which the quadratic character (r/p) is equal to (p/d). Whether d is a quadratic residue (mod p) depends only on p (mod d). Thus, the quadratic character of r (mod p) is (again, apart from primes p that divide r to even powers) equal to (p/d). For example, if r = 10, we obtain d = 40. You can compute the quadratic non-residues (mod d) [assuming d isn't very big] in Pari-GP as follows: Code:
v=vector(eulerphi(d)/2);j=0;for(i=1,d-1,if(kronecker(i,d)==-1,j++;v[j]=i)) But things get a bit tricky. If the odd part of d is congruent to 1 (mod 4), then if k is one of the numbers in v, so is d - k. Thus, the differences v[j] - v[i] for j > i will give all possible gaps between quadratic non-residues (mod d). However, if the odd part of d is congruent to 3 (mod 4) this may not be true. (It happens to be true for d = 4*3 = 12, where v = [5, 11] and the only difference is 6). I checked the cases d = 4*7 and 4*11, and in both cases the further differences d + v[i] - v[j] for j > i gave all the even gaps (mod d) that weren't given by v[j] - v[i] with j > i. For r = 11, d = 44, here are the results: Code:
? d=44;v = vector(eulerphi(d)/2);j=0;for(i=1,d-1,if(kronecker(i,d)==-1,j++;v[j]=i)) ? w=vector(#v*(#v-1));k=0;for(i=1,#v-1,for(j=i+1,#v,m=v[j]-v[i];k++;w[k]=m;m=d-m;k++;w[k]=m));w=vecsort(w); ? w %3 = [2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 6, 6, 8, 8, 8, 8, 10, 10, 10, 10, 12, 12, 12, 12, 14, 14, 14, 14, 16, 16, 16, 16, 18, 18, 18, 18, 20, 20, 20, 20, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 24, 24, 24, 24, 26, 26, 26, 26, 28, 28, 28, 28, 30, 30, 30, 30, 32, 32, 32, 32, 34, 34, 34, 34, 36, 36, 36, 36, 38, 38, 38, 38, 40, 40, 40, 40, 42, 42, 42, 42] I suspect the general result is known, but I am too lazy to track it down at the moment. |
|
![]() |
![]() |
![]() |
#3 |
Feb 2017
Nowhere
61·107 Posts |
![]()
Oh, boy, did I ever foul up!
![]() I did the wrong kronecker() calculation. I should have put the value of d first. So I started over, and cobbled together something that at least gives results. I'm sure it could be turned into something usable for at least very small values of interest. The following Pari-GP code does work, but it is a total kludge. I wouldn't use it on numbers d of any size. I didn't even bother with code to make the value of d "suitable," which I decided was values that were either 4 or 8 times odd square free numbers. Given a value r, d = 4*core(r). Instead, I stuck to code for a specific value of d while I worked out my other mistakes, and when I got something that actually worked, tried other values of d by recalling the previous command and filling in new values by hand. I found that for d = 4*3, the gaps 4, 6, and 8 did not occur as the differences of non-residues. For d = 4*5, the gaps 2, 8, 12, and 18 do not occur. d = 4*p, p = 13, 17, and 29, all gaps occur as differences of non-residues. For d = 4*p, p = 7, 11, 19, and 23, only the gap 2*p does not occur. For d = 8*3, the gaps 8, 12, and 16 do not occur. For d = 8*p, p = 5, 7, 11, 13, 17, 19, only the gap 4*p does not occur. Code:
{ d=120; v=vector(eulerphi(d)/2); j=0; for(i=1,d-1,if(kronecker(d,i)==-1,j++;v[j]=i)); w=vector(#v*(#v-1)); k=0; for(i=1,#v-1,for(j=i+1,#v,k++;w[k]=v[j]-v[i];k++;w[k]=d+v[i]-v[j])); gaplist=listsort(List(w),1); if(#gaplist==d/2-1, print(); print("For d = "d" all gaps occur"); return(), l=d/2-#gaplist-1; ng=vector(l); g=vector(d/2-1,i,2*i); for(i=1,#gaplist, r=gaplist[i]; g[r/2]=0 ); j=0; for(i=1,d/2-1, if(g[i]>0, j++; ng[j]=g[i]) ); ); print(); print("d = "d); print("Vector of gaps that are not differences of non-residues is "ng) } d = 120 Vector of gaps that are not differences of non-residues is [40, 60, 80] |
![]() |
![]() |
![]() |
#4 |
Dec 2008
you know...around...
25×29 Posts |
![]()
Thanks, that helps a lot!
Based on your first post, I wrote my own program, and the results agree with yours. At first I was a bit confused about the results for r=8, but since 8 is a perfect power it's a slightly different story where kronecker alone doesn't help. (All primitive roots mod 8 are either 3, 5, or 11 mod 24.) I can't say that I fully understand all the maths behind it yet, but I can relate to the following: A non-perfect power r can only be a primitive root mod p if it's not a square mod (p mod 4r). Thus, to check which gaps are inadmissible, we only have to check all the differences between the set of odd numbers 2n+1 < 8r for which r is a nonsquare mod 2n+1. That, in principle, answers my main questions about this subject. But I'm going to work my way through the proof of quadratic reciprocity once more. I'm reading "Elementary Number Theory" by W. Stein. |
![]() |
![]() |
![]() |
#5 |
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
47·79 Posts |
![]()
For gaps between primes p which 2 is primitive root mod p:
Code:
2,3 6,5 8,29 10,19 14,149 16,37 18,83 22,421 24,107 26,587 30,317 32,2099 34,619 38,2621 40,1693 42,227 46,1381 48,709 50,3203 54,2477 56,4547 58,12979 62,4157 64,4723 66,1307 70,4021 72,947 74,1787 78,5573 80,12659 82,23251 86,20357 88,9949 90,13523 94,18493 96,15971 98,14243 102,33637 104,3083 106,63667 110,20789 112,24547 114,9059 118,88093 120,11317 122,109619 126,70717 128,46349 130,49891 134,244109 136,70237 138,105691 142,132709 144,18269 146,425387 150,221261 152,266117 154,62323 158,235541 160,31699 162,139907 166,102877 168,65371 170,142211 174,199037 176,265163 178,296299 182,223829 184,411013 186,137723 190,699757 192,191837 194,658643 198,103093 200,339827 202,302227 206,2989757 208,806581 210,425603 214,155797 216,598427 218,184259 222,736469 224,514949 226,2373307 230,1530293 232,1078411 234,512819 238,1427509 240,370133 242,1353371 246,2084653 248,476603 250,2551099 254,4013573 256,2617651 |
![]() |
![]() |
![]() |
#6 |
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
47·79 Posts |
![]()
This is a list of the primes p such that p+2 is also prime, and both p and p+2 have primitive root 2:
3, 11, 59, 179, 347, 419, 659, 827, 1451, 1619, 1667, 2027, 2267, 3467, 3851, 4019, 4091, 4259, 4787, 6779, 6827, 6947, 7547, 8219, 8291, 8819, 9419, 10067, 10091, 10139, 10499, 10859, 12251, 12611, 13931, 14387, 14627, 14867, 16067, 16187, 16979, 17387, 17747, 19139, 20507, 20771, 21011, 21491, 21587, 21611, 22619, 22859, 23027, 23627, 24107, 25931, 27059, 28307, 28547, 28571, 29387, 30011, 30467, 30851, 32027, 32531, 32939, 33347, 33827, 34211, 34259, 35051, 35507, 36011, 36107, 36467, 36779, 36899, 37547, 38651, 38747, 39227, 44267, 44531, 44699, 45587, 46091, 46307, 47147, 47387, 47699, 48539, 49331, 49667, 49739, 50051, 50891, 51059, 51419, 51827, 51971, 52067, 54419, 54539, 55619, 56267, 56891, 57347, 57899, 58787, 58907, 59219, 59627, 60659, 60899, 61331, 62987, 63419, 63587, 64187, 64451, 65027, 65099, 65171, 65267, ... Are there infinitely many such primes? |
![]() |
![]() |
![]() |
#7 | |
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
371310 Posts |
![]() Quote:
Code:
m\n 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 2: 3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593, 3: 2, 11, 67, 13, 41, 61, 883, 313, 271, 431, 5743, 193, 3511, 1583, 2131, 433, 2551, 4177, 8513, 2521, 8779, 683, 10627, 1321, 29851, 1223, 3079, 9661, 49939, 661, 101681, 4129, 4: 0, 3, 0, 17, 0, 31, 0, 73, 0, 151, 0, 433, 0, 631, 0, 337, 0, 127, 0, 241, 0, 331, 0, 601, 0, 4421, 0, 673, 0, 3061, 0, 257, 5: 2, 11, 13, 101, 0, 199, 827, 569, 487, 31, 1453, 181, 7853, 71, 0, 401, 5407, 379, 15277, 761, 1303, 2069, 5107, 409, 0, 1171, 5077, 3109, 1973, 2521, 5023, 449, 6: 11, 19, 7, 5, 31, 139, 463, 97, 37, 101, 353, 241, 4889, 43, 421, 5233, 6563, 1747, 8171, 1901, 11551, 3719, 3037, 409, 28001, 26833, 26407, 11789, 5801, 3931, 48299, 15073, 7: 2, 3, 73, 29, 1031, 19, 43, 113, 883, 311, 353, 1453, 2861, 281, 181, 1873, 409, 1531, 191, 1621, 2311, 419, 14629, 5233, 12251, 7333, 32941, 4397, 11717, 811, 23251, 1409, 8: 3, 17, 13, 113, 251, 7, 1163, 89, 109, 431, 1013, 577, 4421, 953, 571, 257, 4523, 127, 15467, 3761, 3109, 7151, 18539, 73, 25301, 14327, 2971, 42953, 72269, 151, 683, 12641, 9: 0, 5, 0, 13, 0, 67, 0, 313, 0, 41, 0, 61, 0, 883, 0, 433, 0, 271, 0, 2161, 0, 683, 0, 193, 0, 1223, 0, 8317, 0, 2131, 0, 769, 10: 7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289, 11: 2, 7, 193, 5, 191, 19, 379, 449, 199, 1301, 2531, 1549, 2081, 547, 61, 1697, 2789, 523, 28843, 661, 1303, 1013, 18539, 2377, 4001, 1847, 31267, 6917, 10499, 1231, 39929, 6689, 12: 5, 23, 19, 37, 271, 13, 29, 193, 487, 11, 89, 373, 521, 421, 211, 5521, 7243, 829, 2129, 1741, 20707, 1453, 10903, 673, 17551, 4993, 12799, 5209, 233, 3181, 25793, 3169, 13: 2, 3, 7, 17, 331, 103, 2017, 673, 1657, 311, 463, 1213, 0, 1303, 271, 337, 1123, 1171, 19001, 61, 421, 7283, 4049, 2617, 1151, 157, 3889, 701, 8237, 601, 71983, 641, 14: 3, 5, 37, 113, 41, 67, 71, 401, 1459, 61, 463, 13, 3121, 659, 1381, 977, 41413, 1009, 1597, 461, 967, 8779, 23369, 12049, 9151, 547, 811, 8233, 132299, 5431, 148367, 2081, 15: 2, 11, 31, 53, 761, 7, 1163, 257, 3691, 311, 991, 1549, 443, 617, 2551, 2417, 1361, 1801, 2129, 3541, 3697, 1123, 12329, 5641, 4651, 2393, 4159, 113, 9629, 1201, 23003, 1249, 16: 0, 3, 0, 5, 0, 31, 0, 17, 0, 151, 0, 109, 0, 631, 0, 113, 0, 127, 0, 1181, 0, 331, 0, 433, 0, 13963, 0, 1709, 0, 3331, 0, 1217, 17: 2, 13, 73, 149, 181, 223, 29, 257, 541, 101, 2003, 229, 1093, 1471, 991, 433, 0, 883, 2851, 1361, 3361, 1409, 19183, 3673, 13901, 3719, 7723, 8093, 6091, 2371, 10789, 1889, 18: 5, 7, 13, 73, 131, 79, 1667, 41, 19, 311, 3917, 1201, 443, 113, 1381, 17, 1259, 199, 229, 2801, 1429, 881, 1427, 1153, 18701, 599, 12853, 6833, 20939, 2671, 19469, 3361, 19: 2, 3, 97, 101, 131, 307, 1303, 233, 271, 1291, 199, 277, 859, 197, 691, 1217, 12037, 487, 24967, 1901, 1009, 8999, 2393, 4561, 4951, 5227, 6373, 8513, 56957, 151, 14447, 2753, 20: 3, 11, 7, 29, 0, 151, 197, 521, 577, 71, 617, 61, 1873, 491, 0, 1489, 307, 19, 7753, 661, 127, 4049, 9293, 1129, 0, 859, 3673, 3221, 44777, 691, 8123, 929, 21: 2, 37, 13, 5, 11, 43, 953, 337, 433, 461, 199, 1129, 599, 211, 661, 881, 3877, 1747, 14897, 3301, 0, 1277, 52901, 1801, 14551, 30707, 2971, 14197, 34337, 1171, 41231, 1697, 22: 5, 3, 43, 13, 241, 7, 631, 521, 73, 461, 23, 613, 157, 127, 5791, 433, 10337, 2647, 37013, 401, 4201, 947, 17021, 97, 12101, 3407, 15013, 6329, 14153, 1381, 12959, 353, 23: 2, 7, 31, 29, 71, 103, 239, 233, 163, 11, 859, 1093, 53, 911, 271, 1153, 7039, 2719, 25423, 461, 211, 1013, 5843, 3889, 1901, 79, 57349, 1933, 13399, 2131, 17299, 4129, 24: 7, 5, 61, 29, 131, 67, 127, 457, 613, 311, 199, 2617, 79, 379, 991, 241, 4999, 307, 12541, 6581, 8527, 23, 11777, 1009, 1451, 4967, 22303, 2381, 349, 1321, 5023, 4801, 25: 0, 3, 0, 29, 0, 13, 0, 569, 0, 31, 0, 181, 0, 71, 0, 401, 0, 379, 0, 641, 0, 1453, 0, 409, 0, 1171, 0, 3109, 0, 2851, 0, 8609, 26: 3, 11, 151, 5, 31, 19, 547, 313, 1657, 1031, 859, 37, 6397, 3823, 181, 337, 4421, 3853, 4409, 7741, 757, 2311, 37307, 8161, 3701, 2393, 19441, 1597, 1567, 5101, 23561, 4001, 27: 2, 11, 7, 0, 41, 37, 1289, 0, 307, 431, 9857, 13, 7853, 1583, 1051, 0, 7481, 73, 8513, 0, 883, 683, 14813, 313, 38501, 1223, 271, 0, 59393, 661, 101681, 0, 28: 5, 3, 61, 53, 601, 199, 127, 449, 1423, 281, 4093, 1117, 3719, 29, 631, 113, 4999, 613, 23447, 541, 547, 6359, 6211, 6073, 14851, 4733, 4159, 6469, 33641, 4561, 1861, 6113, 29: 2, 5, 31, 13, 61, 7, 617, 1289, 541, 571, 727, 181, 2549, 673, 3121, 2609, 1259, 3061, 2927, 11981, 757, 67, 12743, 7321, 11701, 313, 16417, 12853, 0, 1831, 8123, 12577, 30: 11, 7, 73, 17, 991, 19, 1289, 257, 163, 71, 67, 277, 53, 1163, 31, 113, 1259, 613, 7069, 461, 337, 947, 9293, 409, 401, 1171, 3673, 29, 52259, 241, 14323, 10337, 31: 2, 3, 13, 5, 191, 271, 659, 977, 37, 541, 5237, 349, 4759, 911, 4111, 1217, 2143, 2683, 2129, 3221, 2689, 3499, 2531, 2857, 7901, 1613, 11827, 2437, 45821, 571, 40487, 577, 32: 3, 7, 43, 113, 11, 223, 1163, 73, 397, 41, 1013, 1753, 4733, 673, 691, 257, 1429, 127, 6043, 281, 33013, 6337, 18539, 1777, 251, 14327, 5347, 2857, 72269, 31, 683, 2593, Last fiddled with by sweety439 on 2020-01-19 at 15:13 |
|
![]() |
![]() |
![]() |
#8 | |
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
47×79 Posts |
![]() Quote:
Last fiddled with by sweety439 on 2020-01-19 at 16:11 |
|
![]() |
![]() |
![]() |
#9 | |
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
1110100000012 Posts |
![]() Quote:
|
|
![]() |
![]() |
![]() |
#10 | |
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
47×79 Posts |
![]() Quote:
If n is divisible by 12, then such prime exists for every m>=2 Such prime does not exist if and only if one of these three conditions holds: (note that any pair of two of these three conditions cannot both hold) * m is square, n is odd, n > 1 * Let m' be the squarefree part of m, m' == 1 mod 4, m' > 1, n is odd, and n is multiple of m' * m is of the form 27*k^6, n == 4 or 8 mod 12 Code:
m n such that such prime does not exist 4 m == 1 mod 2 5 m == 5 mod 10 9 m == 1 mod 2 (except m = 1) 13 m == 13 mod 26 16 m == 1 mod 2 17 m == 17 mod 34 20 m == 5 mod 10 21 m == 21 mod 42 25 m == 1 mod 2 (except m = 1) 27 m == 4, 8 mod 12 29 m == 29 mod 58 33 m == 33 mod 66 36 m == 1 mod 2 37 m == 37 mod 74 41 m == 41 mod 82 45 m == 5 mod 10 49 m == 1 mod 2 (except m = 1) 52 m == 13 mod 26 53 m == 53 mod 106 57 m == 57 mod 114 61 m == 61 mod 122 64 m == 1 mod 2 65 m == 65 mod 130 68 m == 17 mod 34 69 m == 69 mod 138 73 m == 73 mod 146 77 m == 77 mod 154 80 m == 5 mod 10 81 m == 1 mod 2 (except m = 1) 84 m == 21 mod 42 85 m == 85 mod 170 89 m == 89 mod 178 93 m == 93 mod 186 97 m == 97 mod 194 100 m == 1 mod 2 101 m == 101 mod 202 105 m == 105 mod 210 109 m == 109 mod 218 113 m == 113 mod 226 116 m == 29 mod 58 117 m == 13 mod 26 121 m == 1 mod 2 (except m = 1) 125 m == 5 mod 10 Last fiddled with by sweety439 on 2020-01-19 at 22:35 |
|
![]() |
![]() |
![]() |
#11 |
Dec 2008
you know...around...
25·29 Posts |
![]()
I've computed this a while ago, just posting here now lest the data goes to waste on my hard drive.
New maximal gap of 1520 between FRPs 282,332,382,833 (nice number, is it not?) and 282,332,384,353. While the sum of reciprocals of FRPs exceeds 1 after p=10,627,446,821, we'll have to wait until p~2.389*10145 until the sum exceeds 2. I've pinpointed the reciprocal summation formula to Artin*log(log(p))-c where Artin is the well-known 0.3739558... and c is the lesser known 0.173943945 ± 10-8. Maybe something can be concocted to close in on that c using Meissel-Mertens constants (lookey here: https://www.math.unipd.it/~languasc/...eckresults.txt) M(40,7), M(40,11) etc., subtracting those in the set that are not FRPs? I couldn't figure out whether or not this is possible. Which is kinda sad, because that's where the real math starts. |
![]() |
![]() |
![]() |
Thread Tools | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
Gaps of Primes? | PawnProver44 | Miscellaneous Math | 10 | 2016-04-10 19:32 |
Primitive roots for a set of primes | mart_r | Math | 0 | 2013-07-20 12:23 |
Primitive Roots | Numbers | Math | 16 | 2005-09-21 23:41 |
Is 3 always a primitive root for mersenne primes? | juergen | Math | 12 | 2005-03-09 08:18 |
Is 3 always a primitive root for mersenne primes? | juergen | Programming | 9 | 2005-03-08 03:51 |