1.5.2 - The Small Primes
1.5.2
The Small Primes
PREV>> 1.5.1 - Introduction to the Number Catalogs
WHAT ARE PRIMES ?
Prime numbers have been an important part of number theory since humans began to contemplate the relationships between numbers. The idea of a prime number originates with the idea of dividing an amount.
For example, say that a group of theives has stolen a small collection of coins. The coins can not be further divided. In order to avoid a potentially fatal argument between the theives, it has been agreed in advance that the collection of stolen coins would be divided "evenly". Meaning that each theif will get an equal portion, and that the number of portions will be equal to the number of thieves.
As you know from grade school, this is simply a division problem. For example, if they stole 100 coins and there are 4 theives, one simply has to compute 100 / 4 to find the size of a portion. 100/4 = 25 , so each theif would get 25 coins, and no argument would arrise ( at least in regards to fairness ). Will we always be able to divide "evenly" though ? If instead of a 100 there was 97 coins, then the 4 theives would have to compute 97 / 4 . Unfortunately there is no whole number equal to this expression ! If each theif is given 24 coins, the total would be 96 and there would still be 1 coin left over. A petty bunch could very well squabble over the left over coin.
Division was and is a basic part of human society. So for mathematicians of ancient times, division was a practical operation. They were aware that not all numbers divide evenly into each other. For example
20 is not broken evenly into 3 whole pieces. One must resort to either breaking up single units, are having a "remainder". Yet 20/4 = 5 and 20 / 5 = 4 . So although 20 can not be evenly divided into 3, it can be evenly divided into 4, 5, or even 10 parts.
Note that every counting number, "n", is divisible by 1, quite obviously. Likewise, one can always divide n by n and get 1. It turns out that there are certain whole numbers which are not divisible by any numbers save 1 and itself. These are the primes. You can imagine that primes can be problematic. Another way to think of a prime is that it is a number which can not be arranged into a complete rectangle, save for 1x n and n x 1.
By this reasoning one might conclude that 1 is prime, because it's only factor is 1 (which is both 1 and itself simultanteously). 1 however is NOT considered a true prime for an important reason.
An interesting fact about all counting numbers, is that they are either prime, or a unique product of primes. This is one of the fundamental theorems of number theory. If one were included as a prime, then one could consider any counting numbers prime factorization as including an arbitrary number of 1's.
ie. 2 = 1x2 = 1x1x2 = 1x1x1x2 = etc.
Besides being an unappealing idea from an astetic point of view, this would also complicate the idea of numbers being "unique products of primes", because there would be multiple expressions resulting in the same number. Thus 1 has been kicked out of the prime number club. By this reasoning, 1 can neither be prime, nor composite ( A composite number is the product of primes, but is not prime itself ) ! This at least gives 1 the distinction of being the only counting number with this unusual property.
In order to exclude 1 from the list of primes, a more precise definition of prime numbers is required. Rather than say it's only factors are 1 and itself we can define a prime in this way ...
Prime. A prime number is a counting number which possess EXACTLY 2 "whole" factors, which upon division results in a whole number.
In otherwords, 1 is excluded because technically 1 and itself are the same factor, thus 1 has only one whole factor.
Primes have fascinated mathematicians for millenia. It is not too hard to prove that there are an infinite number of primes, but there has never been and may never be an algorithm that can compute p(n) simply by substituting n. Such an algorithm has been sought in vein many times throughout history, and remains one of mans most impossible problems.
Modern research into primes usually doesn't concern itself with deriving specific primes, but rather in studying their distribution. It has been demonstrated through exhaustive computer searches that the density of primes does decrease as the range of the search increases. Even my own modest prime catalog reveals this fact. For example , there are 4 primes less than 10, which means that 40% of the counting numbers from 1 to 10 are prime. If we extend our search to primes less than 100, we find that there is no more that 25 primes less than 100, thus only 25% are primes . And if we look for primes less than 1000 we find only a misley 168 out of 1000, which would be 16.8%. Even a causal glance reveals that the ratio of primes to counting numbers is gradually being reduced.
Deeper issues into the prime numbers are beyond our discussion here, but hopefully this reveals some of the intrigue and mystery in regards to primes.
HOW TO READ LIST
This list is a number catalog for the first 200 prime numbers in sequence ( all primes less than 1224 ) .
p(n) will be used to specify the nth prime number.
ie. p(3) = 5 ( 5 is the 3rd prime )
The first column "n" specifies the sequence number, and enumerates the rows. The second column "p(n)" lists the nth primes . The third column "p(n)-p(n-1)" takes the difference of the nth prime and the previous prime ( this can be used to explore the intuitive expectation that the primes will become more spaced out the further one goes in the sequence ). Note that p(0) is undefined. Therefore the expression p(1)-p(0) is undefined, which i abbreviate as ud.
The 4th column is " n / p(n) ". It represents the ratio of primes to the total number of primes and composites. The ratio is written in decimal notation with 8 digits of percision. This can be used to show that in general, the percent of prime numbers decreases as the field of samples increases. However you will notice that the value does not steadily decrease but instead has small fluctuations, where it can actually increase by small amounts where prime numbers aggregate.
You'll notice that some of the ratios are in red. If it is red it means that it is the lowest ratio to appear from row 1 to n. For example, the first ratio ( 0.5 ) is highlighted because it is the lowest ratio from 1 to n by default since n =1 . After this the ratio goes up. The next point at which is reaches a lowest value is at n = 5 where the ratio is approximately 0.45 . If you read the highlighted ratios, you'll see that they always decrease. This helps to better reveal the downward trend of the ratio, despite the fluctuations.
( Note: the prime counting function pi(x) is defined as follows ... pi(x) equals the number of primes less than or equal to x. In this case the ratio n / p(n) is equivalent to pi(x) / x where x = p(n). Also note that ... pi(x) = pi(p(n)) = n )
THE FIRST 200 PRIMES, OR ALL PRIMES LESS THAN 1224
n p(n) p(n)-p(n-1) n / p(n)
1 2 ud. 0. 5000 0000
2 3 1 0. 6666 6667
3 5 2 0. 6000 0000
4 7 2 0. 5714 2857
5 11 4 0. 4545 4545
6 13 2 0. 4615 3846
7 17 4 0. 4117 6471
8 19 2 0. 4210 5263
9 23 4 0. 3913 0435
10 29 6 0. 3448 2759
11 31 2 0. 3548 3871
12 37 6 0. 3243 2432
13 41 4 0. 3170 7317
14 43 2 0. 3255 8140
15 47 4 0. 3191 4894
16 53 6 0. 3018 8679
17 59 6 0. 2881 3559
18 61 2 0. 2950 8197
19 67 6 0. 2835 8209
20 71 4 0. 2816 9014
21 73 2 0. 2876 7123
22 79 6 0. 2784 8101
23 83 4 0. 2771 0843
24 89 6 0. 2696 6292
25 97 8 0. 2577 3196
26 101 4 0. 2574 2574
27 103 2 0. 2621 3592
28 107 4 0. 2616 8224
29 109 2 0. 2660 5505
30 113 4 0. 2654 8673
31 127 14 0. 2440 9449
32 131 4 0. 2442 7481
33 137 6 0. 2408 7591
34 139 2 0. 2446 0432
35 149 10 0. 2348 9933
36 151 2 0. 2384 1060
37 157 6 0. 2356 6879
38 163 6 0. 2331 2883
39 167 4 0. 2335 3293
40 173 6 0. 2312 1387
41 179 6 0. 2290 5028
42 181 2 0. 2320 4420
43 191 10 0. 2251 3089
44 193 2 0. 2279 7927
45 197 4 0. 2284 2640
46 199 2 0. 2311 5578
47 211 12 0. 2227 4882
48 223 12 0. 2152 4664
49 227 4 0. 2158 5903
50 229 2 0. 2183 4061
51 233 4 0. 2188 8412
52 239 6 0. 2175 7322
53 241 2 0. 2199 1701
54 251 10 0. 2151 3944
55 257 6 0. 2140 0778
56 263 6 0. 2129 2776
57 269 6 0. 2118 9591
58 271 2 0. 2140 2214
59 277 6 0. 2129 9639
60 281 4 0. 2135 2313
61 283 2 0. 2155 4770
62 293 10 0. 2116 0410
63 307 14 0. 2052 1173
64 311 4 0. 2057 8778
65 313 2 0. 2076 6773
66 317 4 0. 2082 0189
67 331 14 0. 2024 1692
68 337 6 0. 2017 8042
69 347 10 0. 1988 4726
70 349 2 0. 2005 7307
71 353 4 0. 2011 3314
72 359 6 0. 2005 5710
73 367 8 0. 1989 1008
74 373 6 0. 1983 9142
75 379 6 0. 1978 8918
76 383 4 0. 1984 3342
77 389 6 0. 1979 4344
78 397 8 0. 1964 7355
79 401 4 0. 1970 0748
80 409 8 0. 1955 9902
81 419 10 0. 1933 1742
82 421 2 0. 1947 7435
83 431 10 0. 1925 7541
84 433 2 0. 1939 9538
85 439 6 0. 1936 2187
86 443 4 0. 1941 3093
87 449 6 0. 1937 6392
88 457 8 0. 1925 6018
89 461 4 0. 1930 5857
90 463 2 0. 1943 8445
91 467 4 0. 1948 6081
92 479 12 0. 1920 6681
93 487 8 0. 1909 6509
94 491 4 0. 1914 4603
95 499 8 0. 1903 8076
96 503 4 0. 1908 5487
97 509 6 0. 1905 6974
98 521 12 0. 1880 9981
99 523 2 0. 1892 9254
100 541 18 0. 1848 4288
101 547 6 0. 1846 4351
102 557 10 0. 1831 2388
103 563 6 0. 1829 4849
104 569 6 0. 1827 7680
105 571 2 0. 1838 8792
106 577 6 0. 1837 0884
107 587 10 0. 1822 8279
108 593 6 0. 1821 2479
109 599 6 0. 1819 6995
110 601 2 0. 1830 2829
111 607 6 0. 1828 6656
112 613 6 0. 1827 0799
113 617 4 0. 1831 4425
114 619 2 0. 1841 6801
115 631 12 0. 1822 5040
116 641 10 0. 1809 6724
117 643 2 0. 1819 5956
118 647 4 0. 1823 8022
119 653 6 0. 1822 3583
120 659 6 0. 1820 9408
121 661 2 0. 1830 5598
122 673 12 0. 1812 7786
123 677 4 0. 1816 8390
124 683 6 0. 1815 5198
125 691 8 0. 1808 9725
126 701 10 0. 1797 4322
127 709 8 0. 1791 2553
128 719 10 0. 1780 2503
129 727 8 0. 1774 4154
130 733 6 0. 1773 5334
131 739 6 0. 1772 6658
132 743 4 0. 1776 5814
133 751 8 0. 1770 9720
134 757 6 0. 1770 1453
135 761 4 0. 1773 9816
136 769 8 0. 1768 5306
137 773 4 0. 1772 3157
138 787 14 0. 1753 4943
139 797 10 0. 1744 0402
140 809 12 0. 1730 5315
141 811 2 0. 1738 5943
142 821 10 0. 1729 5981
143 823 2 0. 1737 5456
144 827 4 0. 1741 2334
145 829 2 0. 1749 0953
146 839 10 0. 1740 1669
147 853 14 0. 1723 3294
148 857 4 0. 1726 9545
149 859 2 0. 1734 5751
150 863 4 0. 1738 1228
151 877 14 0. 1721 7788
152 881 4 0. 1725 3121
153 883 2 0. 1732 7293
154 887 4 0. 1736 1894
155 907 20 0. 1708 9305
156 911 4 0. 1712 4040
157 919 8 0. 1708 3787
158 929 10 0. 1700 7535
159 937 8 0. 1696 9050
160 941 4 0. 1700 3188
161 947 6 0. 1700 1056
162 953 6 0. 1699 8951
163 967 14 0. 1685 6256
164 971 4 0. 1688 9804
165 977 6 0. 1688 8434
166 983 6 0. 1688 7080
167 991 8 0. 1685 1665
168 997 6 0. 1685 0552
169 1009 12 0. 1674 9257
170 1013 4 0. 1678 1836
171 1019 6 0. 1678 1158
172 1021 2 0. 1684 6229
173 1031 10 0. 1677 9825
174 1033 2 0. 1684 4143
175 1039 6 0. 1684 3118
176 1049 10 0. 1677 7884
177 1051 2 0. 1684 1104
178 1061 10 0. 1677 6626
179 1063 2 0. 1683 9135
180 1069 6 0. 1683 8167
181 1087 18 0. 1665 1334
182 1091 4 0. 1668 1943
183 1093 2 0. 1674 2909
184 1097 4 0. 1677 3017
185 1103 6 0. 1677 2439
186 1109 6 0. 1677 1867
187 1117 8 0. 1674 1271
188 1123 6 0. 1674 0873
189 1129 6 0. 1674 0478
190 1151 22 0. 1650 7385
191 1153 2 0. 1656 5481
192 1163 10 0. 1650 9028
193 1171 8 0. 1648 1640
194 1181 10 0. 1642 6757
195 1187 6 0. 1642 7970
196 1193 6 0. 1642 9170
197 1201 8 0. 1640 2998
198 1213 12 0. 1632 3166
199 1217 4 0. 1635 1684
200 1223 6 0. 1635 3230
------------------------------------------------------------------------------------
A casual look at the third column does reveal that the size of the gaps is gradually increasing. None the less, you might notice that gaps of 2 continue to appear throughout the list, although the frequency seems to decrease. Will there be a point at which no more gaps of 2 will appear, or is it the case that no matter how far we go out on the number line we will always find more pairs of primes which are 2 apart? Primes seperated by 2 are known as twin primes, and so this is equivalent to asking whether there are a finite or infinite number of twin primes. The answer to this question is unknown and remains and open problem in mathematics but it is a conjectured that they are in fact infinite.
Also notice the ratio n / p(n) . The ratios highlighted in red show that the general trend is in fact downward. When the ratio does go up, you'll often find this is because the consecutive primes are close together. When the ratio is red, it's usually because there is a significant gap between consecutive primes.
Computing primes is difficult, and there are only a few shortcuts that humans have devised to show when a counting number is prime or not.
The best trick I am aware of is dividing a number by primes equal to or less than the square root of the number. If none of these primes prove to be divisors, than the new number is also prime.
Even so, this algorithm becomes quite tedious when dealing with very large numbers. Professional mathematicians and scientists sometimes compete to discover the "largest known prime".
Currently the largest known prime number is (2^74,207,281)-1 found on January 7th of 2008 by Curtis Cooper as part of GIMPS (The Great Internet Mersenne Primes Search). Carrying out the lengthy arithmetic will produce a number with exactly 22,338,618 digits!
The size of such numbers is very impressive by conventional standards, but what is even more impressive is the efforts that are required to prove whether such large numbers are prime or not. Such large primes are found by using super computers ! As we will learn later, it does not require much effort or math to transcend even such numbers as these. For this reason the "largest prime" will probably remain within the "hyper-exponential range" in the foreseeable future, and lag way behind the purely speculative large numbers that can be generated.
These topics will be covered in later sections. If you want, you can proceed to the arithmetic catalog...
NEXT>> 1.5.3 - Arithmetic Catalog