2

Could someone explain me why this arithmetic of sets can not be called a Prime Numbers formula? Was it already found before and is not relevant?

Prime numbers sequence $\mathbb P$ (or set of members expressed as a sequence) is revealed from a combination of $5$ sets (where $k,i,j\in \mathbb N$)

  • Let the set $\{a_k\}$ be defined by $a_k=6k-1$.
  • Let the set $\{b_k\}$ be defined by $b_k=6k+1$.
  • Define the sets $\{o_{1,i,j}\}$ and $\{o_{2,i,j}\}$ and $\{o_{3,i,j}\}$ be defined as $o_{1,i,j}=(6i-1)(6j+1)$ and $o_{2,i,j}=(6i-1)(6j-1)$ and $o_{3,i,j}=(6i+1)(6j+1)$.

Then, we can write the set of primes as $$\mathbb P = \{a_k\} \cup \{b_k\} \setminus \{o_{1,i,j}\} \setminus \{o_{2,i,j}\} \setminus \{o_{3,i,j}\}$$

Thank you for your answers. It is clear for me now.

T.Kalnius
  • 35
  • 1
    Are you saying that the set of primes can be constructed from the set of integers of the form $6k\pm 1$ by throwing away numbers of the form $(6i+1)(6j+1), (6i+1)(6j-1), (6i-1)(6j-1)$? – fretty Jun 15 '16 at 12:39
  • 3
    I don't quite understand your definition, but perhaps you'll find the sieve of eratosthenes relevant. – goblin GONE Jun 15 '16 at 12:39
  • 1
    Your set appears to omit $2$ and $3$. – Cameron Buie Jun 15 '16 at 12:42
  • Fretty, Yes, that is exactly what i am saying – T.Kalnius Jun 15 '16 at 12:42
  • Apart from your construction omitting $2$ and $3$ this works, but it is quite clear why since every composite integer that is $\pm 1 \bmod 6$ must be a product of two such integers. However your construction isn't really a "formula"...If I want the $n$th prime you haven't given me an expression to put $n$ into that tells me it. You must run the algorithm (which is really just the Sieve of Eratosthenes). – fretty Jun 15 '16 at 12:49
  • Closely related: Counting primes by counting numbers of the form $6k\pm 1$ which are not prime. It is well known that all primes $\gt 3$ are of the form $6k\pm 1$, so if we account for primes $2,3$ separately, your idea of eliminating all non-primes and identifying what remains as the primes $\gt 3$ is correct but (1) not what most would expect of a "Prime Numbers formula" and (2) "already found before". – hardmath Jun 15 '16 at 12:53
  • It doesn't give you the $n$th prime number, now does it? (i.e., input $n$, output $p_n$). – barak manos Jun 15 '16 at 14:15

4 Answers4

3

What you have described is essentially a prime sieve with a 6th order wheel, so it will indeed contain exactly the prime numbers congruent to $\pm1\mod6$, that is, all primes except for $2$ and $3$. I would not call it a "formula" for prime numbers, but you could certainly use it to implement an algorithm that generates primes up to a given limit (ie. the Sieve of Eratosthenes).

sbares
  • 4,063
2

Your equation for the primes is nearly true - it excludes $2$ and $3$, but is otherwise the prime numbers. The only lemma one needs to prove this is the following:

If $n$ is an integer not divisible by $2$ or $3$, then it is either of the form $6k+1$ or $6k-1$.

This tells you that every prime other than those two is in either $\{a_k\}$ or $\{b_k\}$. It also tells you that, for any composite number $n=6k\pm 1$ with $n=ab$, we have that $a$ and $b$ are both of the form $6k\pm 1$ as well, since $2$ and $3$ do not divide $n$ and thus do not divide any divisor of $n$ as well.

This is mostly just a way to speed up the sieve of Eratosthenes, since, to check if a number is prime, you still have to check whether a bunch of numbers divide it. That is, checking whether a given number is in $\{o_{1,i,j}\}$ requires considerable computation. In particular, it's not obvious from this formulation that there's even infinitely many primes, so it seems a bit much to say this is a formula for the primes. The main difficulty in calculating primes is that the structures of the sets $\{o_{n,i,j}\}$ are difficult to describe.

Milo Brandt
  • 60,888
0

Hope this helps with regards to whether it was previously found:

2 and 3 might be referred to as the two "forcibly prime numbers" since there are no integers greater than 1 and less than or equal to their respective square roots. Not a single trial division ever needs to be done for 2 or 3, so they are disqualified from the outset from any attempt to belong to the set of composite numbers. 2 and 3 are thus the only consecutive primes. Since any further prime needs to be coprime to both 2 and 3, they must be congruent to 5 or 1 (mod 2*3) and thus must all be of the form (2*3)*k -/+ 1 with k >= 1. When both (2*3)*k - 1 and (2*3)*k + 1 are prime for a given k >= 1, they are referred to as twin primes (3 and 5 being the only twin primes of the form (2*2)*k - 1 and (2*2)*k + 1). - Daniel Forgues, Mar 19 2010 Link - OEIS.org

Marc Hire
  • 1
  • Please format using Mathjax. It makes reading your answer much easier. See http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference for a quick tutorial. Cheers. – M47145 Jun 18 '16 at 20:51
0

I proposed "matrix sieve" algorithm for finding primes:

Positive integers which do not appear in both arrays $A1(i,j)=6i^2+(6i−1)(j−1)$ and $A2(i,j)=6i^2+(6i+1)(j−1)$

                    |  6   11    16     21   ...|
        A1(i,j) =   | 24   35     46    57   ...|
                    | 54   71     88   105   ...|
                    | 96  119    142   165   ...|
                    |...  ...  ...   ...     ...|


                     |  6    13   20    27   ...|
         A2(i,j) =   | 24    37   50    63   ...|
                     | 54    73   92   111   ...|
                     | 96   121  146   171   ...|
                     |...      ...       ...        ...   ...|

are indexes k of primes in the sequence $S1(k)=6k−1$.

Positive integers which do not appear in both arrays $A3(i,j)=6i^2−2i+(6i−1)(j−1)$ and $A4(i,j)=6i^2+2i+(6i+1)(j−1)$

                           | 4       9     14       19.. |
                           |20      31     42       53...|
                           |48      65     82       99...|
                  A3(i,j)= |88     111     134      157..|
                           |...   ...      ...     ...   |

                    | 8      15      22     29 ..|
                    |28      41      54     
           A4(i,j)= |60     79       98     117..|
                    |104    129     154    179...|
                    |...    ...     ...     ...  |

are indexes k of primes in the sequence $S2(k)=6k+1$. As we can see the expressions for arrays A1-A4 differ in that way: columns 1 in arrays A1 and A2 are the same, but columns 1 in arrays A3 and A4 are different, so number of primes in the sequence S1(k) will be slightly bigger than number of primes in the sequence S2(k). But the ratio of number of primes in the sequence S1(k) to number of primes in the sequence S2(k) tends to be 1 for greater ranges. For example: ratio of number of primes in S1 to the number of primes in S2 for the range [5;190] ratio=21/19=1,105263; for the range [5;950] ratio=82/77=1,064935; for the range [5;4750] ratio=323/314=1,028662 .for the range [5;23750] ratio=1332/1307=1,019138;for the range [5;118750] ratio=5613/5579=1,006094; for the range [5;593750] ratio=24345/24284=1,002512 and so on... SEE [link ]http://www.planet-source-code.com/vb/scripts/BrowseCategoryOrSearchResults.asp?lngWId=3&blnAuthorSearch=TRUE&lngAuthorId=21687209&strAuthorName=Boris%20Sklyar&txtMaxNumberOfEntriesPerPage=25

Boris Sklyar
  • 107