mersenneforum.org > Math Prime residues of near-prime modulo a prime
 Register FAQ Search Today's Posts Mark Forums Read

2021-11-18, 12:32   #23
robert44444uk

Jun 2003
Oxford, UK

25×32×7 Posts

Quote:
 Originally Posted by Dr Sardonicus I haven't even begun to think about what governs the size of c1, but although I've seen a number of cases where c1 is fairly close to c2, I haven't noticed any instances where c1 > c2.
c2-c1 negative - these are common at low N. There are 3158 examples in N< 135536 but none after this, checked up to N=304000. Between N=13336 and N=304000 the least difference is c2-c1=6 demonstrated by 182978.

For N = 10 and N=34 , c1=0

 2021-11-18, 17:21 #24 robert44444uk     Jun 2003 Oxford, UK 25·32·7 Posts Coming back to Goldbach. It is proved that there is a prime between N/2 and N (Bertrand- Chebyshev), with N even Using this prime residue technique, is it correct to paraphrase Goldbach to say it is conjected that there exists at least 1 prime p(i) between N/2 to N where N mod p(i) == a prime, p(ii) with p(ii) =< p(i) ? I think this is equivalent to stating that there are 2 primes which add up to N. It should be possible to list N in terms of the prime mod primes discovered between N/2 and N (c2) to find out the factors of N where the count of c2 is very low compared to the size of N. I have done this to N=200000, and the lowest are as follows: My interpretation of the data is that the lowest number of prime pairs that add up to N are predominately found when N factors as 2^x.prime, x from upwards. In this range, there are no small factors other than 2. In this example, the smallest factor is 263. Code: N p >n/2 c2 ratio factors 198728 8347 1008 0.12076195 2.2.2.24841 182012 7692 929 0.120774831 2.2.45503 144128 6217 751 0.120797812 2.2.2.2.2.2.2.2.563 181904 7685 929 0.120884841 2.2.2.2.11369 199328 8366 1013 0.121085345 2.2.2.2.2.6229 196754 8272 1004 0.121373308 2.98377 191834 8073 980 0.121392295 2.95917 195368 8215 998 0.121485088 2.2.2.2.4421 158428 6791 826 0.121631571 2.2.39607 198916 8353 1016 0.121632946 2.2.223.223 167438 7127 867 0.121650063 2.83719 173948 7381 898 0.121663731 2.2.43487 191024 8039 979 0.121781316 2.2.2.2.11939 188882 7964 970 0.121798091 2.94441 168068 7151 871 0.121801147 2.2.42017 179618 7610 927 0.121813403 2.89809 189872 8004 976 0.12193903 2.2.2.2.11867 196628 8266 1008 0.121945318 2.2.49157 176678 7493 914 0.121980515 2.88339 183916 7771 948 0.121992022 2.2.45979 174362 7400 903 0.122027027 2.87181 176024 7448 909 0.122046187 2.2.2.22003 199846 8387 1024 0.122093716 2.99923 189578 7993 976 0.122106843 2.94789 188834 7963 973 0.122190129 2.263.359 At the other end of the spectrum, smooth N predominate Code: N p >n/2 c2 ratio factors 2310 152 114 0.7500000000 2.3.5.7.11 660 54 41 0.7592592593 2.2.3.5.11 270 25 19 0.7600000000 2.3.3.3.5 78 9 7 0.7777777778 2.3.13 96 9 7 0.7777777778 2.2.2.2.2.3 300 27 21 0.7777777778 2.2.3.5.5 840 65 51 0.7846153846 2.2.2.3.5.7 144 14 11 0.7857142857 2.2.2.2.3.3 34 5 4 0.8000000000 2.17 42 5 4 0.8000000000 2.3.7 84 10 8 0.8000000000 2.2.3.7 168 16 13 0.8125000000 2.2.2.3.7 240 22 18 0.8181818182 2.2.2.2.3.5 390 33 27 0.8181818182 2.3.5.13 180 17 14 0.8235294118 2.2.3.3.5 48 6 5 0.8333333333 2.2.2.2.3 126 12 10 0.8333333333 2.3.3.7 630 49 41 0.8367346939 2.3.3.5.7 60 7 6 0.8571428571 2.2.3.5 66 7 6 0.8571428571 2.3.11 150 14 12 0.8571428571 2.3.5.5 330 28 24 0.8571428571 2.3.5.11 420 35 30 0.8571428571 2.2.3.5.7 90 10 9 0.9000000000 2.3.3.5 120 13 12 0.9230769231 2.2.2.3.5 10 2 2 1.0000000000 2.5 16 2 2 1.0000000000 2.2.2.2 36 4 4 1.0000000000 2.2.3.3 210 19 19 1.0000000000 2.3.5.7 Last fiddled with by robert44444uk on 2021-11-18 at 17:26
 2021-11-18, 20:25 #25 Dr Sardonicus     Feb 2017 Nowhere 123578 Posts The Prime Number Theorem (PNT) gives the asymptotic estimate N/log(n) - (N/2)/log(N/2) which is approximately (1/2)*N/log(N)) for the number of primes between N/2 and N. The Hardy-Littlewood conjectural asymptotic formula for the number of representations of N as the sum of two odd primes is 2*C2*N/log2(N)*$\prod_{p\mid N}^{p\;odd}\frac{p-1}{p-2}$ where the product is over the odd prime factors of N and C2 = 0.66016... is the "twin primes constant." This is of smaller order than the number of primes in (N/2, N) by a factor of log(N). Your observation about small prime factors is perfectly in line with the last factor in the Hardy-Littlewood formula, a product over the odd prime factors of N. That factor is biggest when N has a lot of small prime factors, and is smallest if N is a power of 2 (when the factor is the empty product, or 1). For N = 2x*p, p an odd prime, the factor is (p-1)/(p-2). I'm still making no further progress with the residues N%p for p < N/2. As we have already seen, you can carve out intervals N/(k+1) < p < N/k for which N%p is guaranteed to be composite, but that's not nearly enough to get the count of prime residues down to something of order N/log2(N). EDIT: I did come up with a handwaving argument that for large even N the number of prime residues N%p, 2 < p < N/2, is of order N/log2(N). By the Prime Number Theorem, the number of primes $\le$ x is asymptotic to x/log(x). So if p is a "large" prime, about 1/log(p) of the numbers < p are prime. Now for sqrt(N) < p < N/2, log(p) only varies between (1/2)*log(N) and log(N) - log(2). So, assuming, by wave of hand, that for a given p < N/2 not dividing N the residues 1 to p-1 N%p are all "equally likely," we guess that the number of prime residues for sqrt(N) < p < N/2 is of order 1/log(N)*N/log(N) or N/log2(N). There are obviously no more than sqrt(N) primes p < sqrt(N), and sqrt(N) is of lower order than N/log2(N). Last fiddled with by Dr Sardonicus on 2021-11-19 at 20:03 Reason: as indicated
2021-11-20, 13:55   #26
robert44444uk

Jun 2003
Oxford, UK

25×32×7 Posts

Quote:
 Originally Posted by robert44444uk The straight line solution at y=1, suggests x = 69.24 which corresponds to N= e^69.24 or about 1.18e30, still out of reach from a calculation perspective, but significant lower than the previous estimate.
Using 2^30 as the major set of prime factors in N suggests N= e^75.33 corresponding to 5e32. At this type of value of N, the ratio again drops below 1, last seen with N=20

The data below was obtained by running my program for about a week.

Quote:
 N-1 ------------------- ratio 2147483647 1.15794911583994 559419490303 1.143415432 636728901631 1.142847684 817117528063 1.141814031 1377610760191 1.140112789 1403380563967 1.140059613 1918776639487 1.139185906 2073395462143 1.138948385 2266668990463 1.138736027 2369748205567 1.138647817 2814277320703 1.138180496 2910914084863 1.138120794 3110630064127 1.137940743 3310346043391 1.137813568 3619583688703 1.137604767

Last fiddled with by robert44444uk on 2021-11-20 at 14:00

2021-11-20, 14:55   #27
Dr Sardonicus

Feb 2017
Nowhere

23×233 Posts

Quote:
Originally Posted by robert44444uk
Using 2^30 as the major set of prime factors in N suggests N= e^75.33 corresponding to 5e32. At this type of value of N, the ratio again drops below 1, last seen with N=20

The data below was obtained by running my program for about a week.
Quote:
 N-1 ------------------- ratio 2147483647 1.15794911583994 559419490303 1.143415432
Is this your original "density ratio?"

2021-11-21, 11:00   #28
robert44444uk

Jun 2003
Oxford, UK

25×32×7 Posts

Quote:
 Originally Posted by Dr Sardonicus Is this your original "density ratio?"
Yes, the last of these is the lowest ratio, N-1 prime, seen once small N are taken out of the consideration.

Last fiddled with by robert44444uk on 2021-11-21 at 11:16

 Similar Threads Thread Thread Starter Forum Replies Last Post Hugo1177 Miscellaneous Math 5 2021-02-11 07:40 Hugo1177 Miscellaneous Math 1 2021-01-05 08:09 axn Computer Science & Computational Number Theory 66 2011-09-01 21:55 Raman Math 1 2010-02-16 21:25 T.Rex Math 7 2009-03-13 10:46

All times are UTC. The time now is 21:45.

Sat Jan 22 21:45:22 UTC 2022 up 183 days, 16:14, 0 users, load averages: 1.69, 1.52, 1.38