Permalink Submitted by gasbion@gmail.com on August 10, 2018

An explanation plus the equation to test primality

By numbering by two Natural numbers, the first in odd numbers and the second in even numbers are arranged in two columns, giving rise to the following positions: p Odd Even

0 1 2

1 3 4

2 5 6

3 7 8

4 9 10

5 11 12

6 13 14

7 15 16

8 17 18

9 19 20

10 21 22

.....................

The following relation exists between the positions corresponding to the composed numbers and the numbers themselves:

opportunely reiterated it can develop, through simple programs, all the positions occupied by numbers composed up to a given n and, therefore, also all those missing corresponding to prime numbers:

Positions occupied by numbers composed by n between 3000001 and 3000100 obtained through the above report with repetitions:

As p varies from one to six in the figure, the table provides all but the composed numbers, we can also note that there is a relationship between 3 and 1, 5 and 2, and so on: if we call "a" the first term, the second will be equal to the whole part of division by 2 of a: ap + int (a / 2). It is natural to wonder if the positions other than those above, which we remember give us those of all and only the composed numbers, will give all the positions of the prime numbers, unfortunately as it was easy to expect is not so:

It is interesting to note, however, that some of the positions belonging to the second table are not present in the first, while others are common to both. It is also obvious that a similar relation is valid for the second table: a'p + a '/ 2 between 2 and 1, 4 and 2 respectively, and when there is not an "a" for which the following linear relation, although parametric, is valid the position a'p + a '/ 2 will indicate a number definitely prime with a' belonging to the subset of the even numbers of the Naturals and a to the subset of the odd numbers of the Naturals, the position p can be arbitrarily fixed in a'p + a ' / 2 and vary appropriately in the set of Naturals in ap + int (a / 2):

ap+int(a/2)=a’p+a’/2

For example, we set p = 12 and a '=4 in a'p + a' / 2 we will have:

ap + int (a / 2) = 50 not verifiable for each a in the odd numbers of the Naturals and p in the Naturals, position 50corresponds in fact to the prime number 101

again, fixed p = 2 and a '= 4 we will have:

ap + int (a / 2) = 10 verifiable for a = 3 and p = 3, position 10 corresponds to the composed number 21.

Position to be tested:987654321111

141093474444.0 7 3

time taken 0.0160000324249 secondi

Position to be tested: 10**30+1

3.44827586207e+028 29 14

time taken 0.0160000324249 seconds

Position to be tested: 10**30+11

2.70929287456e+026 3691 1845

time taken 0.0469999313354 seconds

Position to be tested: 10**30+13

Probable position of prime number

time taken 120.006000042 seconds

Above we have some examples of tests of the position with the relative execution times with a basic laptop, the first number is the value of p, the second of a and the third the whole part of a / 2, the time was limited to 120 seconds but in fact the last issue tested 2000000000000000000000000000027 is not prime.

## sundaram sieve

An explanation plus the equation to test primality

By numbering by two Natural numbers, the first in odd numbers and the second in even numbers are arranged in two columns, giving rise to the following positions: p Odd Even

0 1 2

1 3 4

2 5 6

3 7 8

4 9 10

5 11 12

6 13 14

7 15 16

8 17 18

9 19 20

10 21 22

.....................

The following relation exists between the positions corresponding to the composed numbers and the numbers themselves:

n p n+p n+p+n

3 1 4 7 10 13 16 ......................................

5 2 7 12 17 22 27

7 3 10 17 24 31 38

9 4 13 22 31 40 49

11 5 16 27 38 49 60

13 6 19 32 45 58 71

15 7 22 37 52 67 82

17 8 25 42 59 76 93

19 9 28 47 66 85 104

.............................................................................................

opportunely reiterated it can develop, through simple programs, all the positions occupied by numbers composed up to a given n and, therefore, also all those missing corresponding to prime numbers:

Positions occupied by numbers composed by n between 3000001 and 3000100 obtained through the above report with repetitions:

1500000, 1500000, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500001, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500002, 1500003, 1500003, 1500003, 1500003, 1500003, 1500003, 1500003, 1500003, 1500004, 1500005, 1500005, 1500005, 1500005, 1500005, 1500005, 1500005, 1500005, 1500005, 1500005, 1500005, 1500005, 1500005, 1500006, 1500006, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500007, 1500009, 1500009, 1500009, 1500009, 1500009, 1500009, 1500009, 1500009, 1500009, 1500010, 1500010, 1500010, 1500010, 1500010, 1500010, 1500011, 1500011, 1500011, 1500011, 1500011, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500012, 1500013, 1500013, 1500013, 1500013, 1500013, 1500015, 1500015, 1500016, 1500016, 1500017, 1500017, 1500017, 1500017, 1500017, 1500018, 1500018, 1500018, 1500018, 1500018, 1500018, 1500019, 1500019, 1500019, 1500019, 1500019, 1500019, 1500019, 1500019, 1500019, 1500019, 1500019, 1500019, 1500019, 1500020, 1500020, 1500020, 1500020, 1500020, 1500020, 1500020, 1500020, 1500020, 1500020, 1500020, 1500020, 1500021, 1500022, 1500022, 1500022, 1500024, 1500025, 1500025, 1500025, 1500025, 1500025, 1500025, 1500025, 1500025, 1500025, 1500025, 1500025, 1500026, 1500027, 1500028, 1500028, 1500028, 1500028, 1500028, 1500029, 1500029, 1500031, 1500031, 1500031, 1500031, 1500032, 1500032, 1500032, 1500032, 1500032, 1500033, 1500033, 1500033, 1500033, 1500033, 1500034, 1500034, 1500035, 1500035, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500037, 1500039, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500040, 1500041, 1500041, 1500042, 1500042, 1500042, 1500042, 1500043, 1500043, 1500043, 1500043, 1500043, 1500043, 1500043, 1500045, 1500045, 1500046, 1500046, 1500046, 1500046,]

All positions between the two limits (without repetitions):

[1500001, 1500002, 1500003, 1500004, 1500005, 1500006, 1500007, 1500008, 1500009, 1500010, 1500011, 1500012, 1500013, 1500014, 1500015, 1500016, 1500017, 1500018, 1500019, 1500020, 1500021, 1500022, 1500023, 1500024, 1500025, 1500026, 1500027, 1500028, 1500029, 1500030, 1500031, 1500032, 1500033, 1500034, 1500035, 1500036, 1500037, 1500038, 1500039, 1500040, 1500041, 1500042, 1500043, 1500044, 1500045, 1500046]

For difference the positions occupied by prime numbers:

[set([1500036, 1500038, 1500008, 1500044, 1500014, 1500023, 1500030])]

Being n = 2p + 1 we can substitute n in the relation that binds the above positions and numbers with 2p + 1, we obtain:

n p n+p n+p+n

3p+1 3 1 4 7 10 13 16 19 ..................................................

5p+2 5 2 7 12 17 22 27 32

7p+3 7 3 10 17 24 31 38 45

9p+4 9 4 13 22 31 40 49 58

11p+5 11 5 16 27 38 49 60 71

13p+6 13 6 19 32 45 58 71 84

......................................................................................................................................

Tabella 1

As p varies from one to six in the figure, the table provides all but the composed numbers, we can also note that there is a relationship between 3 and 1, 5 and 2, and so on: if we call "a" the first term, the second will be equal to the whole part of division by 2 of a: ap + int (a / 2). It is natural to wonder if the positions other than those above, which we remember give us those of all and only the composed numbers, will give all the positions of the prime numbers, unfortunately as it was easy to expect is not so:

2p+1 3 5 7 9 11 13 15 17 .........................................................

4p+2 6 10 14 18 22 26 30 34

6p+3 9 15 21 27 33 39 45 51

8p+4 12 20 28 36 44 52 60 68

10p+5 15 25 35 45 55 65 75 85

12p+6 18 30 42 54 66 78 90 102

.........................................................................................................................................

It is interesting to note, however, that some of the positions belonging to the second table are not present in the first, while others are common to both. It is also obvious that a similar relation is valid for the second table: a'p + a '/ 2 between 2 and 1, 4 and 2 respectively, and when there is not an "a" for which the following linear relation, although parametric, is valid the position a'p + a '/ 2 will indicate a number definitely prime with a' belonging to the subset of the even numbers of the Naturals and a to the subset of the odd numbers of the Naturals, the position p can be arbitrarily fixed in a'p + a ' / 2 and vary appropriately in the set of Naturals in ap + int (a / 2):

ap+int(a/2)=a’p+a’/2

For example, we set p = 12 and a '=4 in a'p + a' / 2 we will have:

ap + int (a / 2) = 50 not verifiable for each a in the odd numbers of the Naturals and p in the Naturals, position 50corresponds in fact to the prime number 101

again, fixed p = 2 and a '= 4 we will have:

ap + int (a / 2) = 10 verifiable for a = 3 and p = 3, position 10 corresponds to the composed number 21.

Position to be tested:987654321111

141093474444.0 7 3

time taken 0.0160000324249 secondi

Position to be tested: 10**30+1

3.44827586207e+028 29 14

time taken 0.0160000324249 seconds

Position to be tested: 10**30+11

2.70929287456e+026 3691 1845

time taken 0.0469999313354 seconds

Position to be tested: 10**30+13

Probable position of prime number

time taken 120.006000042 seconds

Above we have some examples of tests of the position with the relative execution times with a basic laptop, the first number is the value of p, the second of a and the third the whole part of a / 2, the time was limited to 120 seconds but in fact the last issue tested 2000000000000000000000000000027 is not prime.