Sundaram’s sieve and 2n+1 prime

Posted on January 28, 2015 by Sumant Sumant

If the number n is present in sieve then 2n+1 is not prime, else it is.

The sieve is \begin{bmatrix} 4&7&10&13 \\ 7 &12&17&22\\10&17&24&31 \end{bmatrix}

Let (a,b) represents the term in the above sieve. So along the x-axis we have a and along y-axis we have b. The common difference along x-axis is a. The common difference along y-axis is b. The first number is 4. So if we first go down we have 4+(b-1)3 = 4+3b-3 =3b+1. At the same time the common difference across the x axis starting from this point will be 3+(b-1)2 = 3+2b-2 =2b+1. Thus along horizontal axis the term (a,b) will be 3b+1+(a-1)(2b+1) = 3b+1+2ab-2b+a-1 = b+2ab+a.

Now 2(a.b)+1 = 2(b+a+2ab)+1 = 2b+2a+4ab+1 = 2b(1+2a)+2a+1 = (2b+1)(2a+1)

Thus we see that if the number happens to be in the sieve then 2n+1 happens to be a non-prime.

Next we must show that if the number N is not in the sieve, then 2N+1 is a prime. Or by contrapositive if 2N+1 is not prime then N is in the sieve. Suppose 2N+1=a\cdot b, where a,b \in \textbf{N}. Since 2N+1 is odd this means both a,b are odd. Let a= 2m+1 and b = 2n+1. Therefore 2N+1 = (2m+1)(2n+1) = 4mn+2(m+n)+1 \Rightarrow 2N=4mn+2(m+n) \Rightarrow N = 2mn+(m+n) = (2n+1)m+n. This means that N appears as the (m,n) entry in the sieve. Note it could also be (n,m) entry in the sieve.

About Sumant Sumant

I love Math and I am always looking forward to collaborate with fellow learners. If you need help learning math then please do contact me.
This entry was posted in Prime Numbers, Sequences and tagged . Bookmark the permalink.

Leave a comment