The Ulam Spiral of Primes (2010) | Hacker News Reader

The Ulam Spiral of Primes (2010)

scienceblogs.com

109 pointsdvfjsdhgfv43 comments

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

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.

You are correct! Great observation.

Weird, someone else pointed out the same thing on stackexchange around the same time I did. I guess they must have come from here.

I was wondering if you were the same person with different account names on different sites! Evidently not.

I also came close to pointing that out, and then I noticed that it only makes palindromes of this sequence more probable, rather than guaranteeing them (see my comment on Math SE).

It looks like the Online Encyclopedia of Integer Sequences has some information on your series [1]. Always an interesting place to start going down a rabbit hole.

[1] https://oeis.org/A047160

And this one with just the distances between primes:

https://oeis.org/A001223

A lot of references for that sequence.

Fascinating stuff... The palindrome observation of the OP might just be that we are good at finding patterns and there are limited numbers of distances with lower numbered primes (and from the graph of your reference it looks like a lot of the distances are concentrated in smaller numbers -- max dist increasing logarithmically?)

I wonder if the palindrome conjecture can be posed mathematically or algorithmically (seems like it should). It would be interesting to test palindromes to a certain number compared to palindromes of a similarly distributed set of random numbers. Counting all palindromes of any size will probably be a significant big O.

Now I'm just trying to keep myself from looking at the Collatz Conjecture. :)

Prime series are palindromic. Given the set of primes (2, 3, 5, ..., p[m]), there is a repeating pattern of length r = 2 * 3 * ... * p[m], where nr +/- [ p[m+1], p[m+2], ... p[m+q] ] (p[m+q] < r/2) are relatively prime to the given set. When n = 1, the only relatively prime integers which aren't truly prime are those which are some combination of two or more p[m+1] ... p[m+q]; the smallest is of course p[m+1] ^ 2.

Possibly related:

https://en.wikipedia.org/wiki/Riemann_hypothesis

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

Yes, that's right. The real question is, why some quadratic polynomials are so rich with primes? Nobody really has any idea.

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.

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

Spoiler Alert: The section named 'Streaks' right after the graph plot has spoilers.

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

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

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.

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.

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.

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.

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

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

- Random spiral: https://en.wikipedia.org/wiki/File:Randomly_black_odd_number...

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

Yes, if you take into account all factors that might cause diagonal streaks more likely on real spiral as opposed to random grid, you might actually find out the real cause of this strange fact.

IIRC the pattern still arises even if you generate pseudo-primes randomly.

The square root plays a role in the distribution of primes as well as in the area of a circle. The former is involved in an upper bound for the numbers to be checked performing Sieve of Eratosthenes.

Here's another page who does this.

http://ulamspiral.com/generatePage.asp?ID=1

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.

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?

A different page got submitted a while ago, and it has more detail: http://www.numberspiral.com/index.html

https://news.ycombinator.com/item?id=13296129

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

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

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

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.

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

He also sells a t-shirt with it for the music or math nerds interested: https://everpress.com/max-cooper

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

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

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.

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.

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

[2010]

Thanks, fixed.

It's a star map!

Well, probably not.

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

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

Reply on news.ycombinator.com