The Ulam Spiral of Primes(scienceblogs.com)
scienceblogs.com
The Ulam Spiral of Primes
http://scienceblogs.com/goodmath/2010/06/the_surprises_never_eend_the_u.php?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+scienceblogs%2FCyKN+%28Good+Math%2C+Bad+Math%29
7 comments
You are going to see a pattern along the diagonal because every other number is even and never prime (excluding 2). So the only way for two primes to be touching is along a diagonal. Given that and our brains tendency to group items which are closer together as being related, anything along the diagonal will stand out more and appear to be a pattern. A more interesting picture would be one where all of the even numbers are omitted.
A more interesting picture would be one where all of the even numbers are omitted.
I made canvas renderer to check it:
http://alteredqualia.com/visualization/ulam-spiral.html
It's not checkerboard, but there are horizontal and vertical patterns.
I made canvas renderer to check it:
http://alteredqualia.com/visualization/ulam-spiral.html
It's not checkerboard, but there are horizontal and vertical patterns.
All the odds would look like a full checkerboard, not like these diagonals. The fact that some diagonal lines appear to be favored over other nearby diagonal lines of odd numbers is still interesting.
Of course it's interesting. There's no such thing as an uninteresting number. http://en.wikipedia.org/wiki/Interesting_number_paradox
Not coloring all the odds, just plotting only odds and still coloring only the primes. The new spiral has a 3 where the old two was and a 5 where the old three was, etc.
There's also the pattern that every prime (above 3) modulo 6 is congruent to 1 or 5. I suspect that some of the pattern comes from that fact.
Is there a more generalized version of that pattern, perhaps something like this (I haven't checked):
let P(n) be the nth prime number: P(1)=2, etc.
let n be an integer >= 2, and m be an integer > n
then P(m) ≡ 1 and (P(n) - 1) (mod P(n))
?From http://mathworld.wolfram.com/PrimeSpiral.html :
This construction was first made by Polish-American mathematician Stanislaw Ulam (1909-1986) in 1963 while doodling during a boring talk at a scientific meeting.
Awesome. My new excuse for all those doodles in my engineering notebook: valuable, valuable mathematical research.
This construction was first made by Polish-American mathematician Stanislaw Ulam (1909-1986) in 1963 while doodling during a boring talk at a scientific meeting.
Awesome. My new excuse for all those doodles in my engineering notebook: valuable, valuable mathematical research.
My friend Peter made a poster of the Ulam Spiral that includes the Python code used to generate it: http://imprompt.us/2010/ulam-spiral-take-2/
That's my friend Peter, too! He's wicked smart.
I believe this was also shown briefly in the movie Pi. At least, I think that's where I recognize it from. Great movie about finding patterns in numbers and pareidolia.
It really is. One of my favourite movies. Highly recommended.
[These spirals have] been cited by some religious folks as being a proof of the existence of God. Personally, I think that that's silly; my personal belief is that even a deity can't change the way the numbers work: the nature of the numbers and how they behave in inescapable. Even a deity who could create the universe couldn't make 4 a prime number.
Amen to that.
Amen to that.
So, pushing this thought a little further, I'd say such a (or any) deity and us have at least this one thing in common: looking in amazement at those primes.
We invented the idea of Prime Numbers. They're an arbitrary creation. As are patterns in them. Random is -NOT- the same as even distribution. Patterns are inevitable. Las Vegas makes a fortune on people who don't understand that. If you flip a coin a hundred times, you'll see patterns in the result. People are good at seeing patterns.
This is wrong. Humans discovered prime numbers. They are not an invention. They fall naturally out of the integers, and would exist regardless of whether humans did or not. Prime numbers are are some of the most fundamental objects in all of mathematics, and the fact that you can find them on diagonals in these graphs probably indicates a pattern that we can't explain yet.
For more:
http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...
I agree that some mathematical objects are "more fundamental than others"; primes are probably among the most basic.
If you're interested in the ontological status of mathematical entities, and the process and meaning of mathematics, check out "The Mathematical Experience" by Davis and Hersh,
http://books.google.com/books?id=lMdz84dWNnAC&printsec=f...
There is a section on primes starting on page 209.
http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...
I agree that some mathematical objects are "more fundamental than others"; primes are probably among the most basic.
If you're interested in the ontological status of mathematical entities, and the process and meaning of mathematics, check out "The Mathematical Experience" by Davis and Hersh,
http://books.google.com/books?id=lMdz84dWNnAC&printsec=f...
There is a section on primes starting on page 209.
It's also such a universal constant that some sci-fi stories or movies (eg, Contact (1997)) use them as a tool to indicate an intelligent civilisation. In other words, transmit 2 blips, 3 blips, 5 blips, 7 blips, and it soon becomes clear it's not random - it's a list of primes.
[deleted]
The question of whether math is invented or discovered is far from settled. I know next to nothing about math, but a quick google search for "math created or invented" brings up so much controversy I find it unlikely that it's been decided. See Mathematical Platonism and its Opposites by Barry Mazur (p. 19 in: http://www.ems-ph.org/journals/newsletter/pdf/2008-06-68.pdf). He says it's The Question that won't go away.
Indeed. Further, at the risk of soun
ding too phiosophical, this invention/discovery, Platonist/constructivist debate hinges on the fundamental notion of existence. And, as with most fundamental notions, the obvious soon ceases to be so.
Nice link. The article before Mazur's, by Davis (author of the book I mentioned above) is also good.
By that reasoning, all ways of grouping, analyzing, and considering numbers are discovered. And those ways are infinite. That primes are important is of our choosing.
This depends on how you define "of our choosing".
There are a number of practical social situations where an understanding of divisibility can be useful.
For instance, say a group of social animals of equal rank stumble upon some berries and split them amongst themselves. It would be beneficial for them to understand that if the number of berries is relatively prime to the number of them, then an even distribution is impossible and they should accept that.
I'm sure more compelling examples of grouping in social animals arise all the time. Now if these animals begin to study numbers abstractly, one of the first things that they will practically need to understand is the rules that govern groupings. This will lead them immediately into the idea of prime numbers (and by extension relatively prime numbers).
I can't really think of a technique of grouping or looking at numbers that wouldn't at least implicitly require prime numbers.
It may be that higher level analysis of primes (like in this article) is somewhat artificial, but I'd maintain that the idea that a number is prime, or at least the concept that two numbers are relatively prime, is one that is fundemental to having any understanding of a number system.
There are a number of practical social situations where an understanding of divisibility can be useful.
For instance, say a group of social animals of equal rank stumble upon some berries and split them amongst themselves. It would be beneficial for them to understand that if the number of berries is relatively prime to the number of them, then an even distribution is impossible and they should accept that.
I'm sure more compelling examples of grouping in social animals arise all the time. Now if these animals begin to study numbers abstractly, one of the first things that they will practically need to understand is the rules that govern groupings. This will lead them immediately into the idea of prime numbers (and by extension relatively prime numbers).
I can't really think of a technique of grouping or looking at numbers that wouldn't at least implicitly require prime numbers.
It may be that higher level analysis of primes (like in this article) is somewhat artificial, but I'd maintain that the idea that a number is prime, or at least the concept that two numbers are relatively prime, is one that is fundemental to having any understanding of a number system.
Are you sure we didn't discover them? Numbers and mathematics wouldn't cease to exist were we to disappear.
Your use of the word "random" seems to be a non sequitur. Could you explain that connection?
Your use of the word "random" seems to be a non sequitur. Could you explain that connection?
Numbers, yes, but Prime Numbers are dependent on the idea that being divisible by only one and itself are important. There are infinite such ways to group numbers. We do Primes partly because they're useful, and also because they're cool.
I used the word random because the distribution of Primes is random as far as we currently know. http://en.wikipedia.org/wiki/Prime_Numbers#Distribution
I used the word random because the distribution of Primes is random as far as we currently know. http://en.wikipedia.org/wiki/Prime_Numbers#Distribution
"Random" is really a bit strong. They're certainly not very random in the Kolmogorov sense: the shortest program that generates the first N prime numbers is much, much shorter than constant*N. There are all sorts of obvious regularities (e.g., all are odd, all are 1 or 5 mod 6, etc.) and it's no good saying "well, they're random once you take those regularities into account" because taking those regularities into account uniquely determines the prime numbers. There are subtler deviations from the simplest random models, too; for instance, if you just pretend that each number n is (independently) prime with probability 1 / log n, you get what appears to be the wrong answer for the density of twin primes (pairs n,n+2 both of which are prime).
So no, "random as far as we currently know" is a pretty terrible description of the distribution of prime numbers.
So no, "random as far as we currently know" is a pretty terrible description of the distribution of prime numbers.
Right, Prime numbers are anything but random. Their distribution, however, is.
Random how?
We can prove the prime number theorem, we know roughly how many primes there are in a span of numbers and we know the approximate frequency of prime numbers in that span. We know on average how far apart the primes are in a particular span of numbers. All from the prime number theorem and related theorems. This stuff has been proven. Likewise, if the Riemann hypothesis is true then primes would have a very regular distribution.
What we can't yet do is create a generator function that catches most primes. We can create generators though (For example: (n! +1) is prime but it misses tons and tons of primes.) There are no hard fast rules that catch a majority of only primes. This probably doesn't qualify as "random distribution" unless you take a really simple definition of random. It's the non-randomness of their distribution that allows us to test the primality of numbers for cryptography.
We can prove the prime number theorem, we know roughly how many primes there are in a span of numbers and we know the approximate frequency of prime numbers in that span. We know on average how far apart the primes are in a particular span of numbers. All from the prime number theorem and related theorems. This stuff has been proven. Likewise, if the Riemann hypothesis is true then primes would have a very regular distribution.
What we can't yet do is create a generator function that catches most primes. We can create generators though (For example: (n! +1) is prime but it misses tons and tons of primes.) There are no hard fast rules that catch a majority of only primes. This probably doesn't qualify as "random distribution" unless you take a really simple definition of random. It's the non-randomness of their distribution that allows us to test the primality of numbers for cryptography.
I agree with the point you're making, but unfortunately almost all the particular statements above are wrong :-).
n!+1 is not always prime. For instance, 4!+1 = 25 = 5^2, 5!+1 = 121 = 11^2, 6!+1 = 721 = 7.103.
If RH is true, then the number of primes < x differs from the naive prediction you get from saying n is prime with probability 1/log(n) by at most something like sqrt(x) log(x). That's entirely comparable to the accuracy you'd get if the primes really were randomly distributed. (More precisely: the variance of something that's 1 with probability p, else 0, is p(1-p), which is roughly equal to p when p is small, and variances of independent things are additive, so on the random-distribution hypothesis the variance of pi(x) would be comparable to the sum of 1/log(n), which is to say n/log(n). I haven't actually done the calculations, but I think this means that with probability 1 some bound of the same type that you get from RH should hold. So the bound you get from RH doesn't show that the primes are any more regularly distributed than the simple random model suggests.
Similarly, "primes" generated according to the simple random model would, with probability 1, obey theorems of the sort that we know how to prove about the distribution of primes. (And some that we don't know how to prove.)
It is possible to define mathematical functions that recognize primes, or that take on all the primes (and nothing else) as values. But they're generally contrived and inefficient to evaluate.
n!+1 is not always prime. For instance, 4!+1 = 25 = 5^2, 5!+1 = 121 = 11^2, 6!+1 = 721 = 7.103.
If RH is true, then the number of primes < x differs from the naive prediction you get from saying n is prime with probability 1/log(n) by at most something like sqrt(x) log(x). That's entirely comparable to the accuracy you'd get if the primes really were randomly distributed. (More precisely: the variance of something that's 1 with probability p, else 0, is p(1-p), which is roughly equal to p when p is small, and variances of independent things are additive, so on the random-distribution hypothesis the variance of pi(x) would be comparable to the sum of 1/log(n), which is to say n/log(n). I haven't actually done the calculations, but I think this means that with probability 1 some bound of the same type that you get from RH should hold. So the bound you get from RH doesn't show that the primes are any more regularly distributed than the simple random model suggests.
Similarly, "primes" generated according to the simple random model would, with probability 1, obey theorems of the sort that we know how to prove about the distribution of primes. (And some that we don't know how to prove.)
It is possible to define mathematical functions that recognize primes, or that take on all the primes (and nothing else) as values. But they're generally contrived and inefficient to evaluate.
[deleted]
[deleted]
Could you offer a citation? I tried to find the result you mention, and I'm at a loss to even pin down a definition of "random distribution" that might be used.
The closest I can come is the coincidence that a random variable is used in the proof of the Prime Number Theorem, but that's just a modeling technique.
At least I did find this awesome quotation, which seems to play both sides:
In a 1975 lecture, D. Zagier commented "There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision" (Havil 2003, p. 171).
http://mathworld.wolfram.com/PrimeNumber.html
The closest I can come is the coincidence that a random variable is used in the proof of the Prime Number Theorem, but that's just a modeling technique.
At least I did find this awesome quotation, which seems to play both sides:
In a 1975 lecture, D. Zagier commented "There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision" (Havil 2003, p. 171).
http://mathworld.wolfram.com/PrimeNumber.html
The shortest program that generates the differences between the first N primes isn't much longer than the program that generates the first N primes (certainly not enough to break the constant*N barrier).
but Prime Numbers are dependent on the idea that being divisible by only one and itself are important
I confess that I only have an undergraduate degree in Mathematics, but with that caveat I have a very different understanding: importance is a value judgement, and concepts in number theory such as prime-ness hinge on mere observations about the properties of numbers. People may assign importance to the property, but the property exists independently of how people feel about it.
I confess that I only have an undergraduate degree in Mathematics, but with that caveat I have a very different understanding: importance is a value judgement, and concepts in number theory such as prime-ness hinge on mere observations about the properties of numbers. People may assign importance to the property, but the property exists independently of how people feel about it.
Prime Numbers are dependent on the idea that being divisible by only one and itself are important
Whether or not we care about a particular property does not affect whether or not some numbers exhibit that property -- they'd still be prime even if we didn't care about primality.
Humans may have invented them, but they are a pretty natural concept.
Once you have a system of numbering, one of the first things one does is to see which numbers can be arrived at by simply adding other numbers to themselves a bunch of times.
I have a pretty limited knowledge of number theory, so I may be completely off mark, but I don't know that people have yet arrived at a nice fundamental theory that can encapsulate the way that primes arrange themselves along the number line.
Once you have a system of numbering, one of the first things one does is to see which numbers can be arrived at by simply adding other numbers to themselves a bunch of times.
I have a pretty limited knowledge of number theory, so I may be completely off mark, but I don't know that people have yet arrived at a nice fundamental theory that can encapsulate the way that primes arrange themselves along the number line.
"God made the natural numbers; all else is the work of man." -- Kronecker[1]
[1] http://en.wikipedia.org/wiki/Preintuitionism
[1] http://en.wikipedia.org/wiki/Preintuitionism
if you're like me - more physics than math guy, it's the same Stanislaw Ulam of Teller-Ulam design fame.