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.
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.
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.
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.
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.
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.
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.
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
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)
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
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 :)
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.
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?
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.
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.
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:
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.
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.
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"
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?
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.
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 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?
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.
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.
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.
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]
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.
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:
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.
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.