Primes on space-filling curves

This is a variation on a theme by Ulam.  It is well-known that Ulam’s spiral is related to the high density of primes along some quadratic polynomials, as per Hardy & Littlewood’s conjecture F.

What about other curves, in particular space-filling curves like that of Peano or that of Hilbert ? Would one expect to see particular patterns ?

Well, not knowing what to expect, I’ve tried to look at Hilbert’s. Below are thus primes marked on iterations 7 and 8 of Hilbert’s curve, with also primes shown without the curve. (I’ve chosen the convention that has the first vertex at the top left corner, and I prefer not to show the quick and ugly code.)

End result : unfortunately I can’t quite spot anything too noticeable (that the primes avoid some diagonals is an easy consequence of the curve being built from units of 4 vertices, but beyond that…). Also, for some reason wouldn’t allow my svg files, so these are uglier png versions…

Edit (3rd august 2015): since primes do rarefy, it was tempting to look at a few more iterations and see if at least there are more around the top left corner on a larger scale. This is indeed seen in the plots of iteration 10 and 11 that I’ve added after the original ones. Iteration 11 contains 4,194,304 integers, and thus includes a fair amount of primes. But apart from the top left corner denser region the plots in fact look really uniform, despite lots of not too small prime gaps in these ranges, so there’s  really no pattern there.

primesonhilbert7 primesonhilbert7nocurve primesonhilbert8 primesonhilbert8nocurveAnd now iteration 10 and 11 (making the points on the 10th somewhat larger for better viewing).



5 Responses to “Primes on space-filling curves”

  1. Nima Says:

    Interesting try. And I would like to try this on other types of space feeling curves (the seach keywords that thankfully brought me here at the first place and spared me some time to avoid redundant work.)

    I think one of the [many] mysterious reasons that we get Ulam’s patterns for spirals is that Ulam’s and similar spirals are space feeling curves regular enough to rule out a group of non-primes (such as complete squares) on some geometric patterns in the 2D space and and thus leave other regions more likely for the prime numbers.

    Then to see similar patterns we need some other space filling curves (and not Peano / Hilbert) that can capture repeatetive behavior to spot and rule out at least a subset of non-primes on a diagonal or another curve.

    What are your thoughts on that?

    • Thomas Sauvaget Says:

      Yes, that’s another way of seeing things and should be investigated, although as I mentionned, Ulam’s pattern is not so mysterious according to conjecture F.

      I plotted the Hilbert one because it does have a regular iteration algorithm, so it was not clear to me whether or not some pattern could occur.

      Another line of thought (not related to space-filling curves, just to prime patterns) is to see what genetic algorithms can manage to generate. There has been one interesting attempt by James Alfred Walker and Julian Francis Miller using Cartesian Genetic Programming. There’s room for a lot of improvements and nice prime-generating algorithms there too I think.

  2. vinksis Says:

    I don’t get how can you have three consecutive points on the top left corner of the first image as primes. Am I interpreting it incorrectly?

    • Thomas Sauvaget Says:

      Probably. The top left corner is 0 and then you count from there as you go along the red curve, with the black dots being primes. So you can see that it is 0 1 2* 3* 4 5*… as it should be. The three you mention are 2, 3 and 13.

      • V Says:

        Ah I took a closer look again and noticed that the distances between points are different. I was looking at points 2,3 and 5. Points 3 and 5 lie on the same vertical line but the distance is twice the distance between 2 and 3. I didn’t notice this earlier and couldn’t understand how you could have three consecutive numbers as primes. Silly oversight! Thanks for your reply by the way.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: