Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I will use some simple arguments on a prime numbers formula that has been deterministically checked by computer. I would like to compare this result with others you already know.

The set of all natural numbers up to some number E is identical to the set formed by the unions of all primes and its multiples up to E. Therefore, the number of elements in both sets must be the same. Notation:

1) $p_{i}$ is the i-th prime

2) $D(p{_k})$ is the set comprising all the prime numbers up to $p{_k}$

3) $W(A)$ is the set of all subsets of the set $A$

4) $V(W)$ is the function that gives the product of all the elements of $W$

5) $n(A)$ is the function that counts the elements of the set $A$

Note that the number of multiples of $a$ up to $E$ is given by $\lfloor\frac{E}{a}\rfloor$ The result of the discussion above is that, for every E:

$\displaystyle\sum\limits_{A \subset W(D(p{_k}))} (-1)^{1+n(A)} \left \lfloor \frac{E}{V(A)} \right \rfloor = E - 1$

Note that this is the straightforward use of the inclusion-exclusion principle on the left side of the equation, while the right side is the simple statement of the fact that the number of natural numbers up to $E$ is $E$. However, since we consider the prime numbers start with 2, the union of the sets of all primes and its multiples are equal to the natural numbers equal or greater than 2, and because of this we need to subtract one from $E$ (the set of non-zero natural numbers starting from 2 up to $E$ have $E-1$ elements). The formula above holds as long as $D(p{_k})$ is the set of all primes up to $E$. However, if there is at least one prime missing, this equality will necessarily not hold (since this number would not be multiple of any other prime, and the union of all the sets of primes and its multiples up to $p{_k}$ wouldn't be equal $A$ anymore).

As a consequence, the least natural $E$ for which the above equality does not hold is the next prime after $D(p{_k})$ (and the difference between them is unitary). Therefore $p{_{k+1}}$ is the least integer that satisfies the equation below):

$\displaystyle\sum\limits_{A \subset W(D(p{_k}))} (-1)^{1+n(A)} \left \lfloor \frac{p{_{k+1}}}{V(A)} \right \rfloor = p{_{k+1}} - 2$

A simple case is:

$\left \lfloor \frac{3}{2} \right \rfloor = 1 \\$ While $3-2=1$ also.


$\left \lfloor \frac{7}{2} \right \rfloor + \left \lfloor \frac{7}{3} \right \rfloor + \left \lfloor \frac{7}{5} \right \rfloor- \left \lfloor \frac{7}{6} \right \rfloor- \left \lfloor \frac{7}{10} \right \rfloor- \left \lfloor \frac{7}{15} \right \rfloor + \left \lfloor \frac{7}{30} \right \rfloor= 5 \\$ While $7-2=5$ also.

This seems an approach very similar to that of other sieves, but it focus on obtaining the next prime instead of the number of primes on a given interval. Is this worth anything?

share|cite|improve this question

1 Answer 1

I propose the following Matrix Sieve for finding prime numbers: Positive integers not contained in two 2-dimensional arrays: P1(i,j)=6i^2-1+(6i-1)(j-1) and P2(i,j)=6i^2-1+(6i+1)(j-1) are indexes p of all prime numbers in the sequence S1(p)=6p+5, p=0,1,2,... Positive integers not contained in two 2-dimensional arrays: P3(i,j)=6i^2-2i-1+(6i-1)(j-1) and P4(i,j)=6i^2+2i-1+(6i+1)(j-1) are indexes p of all prime numbers in the sequence S2(p)=6p+7, p=0,1,2,..; i,j=1,2,3,...

share|cite|improve this answer
Please use formatting – Shailesh Oct 7 at 12:21
Also, this does not answer the question: the OP is asking for comments on the sieve presented by him, whereas you are merely proposing a different sieve. – Hrodelbert Oct 7 at 12:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.