The twin primes we are talking about here are not the regular twin primes (i.e. with a gap of 2) but the prime numbers with a gap of +-n(number of primes used in the calculation as gap). Anyway, thanks for the insight.

]]>hemiboso wrote:

primesdemytified.com/twinprimes

The correct spelling for that link is http://primesdemystified.com/twinprimes

]]>Thanks for the insight, if I got plenty of free time surely I would do it.

To hemiboso, thanks for the input. It seems interesting.

]]>1. Narrow the field to natural numbers ≡ to {1,7,11,13,17,19,23,29} modulo 30 (oeis.org/A007775). This infinite sequence is commonly known as “numbers not divisible by 2, 3 or 5,” and by definition contains all prime numbers > 5 and their multiplicative multiples. Thus we exclude prime numbers 2, 3 and 5 from our analysis, and the two pairs of twin primes that 3 and 5 are members of: (3,5) and (5,7).

2. Populate a modulo 30 factorization wheel with the above-defined sequence where 1 = 12°. Upon doing so, numbers ≡ to {1,7,11,13,17,19,23,29} modulo 30 are evenly distributed along 8—and only 8—radii: {12°, 84°, 132°, 156°, 204°, 228°, 276°, 348°} and have a repetition cycle of 1{+6+4+2+4+2+4+6+2} {repeat…}. Each rotation around the wheel increments a difference sequence of +30 (for example, numbers ≡ {1} modulo 30 increment as follows: 1, 31, 61, 91, 121, 151, 181 … ). And therefore, in digital root terms, every rotation around the wheel increments each of the 8 radii by +3.

3. Upon completing Step 2, we see that the twin prime candidate field can be further reduced given that numbers radiating at 84° (or numbers ≡ {7} modulo 30) and 276° (or numbers ≡ {23} modulo 30) cannot possibly be twin primes given the closest prime numbers in proximity to numbers ≡ {7} modulo 30 is +4 and for numbers ≡ {23} modulo 30 is -4. We have now winnowed the field of twin prime candidates to numbers ≡ {1,11,13,17,19,29} modulo 30 (oeis.org/A230462) which has a repetition cycle of 11{+2+4+2+10+2+10+2} {repeat…}. The sequence that remains, when consolidated into a single number line, accounts for exactly 20% of natural numbers and consists exclusively of twin prime candidates (n, n+2), starting with (11,13).

4. We now note, given that each rotation around our sieve increments 8 elements +30 {repeat …}, the digital root sequencing of each radius increments by digital root +3. Thus, the digital root sequencing of the 8 radii have a deterministic dependence upon the initial digital root state of the first 8 elements of the sequence where 1, 7, 11, 13, 17, 19, 23, 29 translates to digital roots 1, 7, 2, 4, 8, 1, 5, 2. The 8 radii thus sequence as:

numbers ≡ {1} modulo 30 sequence as {1,4,7} (or 1+3=4; 4+3=7; 7+3=1; repeat ... you get the drill ...)

numbers ≡ {7} modulo 30 sequence as {7,1,4}

numbers ≡ {11} modulo 30 sequence as {2,5,8}

numbers ≡ {13} modulo 30 sequence as {4,7,1}

numbers ≡ {17} modulo 30 sequence as {8,2,5}

numbers ≡ {19} modulo 30 sequence as {1,4,7}

numbers ≡ {23} modulo 30 sequence as {5,8,2}

numbers ≡ {29} modulo 30 sequence as {2,5,8}

5. As stated in Step 3, for the purposes of examining twin prime digital root sequencing, we can ignore numbers ≡ {7, 23} modulo 30, leaving us with numbers ≡ {1,11,13,17,19,29} modulo 30, and their corresponding deterministic digital root sequencing:

numbers ≡ {1} modulo 30 sequence as {1,4,7}

numbers ≡ {11} modulo 30 sequence as {2,5,8}

numbers ≡ {13} modulo 30 sequence as {4,7,1}

numbers ≡ {17} modulo 30 sequence as {8,2,5}

numbers ≡ {19} modulo 30 sequence as {1,4,7}

numbers ≡ {29} modulo 30 sequence as {2,5,8}

When we pair these as n, n+2 dyads (twin prime candidate couplings) we see that:

Numbers ≡ {11,13} mod 30 sequence as:

(11,13) = digital roots {2,4}

(41,43) = digital roots {5,7}

(71,73) = digital roots {8,1}

{digital roots repeat …}

Numbers ≡ {17,19} mod 30 sequence as:

(17,19) = digital roots {8,1}

(47,49) = digital roots {2,4}

(77,79) = digital roots {5,7}

{digital roots repeat …}

Numbers ≡ {29, 1} mod 30 sequence as:

(29,31) = digital roots {2,4}

(59,61) = digital roots {5,7}

(89,91) = digital roots {8,1}

{digital roots repeat …}

And thus we conclude that all twin prime candidates of the form n, n+2 greater than (5,7) that are potentially p, p+2 distribute to one of three digital root dyadic sequences: {2,4} (oeis.org/A232880), {8,1} (oeis.org/A232882) or {5,7} (oeis.org/A232881) (and you’ll note that these decompose to {6,9,3}, the vertices of one of three rotating equilateral triangles, along with {1,4,7} and {2,5,8}, that interact to form tensor matrices representing the coordinates of {9/3} star polygons … but that’s another story …

Trial division would be trivial to parallelize, but is basically worthless. I see a paper by Asaduzzaman et al. from 2014 saying they have sped it up on GPUs, but (1) that's not hard, and (2) their comparison CPU code is 100x slower than the single-core CPU code I use, making their 90x speedup claim dubious. One thing that bothered me at GTC was the uncertainty around speedup numbers -- it's easy to get 100x speedup if you write cruddy CPU code in a weekend and then compare to GPU code you had four people working 6 months on.

AKS should be pretty easy to run in parallel (each of the *s* tests are independent), and the code that takes 99% of the time is pretty simple. You need to do lots and lots and lots of *s += (a * b) % n* type operations. Some problems:

The growth rate difference means ECPP or APRCL on a single host will beat the hundreds of thousands of GPU cores running AKS. If the serial algorithm takes many trillions of years, how many cores will we need to make it run in an hour? Do you have that many GPUs?

There is no certificate, so realistically your saying you ran this is no better than just saying you used well-known software to run BPSW + a Frobenius test + some number of random-base M-R tests. Less for me because I've seen too many broken AKS implementations. It doesn't matter how fast it is if it isn't correct.

There may be other tricks for AKS that can help, but you have to make major changes to it to get it to the same growth rate as APR-CL or ECPP. There are definitely some research opportunities here.

The BLS75 methods involve factoring, so won't scale to usefully large numbers.

I don't know how well APRCL would parallelize. I think there was a thesis about the subject, but it didn't give much detail.

ECPP certainly could benefit if you could write it. If you do, please make it open source and publicize it. That would be a major accomplishment of use to many people. There are quite a few places where things could run in parallel (the fanout is extremely large if you run speculatively).

]]>I think having a computer with GPU processing units (NVIDIA Tesla) would make it faster due to the fact it has thousand cores per GPU. I am still working on building one with multiple GPUs, got to wait until the GPU price going down after sometimes.

]]>100 digit primes can be proved extremely fast (a few milliseconds). 1000 digits will take ~2-8 minutes. For ECPP and APR-CL the time increases at about the 4th power of the number of digits (for AKS it's the 6th power). By 20k digits, expect 3 months using all cores of a 4- or 6-core machine.

I'm not sure about the various DR-restricted numbers, but the first set of unrestricted (post 109) are fairly small. E.g. p=29 => n=932651 is 213 digits, p=31 => n=2547137 is 242 digits. They grow of course, as p=59 => n=4183583 is 469 digits.

]]>

Thanks for the info. I think I need to upgrade my computing power to do the job.

]]>