Fundamentals of discrete mathematics state that any positive integer can be represented canonically, or in what's called "standard form," as the product of many small primes.
From this, we can easily draw the conclusion that almost all "large" numbers (with, shall we say, 5 or more digits) that are composite have an extremely high likelihood of having any of the following numbers as factors:
2, 3, 5, 7, 11, 13, 17, 19, 23
The array of primes above can be extrapolated ad infinitum, provided you subscribe to the Euclidean belief that there is not a finite amount of primes. However, as the leading edge gets higher, the likelihood of it being a factor decreases.
This is not because 47 is innately less likely to factor a number than is 23. Rather, it is because when using an array of known prime numbers to (attempt to) factor some integer n, the leading edge of that array increases until it approaches (or exceeds) the boundary sqrt(n).
Of course, the square root of some integer n is not always a whole number. In such cases, ought one round up or down? Let's say that we round down when the decimal digits are >= .49 and up when they are =<.50.
Back to the premise of trial division - that the use of primes alone to factor n becomes less and less effective as one approaches sqrt(n).
Primes do not necessarily become "sparser" as numbers increase in size. Consider Ulam's Spiral.
Now, imagine that the "center" of the spiral is Earth, and each white dot is a star. From this perspective (at the origin, on the z axis, arbitrarily perpendicular to a 2D space), it would appear that all the "stars" are roughly evenly spaced, albeit sometimes clustered. Close inspection seems to suggest some kind of pattern, and despite being unable to describe the pattern, it is clear the positioning of these dots is not random.
Now, imagine that you are on "Earth" in the center of this spiral. Also, imagine there is no light pollution and the night sky is clear. What would you observe?
The answer varies, but one thing is for sure - you would not necessarily observe a pattern. In fact, you would see the night sky blanketed in stars such that no area of the sky looks discernably different from any other.
This is, in fact, the fundamental theory of the Universe - that there is no "unique" or "special" place in space, and all areas look about the same.
Does the space between stars actually get bigger as you move away from some arbitrary origin point? Of course not*. They just get harder to see - mainly because of interstellar dust, actually, not because they are "fainter."
How on earth does this relate to number theory?
Ulam's Spiral shows us that there is a predictable amount of primes in a given range of numbers. While there is no formula to determine this - yet - it is safe to say that if we were to expand this picture, subsequently added areas would contribute to the overall appearance of a spiral.
However - are there actually fewer primes in ranges of larger numbers? Will the spaces between white dots grow? Why do they seem "clustered" around the middle?
I can at least answer the last rhetorical there: There are fewer numbers around the middle! Remember how we said there is a predictable amount of primes in a given range of numbers? Well, in the spiral, a "range" of numbers is represented by a full 360-degree path around the middle. This path becomes longer and longer as you move away from the origin! Thus, the space between primes should grow...shouldn't it?
No, not necessarily! The amount of primes in a given range of numbers in the spiral actually seems to increase! Why? Because there are more numbers in that 360-degree path? Yes, that sounds logical. But is it provable fact?
No! Of course not. That's why number theory exists as a field of study! Number theorists strive to find rhyme and reason to prime numbers. We can only observe and speculate whilst they do so.
More on trial division to come!
-
JB 24 Jul 2012
*not to be confused with galaxies or galactic clusters, which are in fact speeding away from each other from what seems to be a roughly central point.
From this, we can easily draw the conclusion that almost all "large" numbers (with, shall we say, 5 or more digits) that are composite have an extremely high likelihood of having any of the following numbers as factors:
2, 3, 5, 7, 11, 13, 17, 19, 23
The array of primes above can be extrapolated ad infinitum, provided you subscribe to the Euclidean belief that there is not a finite amount of primes. However, as the leading edge gets higher, the likelihood of it being a factor decreases.
This is not because 47 is innately less likely to factor a number than is 23. Rather, it is because when using an array of known prime numbers to (attempt to) factor some integer n, the leading edge of that array increases until it approaches (or exceeds) the boundary sqrt(n).
Of course, the square root of some integer n is not always a whole number. In such cases, ought one round up or down? Let's say that we round down when the decimal digits are >= .49 and up when they are =<.50.
Back to the premise of trial division - that the use of primes alone to factor n becomes less and less effective as one approaches sqrt(n).
Primes do not necessarily become "sparser" as numbers increase in size. Consider Ulam's Spiral.
Now, imagine that the "center" of the spiral is Earth, and each white dot is a star. From this perspective (at the origin, on the z axis, arbitrarily perpendicular to a 2D space), it would appear that all the "stars" are roughly evenly spaced, albeit sometimes clustered. Close inspection seems to suggest some kind of pattern, and despite being unable to describe the pattern, it is clear the positioning of these dots is not random.
Now, imagine that you are on "Earth" in the center of this spiral. Also, imagine there is no light pollution and the night sky is clear. What would you observe?
The answer varies, but one thing is for sure - you would not necessarily observe a pattern. In fact, you would see the night sky blanketed in stars such that no area of the sky looks discernably different from any other.
This is, in fact, the fundamental theory of the Universe - that there is no "unique" or "special" place in space, and all areas look about the same.
Does the space between stars actually get bigger as you move away from some arbitrary origin point? Of course not*. They just get harder to see - mainly because of interstellar dust, actually, not because they are "fainter."
How on earth does this relate to number theory?
Ulam's Spiral shows us that there is a predictable amount of primes in a given range of numbers. While there is no formula to determine this - yet - it is safe to say that if we were to expand this picture, subsequently added areas would contribute to the overall appearance of a spiral.
However - are there actually fewer primes in ranges of larger numbers? Will the spaces between white dots grow? Why do they seem "clustered" around the middle?
I can at least answer the last rhetorical there: There are fewer numbers around the middle! Remember how we said there is a predictable amount of primes in a given range of numbers? Well, in the spiral, a "range" of numbers is represented by a full 360-degree path around the middle. This path becomes longer and longer as you move away from the origin! Thus, the space between primes should grow...shouldn't it?
No, not necessarily! The amount of primes in a given range of numbers in the spiral actually seems to increase! Why? Because there are more numbers in that 360-degree path? Yes, that sounds logical. But is it provable fact?
No! Of course not. That's why number theory exists as a field of study! Number theorists strive to find rhyme and reason to prime numbers. We can only observe and speculate whilst they do so.
More on trial division to come!
-
JB 24 Jul 2012
*not to be confused with galaxies or galactic clusters, which are in fact speeding away from each other from what seems to be a roughly central point.
No comments:
Post a Comment