Problems & Puzzles: Puzzles

Puzzle 820. The  Sunduram's sieve In 1934 S. P. Sunduram devised the following was of sieving prime numbers 1) Construct the first row of numbers in A.P. starting in 4 and common difference 3: 4, 7, 10, 13,... 2) Make the first column as the first row 3) All the rest of the rows are in A.P.'s as the first one but the common difference are 5, 7, 9, 11, ..., respectively Here is a sketch of the matrix you will  got: 4 7 10 13 16 ... 7 12 17 22 27 ... 10 17 24 31 38 ... 13 22 31 40 49 ... 16 27 38 49 60 ... ... ... ... ... ... ... And the "primality rules" are, simply: Every number x present in the table produces a composite number 2x+1. Every number x not present in the table produces a prime number 2x+1. Q1. Explain why these rules work. Q2. Show that all the primes numbers greater than 2 are generated by this matrix & rules. Q3. Construct a simple and efficient algorithm to compute if a given integer X is or not in the table.

---

Contributions came from Jan van Delden, John Arioni and Vicente Felipe Izquierdo.

***

Jan wrote:

A general value in the table: A[i,j]=A[i,1]+(2i+1)*(j-1).

 

A[i,j] mod (2i+1) =  A[i,1] mod (2i+1) = i mod (2i+1)

2*A[i,j]+1 mod (2i+1) = 2i+1 mod (2i+1) = 0 mod (2i+1)

So the numbers 2x+1 are composite.

 

II)

 

For a number x not present in the table we have:

For all i<x:   x mod (2i+1) <> i mod (2i+1) [Otherwise x would be in row i]

For all i<x: (2x+1) mod (2i+1) <> 0 mod (2i+1)

So 2x+1 is an odd number not divisible by an odd number in [3..2x-1] and therefore prime.

 

Q2:

 

Suppose p is an odd prime, p=2x+1.

Then p mod (2i+1)<>0 mod (2i+1) for all i such that 3<=(2i+1)<p or  1<=i<x.

Therefore x is not present in row 1 .. x-1.

Also x can't be present in row i>=x, because A[i,j]>=A[i,1]=3i+1>3x>x

So if p is an odd prime it corresponds to an x which is not present.

 

Q3:

 

Use the fact that A[i,j]=A[j,i]. If present all values i<j are allready detected.
In row i we could start searching from the value A[i,i]=2i(i+1).
Solving A[i,i]=x gives i=(sqrt(2x+1)-1)/2
 

A simple algorithm in (quasi) c, upperbound based on A[i,i]

 

upbi=trunc((sqrt(2x+1)-1)/2);

present=false;

residue=1;

modulus=3;

i=1;

while (i<=upbi) do {

  if (x % modulus == residue) {

    present=true;

    break;

  }

  i+=1;

  residue+=1;

  modulus+=2;

}

present;

 

I included the variable residue for readability.

 

The maximum number of tests in this algorithm is (sqrt(2x+1)-1)/2.
In standard trial division the maximum number of tests is pi(sqrt(2x+1))-1.

For small values of x (x<138) this algorithm will outperform trial division:

 

 

...

My general impression (hope it's correct..)
 

I think Sunduram's sieve is based on an elegant idea. Generating the sieve is easy. The next row in the table can be computed without first calculating/searching numbers with a special property (like primes). The drawback are the rows (/columns) where one computes i mod (2i+1) where 2i+1 is not prime. That's where it loses efficiency compared to the sieve of Eratostenes. 

 

On the other hand, my given algorithm could be further improved, to exclude these tests on composite 2i+1, by first testing if i is in the table (at the cost of being more complex). 

If one wants to extend the sieve of Eratostenes using a wheel, say mod 2,3,5, one has to precompute residues mod 30. Sunduram's sieve is easily adjusted for numbers not equal to 0 mod {2,3,5}. Just skip the first two rows! So less headache to implement.

 

***

John wrote:

h & H: little eich and BIG EICH

Let q = (2n+1) be the generic odd integer (n =1,2,3,....).

The notations h(q) = n and H(q)= (n+1) will be helpful in the following .

Trivially: h(q)+H(q)=q.

                 h(q) = (q-1)/2 ; q = 2*h(q) + 1

                H(q) = (q+1)/2 ; q = 2*H(q) - 1

Q1 + Q2 :

The generic odd multiple of 3 is  (6n+3), and   h(6n+3) = 3n+1 – i.e. row 1 of the table

The generic odd multiple of 5 is (10n+5), and h(10n+5) =5n+2 – i.e. row 2

The generic odd multiple of 7 is (14n+7), and h(14n+7) =7n+3 – i.e. row 3

And so on …....

The entries of the matrix are h(any odd composite integer)

If p is a prime number then x = h(p) is not present in the matrix, so: p =2*h(p)+1 = 2x+1.

Alternately we could construct the following matrix :

row 1: 5 8 11 14 17 …..

row 2: 8 13 18 23 28 …..

row 3: 11 18 25 32 39 …..

…...........................................

where we have H(6n+3) in row 1, H(10n+5) in row 2 , H(14n+7) in row 3 ,…......

Every number x in the new matrix produces a composite number 2x-1 and every number x not present in the matrix is the BIG EICH of some prime, then x produces a prime number 2x-1 as p = 2*H(p)-1 = 2x-1.

Q3
Entries in the matrix of the puzzle (say matrix A) are the little eiches (h) of the odd composite numbers.

Since the product (2r + 1)*(2c + 1) = 4rc + 2r + 2c +1 [ r = 1,2,3, … c = 1,2,3, …. ] describes the generic odd composite integer, and h(4rc + 2r + 2c +1) = 2rc + r + c , the value of the generic entry A_rc of the matrix is:                                                                  A_rc = 2rc + r + c          [*]  

Exchanging r and c, [*] produces identical values, then the matrix is symmetric

[*] can produce every integer 3n+1 (all of these numbers are already present in row 1), because h(6n+3) = 3n+1 and, of course, 6n+3 is composite.

The values that [*] does not produce are among the integers of the kind 3n-1 or 3n because a prime number can be a 6n-1 or a 6n+1 and: h(6n-1) = 3n-1 ; h(6n+1) = 3n

To compute if a given x = 3n-1 or a given x = 3n is present or not in the matrix the following is a simple algorithm:

a) input: x

b) if x is congruent to 1(mod 3) then thereis = true - exit

c) set: r = 2 thereis = false

d) compute [*] for c = r, r+1, r+2, r+3, ….. until [*] >= x

e) if [*] = x then thereis = true - exit

      else

         r = r + 1

     end if

f) if r is congruent to 1(mod 3) then r = r+1

g) [*] = 2rr + r + r

h) if [*] = x then thereis = true - exit

       else

        if [*] > x then exit

          else

            goto d)

         end if

       end if

Why step f) in the algorithm:

for r = (3a + 1), [*] becomes: 2c(3a + 1) + (3a + 1) + c = 6ac + 3a + 3c + 1 that are values congruent to 1 (mod 3), but the algorithm is devised to find numbers like x = 3n-1 or x = 3n.

Step d): c = r, r+1, r+2, r+3, ….. instead of c = 1, 2, 3, 4 ….. because the matrix is symmetric,

***

Vicente wrote:

Q1. The numbers of matrix are of form:   x= 4+3 (r+c)+2 r c, when r->Row and c->Column in the matrix. Q1, rule 1: 2x+1 is composite because 2x+1=9+6(c+r)+4 c r = (3+2c)(3+2r).

***