8 ms·

The Ulam Spiral of Primes (2010)

109 points by dvfjsdhgfv 9y ago

ansible 9y ago
Now I'm thinking about schemes where you iterate through lots of different permutations of visualizations, in at least two and three dimensions, and then somehow calculate a score for how interesting the pattern is. Maybe using a sort of contrast algorithm like autofocus for a camera. If it looks noisy and random, then that's not an interesting visualizations.
t_tsonev 9y ago
It's a star map! Well, probably not.
chatmasta 9y ago
Here's what a 3d projection of it looks like ("prime numbers projected in the z-axis to their values"): https://www.youtube.com/watch?v=dJ0murDJgf4 https://www.youtube.com/watch?v=dJ0murDJgf4 And another one with a different technique ("viewed as a surface such that -1 is a prime and 0 is a composite number"): https://www.youtube.com/watch?v=ECgsgC13ILg https://www.youtube.com/watch?v=ECgsgC13ILg
susam 9y ago
I once had a surprising moment when I plotted the graph of (p + q) vs. pq for primes p and q and observed the points forming streaks of dots. While surprising at first, it could be explained trivially with a little bit of analysis. I have saved the graph here: https://github.com/mycask/rsa-graph https://github.com/mycask/rsa-graph Spoiler Alert: The section named 'Streaks' right after the graph plot has spoilers.
BlackFly 9y ago
Isn't the answer to "Why do they cluster on diagonals?" Really mundane? The answer of course being: horizontal and vertical lines are forbidden because all non-diagonal neighbours of an odd number are even. Then your mind focuses on all the runs because that is what the human brain does.
- amvalo 9y ago
  Nope there is a real pattern -- they cluster along certain polynomials. Trying picking random points on the black squares of a chessboard (same condition that you stated), they won't make obvious lines like that.
  - nerdponx 9y ago
    Couldn't you simulate this pretty easily? You would need some kind of objective way to measure "diagonal clustering", but you could try to simulate numbers several thousands of times and then see if the observed amount of diagonal clustering is matched in some non-trivial fraction of the simulations.
- susam 9y ago
  It's not just the diagonal runs but the dense clusters along some diagonal lines that is considered to be an unsolved problem. Moreover, the clustering is not limited to just diagonal lines. There are less prominent but high density clusters along horizontal and vertical lines too.
- susam 9y ago
  Here is a quick experiment to show that the Ulam spiral indeed appears to have more prominent diagonal lines than a spiral of randomly chosen odd numbers even when the dimensions and the number of points in both spirals are same: https://github.com/mycask/ulam-vs-random https://github.com/mycask/ulam-vs-random I have plotted a 99x99 grid in this experiment. One can plot larger grids to see that the difference between the two grids (the Ulam spiral and the random spiral) becomes more apparent with larger sizes. Update: After I made these text-plots, I found that Wikipedia has much better graphical plots that demonstrates the difference: - Ulam spiral: https://en.wikipedia.org/wiki/File:Ulam_1.png https://en.wikipedia.org/wiki/File:Ulam_1.png - Random spiral: https://en.wikipedia.org/wiki/File:Randomly_black_odd_numbers.png https://en.wikipedia.org/wiki/File:Randomly_black_odd_number...
  - jwilk 9y ago
    > 200x200 spiral number grid with odd numbers that have a 23.38% chance of being coloured in black. This doesn't seem to take into account that big prime numbers are less "likely" than small ones.
DoctorOetker 9y ago
one should note that except for the number 2, all primes are odd so they are bound to be constrained to the "black squares of a chess board" so to speak
- goldenkey 9y ago
  The same applies to any set of the first n primes. Each prime generates a waveform that destructively adds. 2 eliminates all even numbers. 3 eliminates all multiples of 3 - but has some overlap with 2. Turns out the additive sequence to never hit any multiples of 2 or 3 is {+4, +2} Not much more complex than 'only the odd squares' yet now we are eliminating many more false positives. We can continue to construct the additive sequences for the first N primes. This is known as the First Differences of Reduced Residue Systems Modulo Primorials. Hardy and Littlewood studied the statistical dynamics of these ordered sets.
ptero 9y ago
This is very cool, thank you for sharing. I wonder if at least part of the structure comes from regular structure of major sequences of gaps (e.g., remove all even numbers and all factors of 3 and what is left is of the form 6k +/- 1). If so, I would expect those to wash out a little for larger squares. I have some plotting to do when I get home
jgtrosh 9y ago
> an awful lot of primes occur along the set of lines f(n) = 4n^2+n+c, for a variety of values of b and c. Should be “n and c”.
- hibbelig 9y ago
  I think it was intended to be f(n) = 4n^2 + bn + c.
emmelaich 9y ago
[2010]
- dang 9y ago
  Thanks, fixed.
aerovistae 9y ago
Semi-related, I once noticed an odd thing about low prime numbers which (as far as I know) nobody else has made note of: if you look at the natural numbers 1, 2, 3,...n, and keep track of how far each one is from a prime number, there are a lot of palindromic sequences in the progression. https://math.stackexchange.com/questions/1338059/why-are-there-palindromic-subsequences-at-random-among-this-sequence https://math.stackexchange.com/questions/1338059/why-are-the... I am not particularly talented with programming mathematical quandaries, but if anyone else wanted to analyze this further, it could perhaps be an avenue to interesting results.
- soVeryTired 9y ago
  I think your obervation is due to palindromes in the differences between primes themselves. I worked through your example for the integers 8 to 16, the sequence being 3 2 3 0 1 0 3 2 3. The sequence of numbers we observe is due entirely to the locations of the primes 5, 7, 11, 13, 17, and 19. The differences between these primes is 2, 4, 2, 4, 2, which is again a palindrome. I wouldn't be surprised if that's the reason your original sequence is palindromic. If it is, the question is then whether palindromes in distances between primes are unusually common.
  - aerovistae 9y ago
    You are correct! Great observation.
    - soVeryTired 9y ago
      Weird, someone else pointed out the same thing on stackexchange around the same time I did. I guess they must have come from here.
      - aerovistae 9y ago
        I was wondering if you were the same person with different account names on different sites! Evidently not.
      - 9y ago
TheWoodsy 9y ago
Something that I've always wondered is what these prime spirals would look like in greater than 2 dimensions.
- zwkrt 9y ago
  I wonder if there are any 3d space-filling curves that "make sense" for this type of analysis. You somehow have to wrap points around (0,0,0) in a way that has nice properties like the spiral. For instance, zig-zagging around a 3d box [1] Probably has too many 2d "artifacts" (I'm not a mathematician). The 2d spiral has these really nice properties that contiguous numbers are adjacent, it is approximately symmetric for any rotation in R2, and each number is only +ε farther away from the origin. [1]http://vgalt.com/wp-content/uploads/2009/10/3d-labyrinth.jpg http://vgalt.com/wp-content/uploads/2009/10/3d-labyrinth.jpg
silveira 9y ago
Here is some HTML5+Javascript code for Ulam spirals if you want to play with it. http://silveiraneto.net/2013/05/14/twin-primes-visualized-over-an-ulam-spiral-in-html5/ http://silveiraneto.net/2013/05/14/twin-primes-visualized-ov...
thomasahle 9y ago
This is probably related to Prime Generating Polynomials [1]. Euler first noticed that `n^2 + n + 41` is prime for the 40 integers n = 0, 1, 2, ..., 39. A second-order polynomial should look more or less like a line when plotted around a spiral like this. There are also third-order prime polynomials, which you might be able to see when visualizing the primes in 3d. [1]: http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
- xyzzyz 9y ago
  Yes, that's right. The real question is, why some quadratic polynomials are so rich with primes? Nobody really has any idea.
- mgsouth 9y ago
  It's simpler than that. All primes greater than 2 are equal to 2n + 1 for some n. And since each side of a spiral is 2 longer than the adjacent one, you get a slanted line. You'd have just a blob of bunches of line, except that they thin out. (Primes > 6 are 2 * 3 * n +/- 1, then 2 * 3 * 5 * n +/- [1, 7, 11, 13]. Also, prime series are palindromic. Integers relatively prime to (2, 3, ... p[m]) form a repeating series with period 2 * 3 * ... * p[m], and within each series they are the integers not "knocked out" by the given primes; e.g., 2 * 3 * ... * p[m] +/- [p[m+1], p[m+2], ...]. So the pattern is symmetrical over the period.
  - deleted 9y ago
    [deleted]
_bxg1 9y ago
This could be an interesting application for machine learning. Train it to notice what defines an "interesting" geometrical pattern and then have it graph prime numbers in thousands of different ways and see what it finds. You could even apply it to things like colors, waveforms, etc.
clay_to_n 9y ago
The electronic musician Max Cooper used the Sacks Spiral in his live AV setup for his album Emergence. His lecture isn't the most concise but he touches on a lot of things that might be interesting to this crowd. He talks about the Sacks Spiral at about 3 minutes into this: https://www.youtube.com/watch?v=VFjIk_CnRUM https://www.youtube.com/watch?v=VFjIk_CnRUM He also sells a t-shirt with it for the music or math nerds interested: https://everpress.com/max-cooper https://everpress.com/max-cooper
hateful 9y ago
If you had square blocks and arrange them, having a prime number of blocks means that you can't arrange them in a rectangle. So I would think (as a non-mathematician) that it shouldn't be surprising that the "corners" would appear when doing this. Or rather the non-corners.
DanBC 9y ago
A different page got submitted a while ago, and it has more detail: http://www.numberspiral.com/index.html http://www.numberspiral.com/index.html https://news.ycombinator.com/item?id=13296129 https://news.ycombinator.com/item?id=13296129
evincarofautumn 9y ago
Whenever I see prime visualisations, I go down a rabbit hole of investigating prime numbers in search of a better factoring algorithm. I’m no great mathematician, so I always come up better educated but ultimately fruitless. :) I have this nagging idea, though, that there must be a deep relationship among: 1. the polynomials on which the primes are clustered in the Ulam spiral, 2. algorithms to factor numbers, and 3. recovering information “destroyed” by addition. That is, if you ask me to find the factors of C = A × B, the information about which prime factors went into that product is preserved by multiplication, but if you ask me for the factors of C = A + B, I can’t say much about how the factors of A and B relate to those of C, can I? But if I could, I suspect I could factor numbers efficiently. Something something information theory something entropy… Anyone have any pointers to reading materials along these lines?
acoye 9y ago
Numberfile did a nice video on this phenomena. https://www.youtube.com/watch?v=iFuR97YcSLM https://www.youtube.com/watch?v=iFuR97YcSLM

109 points by dvfjsdhgfv 9y ago

Now I'm thinking about schemes where you iterate through lots of different permutations of visualizations, in at least two and three dimensions, and then somehow calculate a score for how interesting the pattern is. Maybe using a sort of contrast algorithm like autofocus for a camera. If it looks noisy and random, then that's not an interesting visualizations.

t_tsonev 9y ago

It's a star map! Well, probably not.

chatmasta 9y ago

Here's what a 3d projection of it looks like ("prime numbers projected in the z-axis to their values"): https://www.youtube.com/watch?v=dJ0murDJgf4 https://www.youtube.com/watch?v=dJ0murDJgf4 And another one with a different technique ("viewed as a surface such that -1 is a prime and 0 is a composite number"): https://www.youtube.com/watch?v=ECgsgC13ILg https://www.youtube.com/watch?v=ECgsgC13ILg

susam 9y ago

I once had a surprising moment when I plotted the graph of (p + q) vs. pq for primes p and q and observed the points forming streaks of dots. While surprising at first, it could be explained trivially with a little bit of analysis. I have saved the graph here: https://github.com/mycask/rsa-graph https://github.com/mycask/rsa-graph Spoiler Alert: The section named 'Streaks' right after the graph plot has spoilers.

BlackFly 9y ago

Isn't the answer to "Why do they cluster on diagonals?" Really mundane? The answer of course being: horizontal and vertical lines are forbidden because all non-diagonal neighbours of an odd number are even. Then your mind focuses on all the runs because that is what the human brain does.

amvalo 9y ago
Nope there is a real pattern -- they cluster along certain polynomials. Trying picking random points on the black squares of a chessboard (same condition that you stated), they won't make obvious lines like that.
- nerdponx 9y ago
  Couldn't you simulate this pretty easily? You would need some kind of objective way to measure "diagonal clustering", but you could try to simulate numbers several thousands of times and then see if the observed amount of diagonal clustering is matched in some non-trivial fraction of the simulations.
susam 9y ago
It's not just the diagonal runs but the dense clusters along some diagonal lines that is considered to be an unsolved problem. Moreover, the clustering is not limited to just diagonal lines. There are less prominent but high density clusters along horizontal and vertical lines too.
susam 9y ago
Here is a quick experiment to show that the Ulam spiral indeed appears to have more prominent diagonal lines than a spiral of randomly chosen odd numbers even when the dimensions and the number of points in both spirals are same: https://github.com/mycask/ulam-vs-random https://github.com/mycask/ulam-vs-random I have plotted a 99x99 grid in this experiment. One can plot larger grids to see that the difference between the two grids (the Ulam spiral and the random spiral) becomes more apparent with larger sizes. Update: After I made these text-plots, I found that Wikipedia has much better graphical plots that demonstrates the difference: - Ulam spiral: https://en.wikipedia.org/wiki/File:Ulam_1.png https://en.wikipedia.org/wiki/File:Ulam_1.png - Random spiral: https://en.wikipedia.org/wiki/File:Randomly_black_odd_numbers.png https://en.wikipedia.org/wiki/File:Randomly_black_odd_number...
- jwilk 9y ago
  > 200x200 spiral number grid with odd numbers that have a 23.38% chance of being coloured in black. This doesn't seem to take into account that big prime numbers are less "likely" than small ones.

DoctorOetker 9y ago

one should note that except for the number 2, all primes are odd so they are bound to be constrained to the "black squares of a chess board" so to speak

goldenkey 9y ago
The same applies to any set of the first n primes. Each prime generates a waveform that destructively adds. 2 eliminates all even numbers. 3 eliminates all multiples of 3 - but has some overlap with 2. Turns out the additive sequence to never hit any multiples of 2 or 3 is {+4, +2} Not much more complex than 'only the odd squares' yet now we are eliminating many more false positives. We can continue to construct the additive sequences for the first N primes. This is known as the First Differences of Reduced Residue Systems Modulo Primorials. Hardy and Littlewood studied the statistical dynamics of these ordered sets.

ptero 9y ago

This is very cool, thank you for sharing. I wonder if at least part of the structure comes from regular structure of major sequences of gaps (e.g., remove all even numbers and all factors of 3 and what is left is of the form 6k +/- 1). If so, I would expect those to wash out a little for larger squares. I have some plotting to do when I get home

jgtrosh 9y ago

> an awful lot of primes occur along the set of lines f(n) = 4n^2+n+c, for a variety of values of b and c. Should be “n and c”.

hibbelig 9y ago
I think it was intended to be f(n) = 4n^2 + bn + c.

emmelaich 9y ago

[2010]

dang 9y ago
Thanks, fixed.

aerovistae 9y ago

Semi-related, I once noticed an odd thing about low prime numbers which (as far as I know) nobody else has made note of: if you look at the natural numbers 1, 2, 3,...n, and keep track of how far each one is from a prime number, there are a lot of palindromic sequences in the progression. https://math.stackexchange.com/questions/1338059/why-are-there-palindromic-subsequences-at-random-among-this-sequence https://math.stackexchange.com/questions/1338059/why-are-the... I am not particularly talented with programming mathematical quandaries, but if anyone else wanted to analyze this further, it could perhaps be an avenue to interesting results.

soVeryTired 9y ago
I think your obervation is due to palindromes in the differences between primes themselves. I worked through your example for the integers 8 to 16, the sequence being 3 2 3 0 1 0 3 2 3. The sequence of numbers we observe is due entirely to the locations of the primes 5, 7, 11, 13, 17, and 19. The differences between these primes is 2, 4, 2, 4, 2, which is again a palindrome. I wouldn't be surprised if that's the reason your original sequence is palindromic. If it is, the question is then whether palindromes in distances between primes are unusually common.
- aerovistae 9y ago
  You are correct! Great observation.
  - soVeryTired 9y ago
    Weird, someone else pointed out the same thing on stackexchange around the same time I did. I guess they must have come from here.
    - aerovistae 9y ago
      I was wondering if you were the same person with different account names on different sites! Evidently not.
    - 9y ago

TheWoodsy 9y ago

Something that I've always wondered is what these prime spirals would look like in greater than 2 dimensions.

zwkrt 9y ago
I wonder if there are any 3d space-filling curves that "make sense" for this type of analysis. You somehow have to wrap points around (0,0,0) in a way that has nice properties like the spiral. For instance, zig-zagging around a 3d box [1] Probably has too many 2d "artifacts" (I'm not a mathematician). The 2d spiral has these really nice properties that contiguous numbers are adjacent, it is approximately symmetric for any rotation in R2, and each number is only +ε farther away from the origin. [1]http://vgalt.com/wp-content/uploads/2009/10/3d-labyrinth.jpg http://vgalt.com/wp-content/uploads/2009/10/3d-labyrinth.jpg

silveira 9y ago

Here is some HTML5+Javascript code for Ulam spirals if you want to play with it. http://silveiraneto.net/2013/05/14/twin-primes-visualized-over-an-ulam-spiral-in-html5/ http://silveiraneto.net/2013/05/14/twin-primes-visualized-ov...

thomasahle 9y ago

This is probably related to Prime Generating Polynomials [1]. Euler first noticed that `n^2 + n + 41` is prime for the 40 integers n = 0, 1, 2, ..., 39. A second-order polynomial should look more or less like a line when plotted around a spiral like this. There are also third-order prime polynomials, which you might be able to see when visualizing the primes in 3d. [1]: http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

xyzzyz 9y ago
Yes, that's right. The real question is, why some quadratic polynomials are so rich with primes? Nobody really has any idea.
mgsouth 9y ago
It's simpler than that. All primes greater than 2 are equal to 2n + 1 for some n. And since each side of a spiral is 2 longer than the adjacent one, you get a slanted line. You'd have just a blob of bunches of line, except that they thin out. (Primes > 6 are 2 * 3 * n +/- 1, then 2 * 3 * 5 * n +/- [1, 7, 11, 13]. Also, prime series are palindromic. Integers relatively prime to (2, 3, ... p[m]) form a repeating series with period 2 * 3 * ... * p[m], and within each series they are the integers not "knocked out" by the given primes; e.g., 2 * 3 * ... * p[m] +/- [p[m+1], p[m+2], ...]. So the pattern is symmetrical over the period.
- deleted 9y ago
  [deleted]

_bxg1 9y ago

This could be an interesting application for machine learning. Train it to notice what defines an "interesting" geometrical pattern and then have it graph prime numbers in thousands of different ways and see what it finds. You could even apply it to things like colors, waveforms, etc.

clay_to_n 9y ago

The electronic musician Max Cooper used the Sacks Spiral in his live AV setup for his album Emergence. His lecture isn't the most concise but he touches on a lot of things that might be interesting to this crowd. He talks about the Sacks Spiral at about 3 minutes into this: https://www.youtube.com/watch?v=VFjIk_CnRUM https://www.youtube.com/watch?v=VFjIk_CnRUM He also sells a t-shirt with it for the music or math nerds interested: https://everpress.com/max-cooper https://everpress.com/max-cooper

hateful 9y ago

If you had square blocks and arrange them, having a prime number of blocks means that you can't arrange them in a rectangle. So I would think (as a non-mathematician) that it shouldn't be surprising that the "corners" would appear when doing this. Or rather the non-corners.

DanBC 9y ago

A different page got submitted a while ago, and it has more detail: http://www.numberspiral.com/index.html http://www.numberspiral.com/index.html https://news.ycombinator.com/item?id=13296129 https://news.ycombinator.com/item?id=13296129

evincarofautumn 9y ago

Whenever I see prime visualisations, I go down a rabbit hole of investigating prime numbers in search of a better factoring algorithm. I’m no great mathematician, so I always come up better educated but ultimately fruitless. :) I have this nagging idea, though, that there must be a deep relationship among: 1. the polynomials on which the primes are clustered in the Ulam spiral, 2. algorithms to factor numbers, and 3. recovering information “destroyed” by addition. That is, if you ask me to find the factors of C = A × B, the information about which prime factors went into that product is preserved by multiplication, but if you ask me for the factors of C = A + B, I can’t say much about how the factors of A and B relate to those of C, can I? But if I could, I suspect I could factor numbers efficiently. Something something information theory something entropy… Anyone have any pointers to reading materials along these lines?

acoye 9y ago

Numberfile did a nice video on this phenomena. https://www.youtube.com/watch?v=iFuR97YcSLM https://www.youtube.com/watch?v=iFuR97YcSLM