## Prime Number Tricks

January 3rd, 2013 by Math Tricks | 3 Comments | Filed in Math Tricks, Prime Numbers

``` // <![CDATA[ google_ad_client = "ca-pub-2176115693811858"; /* Prime Number Tricks */ google_ad_slot = "9024977792"; google_ad_width = 468; google_ad_height = 60; // ]]&gt; // <![CDATA[ // ]]&gt; ```
One topic that I was introduced to in my elementary school days was the set of prime numbers.  I was given the standard definition of prime numbers that I was to commit to memory, and the composite-prime number lists discussed in class were mostly used as exercises in multiplication and division.  It really is a shame that the more mysterious aspects of prime numbers were not discussed, because it would have perked my interest in mathematics at the time.  I am not a school teacher, so I do not know how prime numbers are taught in schools today.  I can only hope that they are given more attention than when I was in school.  I will not talk about all of the remarkable properties of primes here – I am only going to show a couple of math tricks which are related to prime numbers.

Finite or Infinite Primes

If you are anything like me, you have probably spent many hours contemplating the prime numbers – the set of positive integers (not including 1, as I have to often remind others) that can only be evenly divisible by one or themselves.  A formal definition of a prime number can be stated as:

A number n is prime if it is greater than 1 and has no positive divisors except 1 and n

One of the standard questions one asks about prime numbers is, “How many prime numbers are there?”  The answer is that there are an infinite number of primes.  This was demonstrated by Euclid thousands of years ago.  He came up with a neat trick (described below) to demonstrate how there are an infinite number of primes.

If you take the first few primes and multiply them together, you will come up with a product which is a composite of each prime used, and thus is evenly divisible by each of those primes.  For example:

2 x 3 x 5 = 30

If you divide 30 by 2 or 3 or 5, you will not get a remainder.

Now, if you add 1 to the product, you will get a number that can NOT be evenly divisible by ANY of the primes used.  In fact, this new number can only be either a NEW prime number, or a product of two or more NEW prime numbers.

This is what Euclid did to show how there are an infinite number of primes.  The sequence of results is called the Euclid numbers: 1 + (product of the first n primes).  Applying this method for the first few primes we get:

1 + (2) = 3 (Prime)

1 + (2*3) = 7 (Prime)

1 + (2*3*5) = 31 (Prime)

1 + (2*3*5*7) = 211 (Prime)

1 + (2*3*5*7*11) = 2311 (Prime)

1 + (2*3*5*7*11*13) = 30031 (Not prime, but composed of the new primes 59 × 509)

1 + (2*3*5*7*11*13*17) = 510511 (Not prime, but composed of the new primes 19 × 97 × 277)

1 + (2*3*5*7*11*13*17*19) = 9699691 (Composed of the new primes 347 × 27953)

This method can be carried out ad infinitum, demonstrating the infinity of prime numbers.

Calculating Prime Numbers

An often-asked question is whether or not you can calculate the number of primes within a stretch of integers.  For instance, how many prime numbers are there from 1 to 3500?  To answer this question, I used Microsoft Access to separate the first 500 prime numbers from the OEIS A000040 (http://oeis.org/A000040) sequence (unverified):

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571

So, as you can see, there are nearly 500 prime numbers from 1 to 3500 (489 to be exact), or just about 14%.  Well, that is a lot of work to get the answer you seek.  It would be great if you can at least get an estimate of the number of primes present in a stretch of integers.  As it so happens, prime numbers have been studied for some time now, and there are ways of calculating the number of primes in a stretch of numbers very accurately.  For obtaining a very rough estimate on your calculator, there is a very simple formula you can use that was developed by Carl Friedrich Gauss during his investigations of the relation between logarithms and prime numbers:

Number of Primes from 1 to N ~= N/ln N

So in our example,

# Primes ~ 3500/ln (3500) = 3500/8.16052 = 429 prime numbers

Adrien-Marie Legendre, a contemporary of Gauss, was able to produce a simple formula which produced an even closer approximation:

Number of Primes ~ N/(ln N – 1.08366)

So in our example,

# Primes ~ 3500/(ln (3500) – 1.08366) = 3500/(8.16052 – 1.08366) = 494 prime numbers

I hope this has wetted your appetite for prime numbers.  They really are very interesting, and I am sure you will enjoy reading about them on your own.  Bon Appétit!