20211103, 18:28  #45  
Jan 2018
5×17 Posts 
Quote:
In my words, how I understand it: The idea is to set up a tree of nodes where each node (= a product of more and more primes) is computed once and used to determine the remainder of that node to the interval start ( say IntStart= M*P(x)#/D25*P(x)). The tree has levels as Jens described in the link you gave, where the base level is made up of nodes consisting of the product of say 10 primes each. Node(level=0,node=1)=P(1)*P(2)*P(3)*...*P(10)=6469693230 Node(level=0,node=2)=P(11)*P(12)*P(13)*...*P(20) Node(level=0,node=3)=P(21)*P(22)*P(23)*...*P(30) Node(level=0,node=4)=P(21)*P(22)*P(23)*...*P(30) Level 1 has the multiplied nodes of level 0, say: Node(level=1,node=1)=Node(0,1)*Node(0,2) Node(level=1,node=2)=Node(0,1)*Node(0,2) Level 2 has the multiplied nodes of level 1, say: Node(level=2,node=1)=Node(1,1)*Node(1,2) And assume Node(2,1) is in the order of sqrt(IntStart) (you have to build a tree with this in mind) Now determine IntStart%Node(2,1) = R(2,1). Use this remainder R(2,1) to determine: R(1,1)=R(2,1)%Node(1,1) R(1,2)= R(2,1)%Node(1,2) And move to the lowest level: R(0,1)=R(1,1)%Node(0,1) R(0,2)=R(1,1)%Node(0,2) R(0,3)=R(1,2)%Node(0,3) R(0,4)=R(1,2)%Node(0,4) Now determine the remainder of the individual primes (eg R(0,1)%3), so you can use that remainder to start crossing off the candidates in the prime gap interval. This in a nutshell, hope it is clear. From experience I can say it works really well for big numbers. Quote:
By the by: NP = x^2+2kx is the formula for all nonprimes, with x a whole number [3.> and k a whole number [0,> Use graph.exe to show you a grafic representation of that formula. Also nice, let graph.exe show the equation NP = x^2+2kx (in the 4th quadrant, where k is negative). This shows where Fermat got his idea for NP = X^2  Y^2. Based on the formula NP = x^2 + 2kx, you can be more exact: NP + k^2 = x^2 + 2kx + k^2 = (x+k)^2 NP = (x+k)^2  k^2. Another way of coming to this formula is: NP = x * y (x and y whole numbers [3,> Say x<=y and y is odd then y = x + 2k with k a whole number [0,> Then NP = x (x + 2k) = x^2 + 2kx Note: The formula for the nonprimes (NP = x^2 + 2kx) moves asymptotically to k=1/2x and since that is the place where no NonPrime will ever be, it seems like a good place to look for primes in the imaginary mathematical world. My point: the Riemann critical line is the intrinsic property of the primes. The better question is: what is the relation between the Riemann zero's and the primes themselves? Can it be used to determine the actual primes? if anybody gets inspired and proves the Riemann Hypothesis by this, at least mention me in your proof, A nice share in the prize money in the order of USD 100.000 would do nicely as well! Kind regards Michiel 

20211104, 06:26  #46 
Mar 2021
59 Posts 
The advantage of my approach is that you can do much better than Sieve of Eratosthenes. When using a wheel with the first 250 primes, only about 1 in 13 numbers can be prime. It's even better than this when using deficient primorials. My sieving method allows you to only sieve numbers which aren't already eliminated by the primorial. The Sieve of Eratosthenes requires eliminating all elements except the even numbers so you end up having to remove about 8 times more elements.
I think you are sieving for one multiplier at a time. Are you recomputing the mods for each multiplier? The mods only need to be computed once. If I was going to sieve one multiplier at a time I would use the following: Compute A*P#/Divider%p, for each prime p Compute P#%p, for each prime p and use this to adjust the starting position from one multiplier to the next. Using the example from before: A*11#/6, A = 1, 7, 13, ... with p = 13 1*11#/6%13 = 8, so for A = 1 we can remove 5, 31, 57, ... and 21, 47, ... 11#%13 = 9, so each time we move to the next multiplier we just need to add 4 to the previous numbers. For 7*11#/6 we start with 9, (7*11#/6 + 9)%13 = 0 For 13*11#/6 we start with 13 
20211104, 07:57  #47  
Jan 2018
85_{10} Posts 
Quote:
you are correct. I do make too many calculations atm, mainly because I do not keep to one divider and also because I do not search one primorial at the time, but go through a wide range of those. The optimizations you (and Seth) are using, make sense if the search is more limited in P(x)# and D. You find much more 30+ gaps than I do, so you guys must be doing something right ;) This is also why I like the article (and the insights) of Seth. I will incorporate those ideas into my new approach. There are some other ideas I would like to explore, one has to do with a more efficient number presentation: there are 8 candidates that remain in a wheel of 30. You can represent them as a matrix of 8 by N elements. The 3rd element of the 11th byte represents 11 + 11*30 = 341 (Note 8 candidates represented as 0 or 1 make up one byte). Sieve each bit separately in an interval and you have a better parallel sieving method that I think can work on GPU. Changing to a wheel of 210 gives 48 candidates, but I am under the impression that a SMT has 64 cores, so what to do with the remaining 16 cores? Anywayz, interesting times! And one more thing about NP = x^2 + 2kx: if k = 1/2 x + 1/2 then NP = x^2 + 2x(1/2x + 1/2) = x And k = 1/2 x  1/2 then NP = x^2 + 2x(1/2x  1/2) = x Here you will find the trivial zero's. 

20211104, 14:58  #48 
Mar 2021
59 Posts 
I always wondered why Seth claimed a factor of 10000 improvement. I would have expected less than 10. Recomputing the mods probably explains it.
In my sieve I use 1 bit per multiplier per possible prime offset so memory use is as efficient as possible. There are a couple of ways to parallelize. You can have each threadblock work on a different set of possible prime offsets. You can have each threadblock work with a different set of primes. There might be others. 
20211104, 18:35  #49  
Jan 2018
5×17 Posts 
Quote:
it is not so much about the storage of the in essence boolean value for candidate or composite, but sieving on more gpu cores at the same time. I don't know how to make this clear yet. I will let this sink in and let it stew for a while. Do some tests and come back on the sieving part. Maybe a varied approach should be in order, one for fixed P(x)# and div, and another for broader searches. Thanks for thinking along and sharing! Appreciated Kind regards michiel 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
HTML5 prime number searching?  Dale Mahalko  Software  7  20150321 19:55 
Elementary Literature on probabilistic aspects of prime searching  hhh  Math  7  20140318 14:37 
Question about multicore prime searching.  Trilo  Riesel Prime Search  33  20130919 21:21 
idea for twin prime searching  MiniGeek  Twin Prime Search  8  20110130 00:18 
Searching for user BlueSoda (no its not a prime)  ltd  Prime Sierpinski Project  3  20060323 19:27 