7 ms·

The Ulam Spiral of Primes

74 points by fogus 16y ago

jokermatt999 16y ago
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.
- dunk010 16y ago
  It really is. One of my favourite movies. Highly recommended.
CapitalistCartr 16y ago
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.
- pohl 16y ago
  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?
  - CapitalistCartr 16y ago
    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 http://en.wikipedia.org/wiki/Prime_Numbers#Distribution
    - gjm11 16y ago
      "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.
      - CapitalistCartr 16y ago
        Right, Prime numbers are anything but random. Their distribution, however, is.
        argv_empty 16y ago
        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).
        TheCondor 16y ago
        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.
- vecter 16y ago
  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.
  - zandorg 16y ago
    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 16y ago
      [deleted]
  - CapitalistCartr 16y ago
    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.
    - thefool 16y ago
      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.
- thefool 16y ago
  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.
  - bitdiddle 16y ago
    "God made the natural numbers; all else is the work of man." -- Kronecker[1] [1] http://en.wikipedia.org/wiki/Preintuitionism http://en.wikipedia.org/wiki/Preintuitionism
rgoddard 16y ago
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.
- inferno0069 16y ago
  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.
  - PebblesRox 16y ago
    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.
  - Barnabas 16y ago
    Of course it's interesting. There's no such thing as an uninteresting number. http://en.wikipedia.org/wiki/Interesting_number_paradox http://en.wikipedia.org/wiki/Interesting_number_paradox
- paulgb 16y ago
  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.
  - nitrogen 16y ago
    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)) ?
Dove 16y ago
From http://mathworld.wolfram.com/PrimeSpiral.html 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.
borism 16y ago
if you're like me - more physics than math guy, it's the same Stanislaw Ulam of Teller-Ulam design fame.
mbrubeck 16y ago
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/ http://imprompt.us/2010/ulam-spiral-take-2/
- crux 16y ago
  That's my friend Peter, too! He's wicked smart.
shrikant 16y ago
[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.
- dagobart 16y ago
  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.

74 points by fogus 16y ago

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.

dunk010 16y ago
It really is. One of my favourite movies. Highly recommended.

CapitalistCartr 16y ago

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.

pohl 16y ago
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?
- CapitalistCartr 16y ago
  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 http://en.wikipedia.org/wiki/Prime_Numbers#Distribution
  - gjm11 16y ago
    "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.
    - CapitalistCartr 16y ago
      Right, Prime numbers are anything but random. Their distribution, however, is.
      - argv_empty 16y ago
        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).
      - TheCondor 16y ago
        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.
vecter 16y ago
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.
- zandorg 16y ago
  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 16y ago
    [deleted]
- CapitalistCartr 16y ago
  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.
  - thefool 16y ago
    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.
thefool 16y ago
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.
- bitdiddle 16y ago
  "God made the natural numbers; all else is the work of man." -- Kronecker[1] [1] http://en.wikipedia.org/wiki/Preintuitionism http://en.wikipedia.org/wiki/Preintuitionism

rgoddard 16y ago

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.

inferno0069 16y ago
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.
- PebblesRox 16y ago
  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.
- Barnabas 16y ago
  Of course it's interesting. There's no such thing as an uninteresting number. http://en.wikipedia.org/wiki/Interesting_number_paradox http://en.wikipedia.org/wiki/Interesting_number_paradox
paulgb 16y ago
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.
- nitrogen 16y ago
  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)) ?

Dove 16y ago

From http://mathworld.wolfram.com/PrimeSpiral.html 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.

borism 16y ago

if you're like me - more physics than math guy, it's the same Stanislaw Ulam of Teller-Ulam design fame.

mbrubeck 16y ago

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/ http://imprompt.us/2010/ulam-spiral-take-2/

crux 16y ago
That's my friend Peter, too! He's wicked smart.

shrikant 16y ago

[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.

dagobart 16y ago
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.