By Tom Kando
On. Feb. 12, 2011, I wrote a post on prime numbers: Prime Numbers, Large Numbers. This topic still fascinates me.
A prime number is a whole number that can only be divided by 1 and by itself. Or put differently, prime numbers cannot be divided by any other whole number without leaving a fraction. For example, the four prime numbers below ten are: 2, 3, 5, 7. Beyond that, no even number can be a prime. Nor can any number ending on 5, since all such numbers can be divided by 5.
One fascinating aspect of prime numbers is that they seem to obey no other law than that of chance, and that nobody can predict what the next higher - and not yet discovered - prime number will be!
Back in 2009, the largest prime number ever discovered (by the Greater Internet Mersenne Prime Search Research Project) was: 2 to the power 43,112,609 minus 1. This is a number with almost 13 million decimal digits.
Since then, the same researchers have gone much further. As of early 2014, the largest known prime is 2 to the power 57,885,161 minus 1. This number has nearly 17 and a half million digits. To write it out would require 6,000 pages, or twenty 300-page long books. For more information about prime numbers, see: prime numbers
* * * *
The way to find out whether a number is a prime:
First, as I just told you, no even number, nor any number ending on 5, can be a prime. So the only candidates to be prime numbers are those that end on 1,3,7 or 9. This already reduces your task by 60%.
But then, you have to factorize: That is, when you try to determine whether a number is a prime or not, you must “decompose” it and find its factors that are prime (indivisible). For example, take 87: It is divisible by two prime numbers: 3 (and 29). Therefore 87 is not a prime.
Now try to factorize 89: is it divisible by 3? No. By 7? No. By 9? No. Etc. 89 turns out to be a prime.
Here are the 25 primes under 100: 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.
As you get into large numbers, factorization becomes tediously time-consuming. The good news is that there are many prime number calculators on the Internet, for example: calculator, which you can use up to nearly four and a half billion.
* * * *
Here is one of the most fascinating aspects of prime numbers: There is an INFINITE amount of them, but at the same time, they become more and more rare as you move up the sequence of natural numbers. This is something you suspect right away, even just looking at the first few hundred numbers: For example, here is how many prime numbers there are under 500:
from 1 to 100: 25
101 to 200: 21
201 to 300: 16
301 to 400: 17
401 to 500: 16
The diminishing number of primes is called the Prime Number Theorem (PNT).
Mathematicians have known this for hundreds of years. For example, Carl Friedrich Gauss - of the famous Gaussian (normal) distribution - studied and confirmed this theorem in 1791, at the age of 14.
Mathematicians say that “the distribution of primes is ASYMPTOTIC.” This means that the curve approaches zero as it tends towards infinity. In other words, it never touches zero, and its slope is curvilinear, declining ever more slowly. See: https://www.google.com/#q=asymptotic+curve
I just wanted to SEE the asymptotic distribution of prime numbers with my own eyes, so I examined some tables showing the density of primes as you go up the sequence of natural numbers. Here is what I found:
below 10, there are 4 prime numbers = 40 per 100
below 100: 25 = 25 per 100
below 1,000: 138 = 14 per 100
below 10,000: 1,229 = 12 per 100
below 100,000: 9,592 = 10 per 100
below 1 million: 78,498 = 8 per 100
below 10 million : 664,579 = 7 per 100
below 100 million: 5,761,455 = 6 per 100
below 1 billion: 50,847,534 = 5 per 100
below 10 billion: 455,052,511 = 4.6 per 100
Etc.
See: questions about prime numbers
So it’s clear that prime numbers become more rare as you go up the series of natural numbers. Also, the DECLINE in the frequency of prime numbers slows down.
Mathematicians say that the frequency reaches zero in infinity or at the “limit.” In other words, there NEVER comes a number, no matter how unimaginably large, beyond which there are zero primes, or only one, or only a finite amount of them, even though they are spaced further and further apart, which is what makes finding them increasingly difficult, even with the most powerful computers.
I find it incredibly weird that there are immense numbers out there which are indivisible, in other words, quantities of just ONE piece, without ANY component parts.
© Tom Kando 2014
leave comment here
Tom,
ReplyDeleteI’m with you, fascinated by primes.
There are methods nowadays for determining whether a number is prime that don’t involve factoring the number. With these methods, it is not difficult to test whether numbers with hundreds of digits are prime. This is to be contrasted with the difficulty of factoring a large number. A number that is several hundred digits long that can be determined to be a composite number (i.e., it is not a prime) cannot generally be factored by computers, in any amount of time. This contrast between the ability to test whether large numbers are prime and the inability to factor large numbers is foundational to modern cryptography.
These algorithms that test whether a number is prime rely on other fascinating properties of primes. For example, if p is a prime and a is any whole number, then a^p-a (where a^p means a raised to the power p) is always divisible by the prime p.
The largest known prime numbers are a particular kind of prime, Mersenne primes. These are prime numbers that happen to be one less than a power of 2. There is an algorithm for determining whether a number that is one less than a power of 2 is prime, and it works well enough to allow for determining whether numbers of that form, with millions of digits, are prime! The other fascinating aspect to this is that your computer can join thousands of other home computers and participate in finding the next Mersenne prime. That’s how the Great Internet Mersenne Prime Search works, using ordinary people’s computers when they would otherwise be idle.
For some other fun with primes, I suggest that you play with the reciprocals of primes, which produce repeating decimals that have fascinating properties. Here’s a short video of an Ignite session I did on this topic:
http://www.youtube.com/watch?v=U8MSc_UYJ_0&index=38&list=PL5CDF98F961F9527D
Congratulations and welcome to my world Tom. That is the world of "meaningless mathematics" as distinguished from the "meaningful and practical world" of physics and engineering.
ReplyDeleteIn ancient Greece we would have attended Socrates' University of Meaningful Thought instead of The Pathagorian College of Real Accomplishments. We would have studied in the middle of a dark & dense forest drinking from cascading streams and eating wild olives and figs. The Pathagorus guys would study in well constructed buildings and eat tasteful, seasoned and balanced meals served in the school cafeteria.
I can't wait until we meet next for dinner. We'll discuss the benefit of carrying out PI to 1,001 places instead of only 500. Our wives will love it as well!
QED
that is visible, that you are grandson of Manó Beke.
ReplyDeleteTom’s, Scott’s and Susan’s comments are gratifying.
ReplyDeleteTom’s description of ancient Greek philosophical life is colorful. I love it - the world of meaningless mathematics! That’s for me.
Scott is a mathematician, and way over my head. His is the sort of response I was hoping for. I am a Jack of all trades and master of none. I like to intersperse my pro-Obama diatribes with thoughts about prime numbers and Medieval genealogy. Although, as Susan points out, math was of the essence in my family: Beke Mano was my great-grandfather, President of the University of Budapest and eminent mathematician. He wrote the book on Integral Mathematics. One of his students was Edward Teller. I’m not making this up!
Anyway, Scott: I saw your virtuose video about the reciprocals of prime numbers. Could barely follow it. Brilliant. Thanks. Yes, I did notice that the Mersenne primes are all one less than a power of 2. Obviously, they have to be odd numbers.
In your lecture, you briefly mention “building the universe.” I have often seen questions posed about the relationship between mathematics and the universe. For example, is the universe “made up of mathematics/mathematical laws?” A question both absurd and profound?