Generating Prime numbers
There are many ways by which the prime numbers can be identified. But no method is uniquely suitable for the entire range of numbers. The method due to Eratosthenes (276 – 194 BC), another Greek scholar is little different, however, it is laborious for higher prime numbers. It is called “Sieve of Eratosthenes“
Sieve of Eratosthenes
All numbers up to a number N, below which all the prime numbers would be identified were written in a form of matrix. Eratosthenes, at first crossed out (actually punched the numbers with wax) all numbers divisible by 2,of course excluding the number 2, as it is the first prime number. Of the remaining uncrossed numbers, he next crossed out all the numbers divisible by 3 (excluding 3). Likewise, leaving the successive prime numbers 5, 7, 11, 13.......and its multiples were crossed out. The numbers that remained after the successive crossing were the prime numbers in natural series. This can be performed in many different ways, which depend upon the arrangement of the number arrays. One such example is given below the numbers in natural series are arranged in a manner so that consecutive six numbers fall in a row.
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36
37 38 39 40 41 42
43 44 45 46 47 48
49 50 51 52 53 54
55 56 57 58 59 60
61 62 63 64 65 66
67 68 69 70 71 72
73 74 75 76 77 78
79 80 81 82 83 84
85 86 87 88 89 90
91 92 93 94 95 96
97 98 99 100 101 102
103 104 105 106 106 108
109 110 111 112 113 114
115 116 117 118 119 120
121 122 123 124 125 126
127 128 129 130 131 132
Cross out vertically all the numbers under the column 2, 3, 4 and 6 excluding 2 and 3, as they are all divisible by 2 and 3. Cross out all the numbers divisible by 5 except 5 diagonally. Similarly cross out all the numbers divisible by 7 from 49 diagonally. Then cross out every 11 th integer from 121, 13 th integer from 169, 17 th integer from 289 and so on, as they are divisible by the respective prime numbers. It is observed that all the prime numbers fall either in the first or in the fifth column. In striking out the numbers, we find that some numbers are struck twice or even thrice. This repetition is partially reduced with the help of the fact that for primes up to N, we need to cross out all the numbers that are multiples of the primes from 2,3,5,7...... upto all primes within √ N. For example, if N = 100, we need not cross out multiples of 11, since 11 > √ 100 .
Accidental coincidence
It is mostly fluke and hence that cannot be accounted by any mathematics. Prime numbers are all odd, which demands at first that, whatever may be the structure of the relation designed for the generation of prime numbers, it must give only odd numbers. All the odd numbers can be represented with the first two prime numbers 2 and 3 by its linear combinations. Since all the primes are odd in nature, they can be expressed by the linear combination of 2x + 3y, where x and y are any favourable set of integers. If 2x and 3y have any common factor or 2x + 3y is a multiple of 5, then such unfavourable combinations yield composite numbers. When squares of any two successive numbers are added or subtracted it results with an odd number. Even though many such addition and subtraction give primes, there are some exceptions also. Few illustrations are given in Table.4.
Table.4. Addition/subtraction of squares
___________________________________
addition subtraction
___________________________________
12 + 22 = 5 22 - 12 = 3
22 + 32 = 13 32 - 22 = 5
........................ 42 - 32 = 7
42 + 52 = 41 ....................
52 + 62 = 71 62 - 52 = 11
........................ 72 - 62 =13
72 + 82 = 113 .....................
........................ 92 - 82 = 17
92 + 102 = 181 102 - 92 = 19
______________________________________
When 1 is added to or subtracted from 2n gives prime numbers for many smaller values of n. They are listed in Table .5.
Table.5 .Prime by 2n ± 1
_____________________________
n 2n + 1 2n – 1
______________________________
1 .....
2 5 3
3 .... 7
4 17 ....
5 .... 31
6 .... ....
7 129 127
8 257 ....
______________________________
Like the sum of squares of two successive numbers, sum of fourth power of two successive numbers also yield primes in many cases. The primes generated by this hypothetical relation are always one excess over some multiples of 16.( Table . 6.)
Table.6. Primes by n4 + (n+l)4
_________________________________
n Prime 16 x + 1
_________________________________
1 17 1 x 16 + 1
2 97 6 x 16 + 1
3 337 21 x 16 + 1
4 881 55 x 16 + 1
5 1921 120 x 16 + 1
6 3697 231 x 16 + 1
__________________________________
From the sieve of Eratosthenes, we understand that all the primes except 2 and 3 are either in the next preceding column or in the next succeeding column, i.e., they are either greater or lesser than some multiples of 6 by unity. e.g.,
5 = 1 x 6- 1 ; 7 = 1x 6 +1
11 = 2 x6– 1 ; 13 = 2 x 6 +1
17 = 3 x6 –1 ; 19 = 3x 6 + 1
23 = 4 x6 –1 ; .....................
29 = 5 x6 –1 ; 31 = 5 x 6 + 1
..................... ; 37 = 6 x 6 + 1
4l = 7 x6 –1 ; 43 = 7 x 6 + 1
Even though it holds for the entire range of prime numbers, there are some exceptions few reasonable and few unreasonable. 6n ± 1 giving odd numbers ending with 5 cannot be prime, because of its divisibility by 5 . Some multiples of 6, like 120,144,186,204,216...... don’t produce prime numbers with addition or subtraction of unity.
Prime numbers by Polynomials
Since all these relations are not rigid and applicable for the entire range of prime numbers, mathematicians then attempted with polynomials. But most of the polynomials gave only a set of prime numbers within certain limits and that too not all the primes within the limit. Beyond the limit, the polynomials give both prime and composite numbers.
It was Euler, who discovered at first a formula for generating primes. His formula is very simple in its structure and is given by x2 - x + 41. It generates primes for values of x from 0 to 40, and beyond this limit it gives both primes and composite numbers. In fact it gives prime numbers for higher values of n. It is show in Table.7.
Table.7. Primes generated by Euler’ s formula
_____ _____________________________________________________________________ Beyond limit
n p n p n p n p n p factors
_____ ___________________________________________________________________
1 41 11 151 21 461 31 971 41 1681=41 x 41
2 43 12 173 22 503 32 1033 42 1763= 41 x 43
3 47 13 197 23 547 33 1097 43 1847
4 53 14 223 24 593 34 1163 44 1933
5 61 15 251 25 641 35 1241 45 2121=43 x 47
6 71 16 281 26 691 36 1301 46 2111
7 83 17 313 27 743 37 1373 47 2203
8 97 18 347 28 797 38 1447 48 2297
9 113 19 383 29 853 39 1523 49 2393
10 131 20 421 30 911 40 1601 50 2491=47 x 53
_____ _____________________________________________________________________
Euler’s formula fits with the general form of the polynomial P(x) = ax2 + bx + c, where a, b, c have fixed values. In fact it is not possible to get amicable values for a, b, c in order to get prime numbers from P(x) for all values of x. The significance of the polynomial is how many prime numbers in series that it can generate, how it deviates away beyond the limit and its efficiency. The efficiency of Euler’s formula is 47.5 %. This can be predicted by considering x in a long range and determining the yield of P(x) (Within the range of 1 to 40, Euler’s formula is 100 % efficient, but it is less when the range of x expands). In general there are two parts in the formula, one is varying in accordance with x and the other one has fixed value, usually a prime number, in order to give prime for x = 0 in P(x). Since the fixed value is inevitably odd, the remaining portion must necessarily be even. Euler’s formula, it is n(n-l), a product of two successive numbers ,which is always even for all values of n.
Another polynomial P(x) = 2 x2 – 4x + 11 (where a = 2, b = -4 and c = 31) gives 29 primes in series. It is noted that the constant portion is odd and prime while the remaining variable portion is even. The polynomial P(x) = x2 – x + 17 gives 16 primes for all values of x < 16, P(x) = x2 -79x +1601 gives 80 primes when the value of n is less than or equal to 79, P(x) = 2x2 – 199 gives 190 primes for values x > 11 and for some values of x it gives square of some odd numbers. The polynomial P(x) = 4x2 + 170x + 1847 with an efficiency of 46.6 % gives 760 primes ,while P(x) = 4x2 + 4x +59 with lesser efficiency 43.7 % gives 1500 primes.
The Euclid
Pn = P1 x P2 x P3 x P4 x ...... x Pn-1 + 1
It is noted that the prime numbers generated by this way are all ending with 1 except the first two – 3 and 7.
No comments:
Post a Comment