Why do prime numbers make these spirals? (2019) | Hacker News Reader

Why do prime numbers make these spirals? (2019)

3blue1brown.com

372 pointsnivethan100 comments

One of the thrills of studying the primes is the discovery that all primes greater than 3 are of the form 6k+1 or 6k-1. And for primes greater than 2, all primes are of the form 4k+1 or 4k-1. It is something that is commonly rediscovered by students, and that new independent finding was quite exciting for me.

The reasoning, which is in the article here, is that you can make any whole number you wish if the number is of the form 6k+1, 6k-1, 6k+2, 6k-2, 6k+3, or 6k-3. But you cannot make primes with the numbers of the form 6k+2, 6k-2 (they would always have to be divisible by 2), and you cannot makes primes with numbers of the form 6k+3, 6k-3 because they are always divisible by 3. So what are you left with? All primes >3 must of the form 6k+1 or 6k-1. And that factor 6 is just a bit less than 2 pi (a full turn in radians) so you get spirals from the offset. They are also a pixel or two off, but that is imperceptible.

The same logic is a nice exercise to apply to the problem of why primes >2 can only be of the form 4k+1 or 4k-1. Apply the same logic as above.

Yes, it was such a thrill to discover this in college (not a math major). I formulated it as all primes >2 are “factors” of 1 and 5 in a base 6 notation.

Well, factor is clearly the wrong technical term here, you probably meant the last digit? Like the last digit (remainder of modulo 10 division: p%10 in C-notation) of a prime number (p>5) in base 10 can be {1,3,7,9}.

And yes, in base 6 that becomes 1 and 5, as p%6 = 1 or 5, equivalent to p=6k±1. Interesting observation, thanks :)

This is neat and I never noticed this. For 5, I guess the linear component would be (2*3*5)k, but it isn't as interesting or useful because the constant component would be +/- 1, 7, 11, or 13. This method feels like it's basically a "higher order prime sieve".

[append] Oh, and because this pattern (of 1 always being one of the constants) carries out for arbitrarily large linear coefficients, that also explains the "twin prime" phenomenon: https://www.youtube.com/watch?v=QKHKD8bRAro

A “higher order prime sieve” indeed: https://en.wikipedia.org/wiki/Sieve_of_Pritchard

Isn't 4k+1/4k-1 rule trivial though?

If we take any number K=N*4 divisible by 4 and >2, that'd be an even number by definition. The two closest odd numbers on either side would be (K-3), (K-1), (K+1), (K+3). As it happens (K+3) is the same as K(-1) for the next N, and (K-3) is the same as (K+1) for the previous N. So _all_ odd numbers follow this rule.

What "4k+1 or 4k-1" says in a roundabout way is that all prime numbers (>2) are odd, which isn't much of a surprise.

So is the 6k±1 rule: 6k and 6k±2 are all even, 6k±3 is divisible by 3. You can extend this further: all primes greater than 5 must take one of the forms 30k±1, 30k±7, 30k±11, 30k±13. This is much less exciting, but ... suggestive. (No, not that suggestion, that one isn't actually true.)

For a certain point of view, most of math is trivial corollaries.

(Proof: check.)

I think this still seems trivial with a 5th grade algebra knowledge.

Additionally, for the 4k+1 / 4k-1 topic, it is just a complicated way of saying 2k+1 (as parent suggested).

Well I'm sure it looks trivial to you. But the joys of math often aren't in the difficulty but the discovery. Would your prefer it not have been stated at all, or did you just want to let us know you understood it.

As well, i think the 2k+1 thing is drastically more trivial and not at all equivalent being that all you need to know for 2k+1 is that 2k+1=odd. 4k and especially 6k take a larger generalization and different analytical method and often aren't included in the definition of the primes we learn like 2k+1 (odd) is.

Has anyone approached you about writing a math textbook yet? You've already got the tone perfected.

Somehow I find 30k +/- 1, 7, 11, 13 more pleasing. It's 8 numbers and the primality of each "group" can be encoded in a byte.

I have discovered the same thing while practicing prime sieve algorithms back in the day. Such properties of primes are quite useful for optimizing both speed and memory of sieve algorithms.

More generally, if you take the first n primes p_1, ..., p_n and define P=p_1*...*p_n, then all primes bigger than P be in the form of P*k +- a, such that a < P and GCD(P, a) = 1. In case of n=2 (P=2*3=6), there is this nice property that the only such a are 1 and 5 (which are equivalent), but in principle, the same can be done for any n. It's just that the set of all a has the size equal to Euler's totient function of P, which grows pretty fast as n increases.

For example, if n = 3, then P = 2*3*5 = 30, so all prime numbers bigger than 30 have to be in the form of 30k +- 1, 30k +- 7, 30k +- 11, 30k +- 13, 30k +- 17, 30k +- 19, 30k +- 23 or 30k +- 29 (notice that half of these are equivalent to the other half and can be ommitted). It is interesting that in this particular case, all a are either 1 or a prime less than P: I don't think that property holds for all n, though.

Indeed it's not, it's just anything coprime to P. This explains why there are always ±1s, and in particular why e.g. 210±1/210±209 are viable, even though 209=11*19.

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

You can also approximate pi as 22/7, which explains some of the other patterns that appear farther out.

> You can also approximate pi as 22/7

Except in Indiana, where the legal value of pi is 3.2 by mandate.

To be fair, this was proposed but not accepted by the state legislature (in 1879)

I'm curious why, even if you were going to approximate it, it would be rounded up to the nearest decimal rather than rounded in the standard way to 3.1?

The value 3.0 is better; then you can build hexagonal wheels.

Its the dimensionality? 2nd dimension, 3rd dimension and there permutation shadows? So by the mathematical principal, there is only one interesting permutation, and thats the "natural" one within the first dimension, aka 1 and 2s.

> imperceptible

isn't that sort of cheating, when it comes to math?

It's "almost" the thing just not the thing

Nah, it opens a whole new area of research. Everything is a great opportunity for new fun in maths.

You just have to properly define what you mean by "imperceptible" and you are good to go. Now you can look for a bounded approximation. See how it changes as things get bigger. See if it can be improved.

Bounds and approximation are generally a very useful tool. Properties simplifications and working on sub parts can also yield interesting results.

Generally I would say that if you can’t prove something, trying something close but simpler is nearly always a good idea.

To that extent, is there not a capital-N Natural bound even to math? I mean to say, consider the highest-order abstraction or system or whatever, and that itself is bounded by.. something - I suppose this is the ultimate philosophical question and exceeds what is pragmatic for human-sake, versus a pontificator's notions in passing.

What's k?

An integer.

A weird way of writing n?

More seriously, it’s an integer variable. By convention, letters from the middle of the alphabet are used for them (generally n then k).

Here, the commenter uses k because that’s what’s used in the article and that’s what’s used because n is already used to designate the class in the definition of a residue class.

Trivial correction:

> 6k+3, or 6k-3.

These are the same collection of numbers, you meant to put 6k instead of one of them :-)

> the discovery that ...

Wouldn't the vast majority of those studying primes learn this from their textbook?

Note that 6k-1 is the same as 6k + 5. By writing that way, we can focus in positive representations of the modulo 6 congruence.

6k + 0 can't be prime, it's divisible by 6, yielding k

6k + 1 might be prime: we cannot rule it out by division.

6k + 2 cannot be prime, it's divisible by 2, yielding 3k + 1.

6k + 3 cannot be prime, it's divisible by 3, yielding 2k + 1

6k + 4 cannot be prime, it's divisible by 2, yielding 3k + 2

6k + 5 might be prime again.

That covers all cases of the modulo 6 congruence.

Thus only 6k + 1 and 6k + 5 can possibly be prime.

This is trivial fluff, only a smidgeon more clever than "all primes greater than 2 are of the form 2k + 1".

Another line of reasoning:

If a number N is divisible by 6, then it is even. This means that N + 2 and N + 4 are also even. Thus none of those numbers are prime.

If a number N is divisible by 6, it is also divisible by 3. This means that N + 3 is also divisible by 3. Thus, it cannot be prime.

That leaves N + 1 and N + 5, whose divisibility doesn't relate to 6.

My textbook, at least, spent its space on the important axioms, theorems and corollaries. There were some easily-rediscovered results there, but mostly its pages described stuff that wasn't trivial to me.

And that's why it's one of the five books I have kept in the decades since.

Care to share the name of that textbook?

Authors called Edwards and Penney IIRC, but it's lent out this year.

Here is an exercise: does this generalize from 6 to any M > 2?

The 1 and 5 elements of the (modulo 6) congruence are precisely those which are relatively prime to 6: those two elements that Euler's totient function counts: φ(6) = 2.

It doesn't generalize trivially; there is osmething to puzzle out there. For instance in the case of M = 15, we have 8 being relatively prime to 15. Yet 15k + 8 might be composite (like in the case k = 0).

I may go into it more if I have a bit of time away from other interesting or urgent matters.

6k+1 might also be composite. However, it can be prime; a e.g. 6k+3 can literally never be prime, because it will always be divisible by 3.

Every prime p > 15 can be written as 15k + r, where r = p % 15 is coprime to 15. Put this way, it should be pretty clear what's going going on: gcd(15, r) is necessarily a factor of p, so we need that to be 1. Of course for prime p, gcd(p, q) is necessarily 1 for all q < p.

>all primes greater than 3 are of the form 6k+1 or 6k-1

what's the value in using this "formula"? We could also keep extending this rule, and say that all primes greater than 5 are of the form 30k±1, 30k±7, 30k±11, or 30k±13. Or go further by multiplying coefficient of X with the next primes

30k±1 = 6x±1 where x = 5k and so on. Why use four formulas when one will suffice?

For the same reason you'd use 6x±1 instead of 1+2n or, more basically, n - higher check hit rate at the cost of more complex checking rules.

This simple fact blows up into a bunch of even more surprising things that are true of all primes when you follow the algebra to its logical conclusions. Like:

Since this means every pair of twin primes > 3 must be separated by a multiple of 6, so they can be written as 6k+1, 6k-1. That means the product of any pair of twin primes will be of the form 36k^2-1.

In other words take any pair of twin primes, multiply them together, add 1, divide by 36, you are guaranteed to get a perfect square. E.g. 11*13=143, +1=144, /36=4 =2^2.

Or (and this one’s actually a little more complicated because it gets kind of casewise) you can show that the square of any prime (>3) is either one more or one less than a multiple of 24 (which is the product of the 6 and the 4 from the 6k and 4k rules)

That is because 6 is a priomorial. For any primorial p', k*p' +/- 1 will result in a number relatively prime to p', some of which are absolute primes.

The key to understanding primes is in relative primes and reduced residue sets. All patterns in (higher) primes (absolute) are generated by the members of RRS of smaller primes. This includes the clusters, such as twins, triple, quadruple, ..., primes. RRSs also hint [imo] at intimate connection between complex numbers and primes.

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

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

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

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

Let's think like a programmer implementing the sieve of Eratosthenes.

You can think of the sieve of Eratosthenes as starting with an infinite string of 1 bits, then for each prime p, you AND it with a periodic infinite string that's all 1's except for 0's at multiples of p. Then repeat until you get to sqrt(sieve_size), with the next p being the next 1 bit in the string.

AND is associative so you could alternatively AND together several of the periodic strings first, then you get a string whose period is the product of the periods.

Could you use that to optimize? Yes. For example if your big sieve is 1GB, naively you'd need to do four 1GB passes to knock out four consecutive primes, say 11, 13, 17, 19. But you can instead calculate the combined action of those primes by doing four passes over a (much smaller!) bit vector of size 11x13x17x19, then apply that in one pass over the main 1GB sieve. (I guess you'd want to tune the max size of the small bit vector based on your cache size.)

Further optimizations are possible, e.g. you could special-case the smallest primes. With a trivial indexing change, you can have your sieve bits represent odd numbers only, and halve the memory requirement (or double the largest prime you can find with a fixed amount of memory). Subsequent primes (e.g. knocking out multiples of 3 so your bit vector only contains bits representing numbers of the form 6k±1) involve less trivial changes to the indexing logic with diminishing returns.

I thought this video was fantastic. Just a great intro and example of how "playing" with numbers and visualizations can help you understand deeper, more profound concepts.

For commenters saying "well, doesn't anything in polar coordinates end up like spirals?", do yourself a favor and watch the video. He says as much pretty early on that yes, any plotting of the integers like that will look like spirals, but goes into excellent detail in my opinion explaining why the specific patterns you see with prime numbers are as they are.

Shameless self-promotion, just because it seems to fit: I build an "animation engine" around primes and spirals, just in case you need some distraction or you are bored:

https://primes.nickyreinert.de/

I can also make all integers look like sine waves sin(x)

Better divide x by something or you get a pretty crummy sine.

Or multiply by 19.

Or use the high-school sin. (Take's degrees as input)

y = (-1)**x

-1 is a circle, brah!

Tangentially, this is directly related to the article, as x*sin(x) is the x-component of plotting (x,x) in polar coordinates: with more precision (with x a real), you'd obtain a single spiral, but with integers where 2pi≈6, they appear as six.

Plotting primes p like this is plotting p*e^(ip), but the spirals are an interesting observation. You can straighten them out by adding a pi factor to the polar coordinate (so iside the sin...) but that's less interesting.

This is one of my favourite mysteries.

https://en.wikipedia.org/wiki/Goldbach%27s_conjecture

How is it that all even number are the sum of 2 primes and odd number the sum of 3 primes?

We don't know whether it's true.

Well, then it's a great mystery of up to 10^18: "T. Oliveira e Silva ran a distributed computer search that has verified the conjecture for n ≤ 4 × 10^18"

It is true but unproven.

The odd number sums follow from the fact about the even numbers.

Why though?

If you can make any even number with 2 primes, you can make an odd number by subtracting one odd prime from the odd number first (e.g. 3) and the resulting even number with 2 more primes.

I’m hardly a math genius, but isn’t this basically because he’s using polar coordinates, where nearly any trend is going to look like curves and spirals?

Hence, the video...

Hence the video what? It's polar coordinates making the spiral, not prime numbers.

The primes >3 are all of the form 6k+1 or 6k-1, so they are close to 6k. As k increases, the resulting marks on the polar coordinate system form nearly complete turns because 6 is close to 2 pi. Hence, spirals. See my other comment for a clearer explanation of why primes >3 all must necessarily be one more or one less than a factor of 6k where k is an integer. That is the crucial piece that the author did not make totally clear.

So what does it look like if you fudge it by scaling 2 pi down to 6 ?

A straight line of pillars.

This is pointed out in the video

Hence the video making it extremely clear pretty much right off the bat that yes, any integer plotted that way will form a spiral. The video then goes into a very interesting discussion IMO into why you see the specific patterns of spirals and rays with the primes.

It's because we live inside a spiral galaxy that's transitioning into a new galaxy type so we see through a spiral

Doesn't work in Australia.

My browser did not enjoy that 40MB web page.

It could use a (2019) in the title. Interesting, but not recent.

Does it matter for math articles? It’s not like the math has changed in 4 years.

Something has to define when new math came to be /s

I double checked, 1+1 is still 2 in ios 16.3.1

In 16.4.1, you have the opportunity to make it 4.15% bigger.

Sometimes it's hardware

https://en.m.wikipedia.org/wiki/Pentium_FDIV_bug

On the other hand 1+2+3 is 24 in iOS 11.1

There is an aspect of novelty when it comes to YouTube videos

> Does it matter for math articles

It matters for all the articles, so yes.

But, why does it matter for all articles? Is it just a blind rule, or can we apply it just when it actually makes sense?

The year in the title means: it is so good, it is worth reposting here.

It has less to do with math, and more to do with the conventions of posting to HN where people expect dates for non-recent links. There's nothing wrong with them otherwise.

The convention exists because for most articles, publication year is an important piece of context. I'm not sure we have to blindly follow the convention when it isn't.

Could there be a way to derive prime numbers based on an extrapolated graph which would be less resource intensive as compared to current prime identifying methods?

What's the commentary on prime numbers currently? Is it expected that there is some unfound pattern to them? Or will they always remain elusive?

Yes

No.

Maybe.

Elusiveness is subjective, but there's certainly plenty of patterns to be found (though, to be fair, what constitutes a pattern might also be subjective). You should check out Terence Tao's blog [0], he's not only one of the most prominent mathematicians in the field but he's also excellent at explaining things. These slides [1] for example don't require any background in math.

[0] https://terrytao.wordpress.com

[1] https://www.math.ucla.edu/~tao/preprints/Slides/primes.pdf

Prime numbers are important for cryptography - if there is a pattern to them it might have an effect on what we think is secure or not.

https://www.abc.net.au/news/science/2018-01-20/how-prime-num...

The answer to these questions is the Riemann hypothesis. John Baez just wrote a related paper about "motives" for beginners (undergrads?) [1]. It's worth a read even if you squint at the equations like i do, there's plenty of interesting commentary as well.

[1] https://math.ucr.edu/home/baez/motives.pdf

Bit of a let down when they reveal that plotting integers in general results in the same spiral pattern as primes. So naturally primes as a subset of integers also produce spirals.

Seems the title is a bit misleading!

A bit misleading I agree. I suppose since prime numbers DO make these spirals, it's not inaccurate.

We expect patterns from quotidian integers. The seeming chaos of primes, in contrast, brings the intrigue.

It's referencing the Math Stack Exchange question which asked the same question: https://math.stackexchange.com/questions/885879/meaning-of-r...

I don't know, for me the fact that this gives you a visualization of a totient is really interesting.

Another really interesting idea is to deliberately change the thing which you are rationally approximating; you don't have to rationally approximate π if you don't want to, that's just if you make steps of 1 radian. Make steps of q radians and you get the denominators for rational approximations of q/π.

This is used in the golden spiral algorithm[1] to evenly-ish distribute points on a sphere, we choose the most irrational number q/π = φ, the golden ratio. Since all of its rational approximations suck, the spirals are as inoffensive as they can be.

1. https://stackoverflow.com/questions/9600801/evenly-distribut...

Something less interesting is testing what the polar plot looks like if you plot the angle in degrees instead of radians. Or, like in this plot, where I defined 10 degrees as exactly one complete turn around the circle:

https://i.ibb.co/59k5dRT/polarplot.png

Slightly more interesting is what the primes look like when one complete turn is defined as 1, 2, 3... 30 units:

https://i.ibb.co/F0GvrSY/polarplot2.png

The whole point of the video is that asking these kinds of questions even if at first they seem kind of silly or arbitrary often lead to really interesting observations. In this case: Dirichlet's theorem on arithmetic progressions [0]

[0] https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arith...

I found it insightful, not a let down. It says a lot about human nature and our biases towards spotting patterns that may be incomplete or inaccurate.

In the absence of reliable telepathy, there is indeed survival value in spotting patterns in incomplete information.

I suspect most functions would make a spiral on a polar graph if you zoomed out far enough.

Well, except as the video points out - primes don't make spiral when you zoom out far enough, they make a "rays" pattern... which then if you zoom out even further becomes a much gentler spiral.

And the fact that pi is irrational means you will continue zooming out getting ever closer to rays, but never actually find rays - you’ll always have a slight spiral.

a factor, plus one. maybe? so it’s the pair of primes in that short sequence

> These patterns are certainly beautiful, but they don't have a hidden, divine message about primes.

As far as we know, for now.

Yeah, it's clearly someone's fingerprint:

https://i.imgur.com/yFMPmtW.png

Reply on news.ycombinator.com