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.
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.
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.
>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.
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 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.
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?
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.
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.
[+] [-] westcort|2 years ago|reply
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.
[+] [-] tie_|2 years ago|reply
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.
[+] [-] bheadmaster|2 years ago|reply
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.
[+] [-] csense|2 years ago|reply
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.
[+] [-] eternalban|2 years ago|reply
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
[+] [-] kazinator|2 years ago|reply
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.
[+] [-] leoff|2 years ago|reply
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
[+] [-] jameshart|2 years ago|reply
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)
[+] [-] CGamesPlay|2 years ago|reply
[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
[+] [-] pcmaffey|2 years ago|reply
[+] [-] waitforit|2 years ago|reply
[+] [-] unknown|2 years ago|reply
[deleted]
[+] [-] quietbritishjim|2 years ago|reply
> 6k+3, or 6k-3.
These are the same collection of numbers, you meant to put 6k instead of one of them :-)
[+] [-] qikInNdOutReply|2 years ago|reply
[+] [-] hinkley|2 years ago|reply
[+] [-] kfrzcode|2 years ago|reply
isn't that sort of cheating, when it comes to math?
It's "almost" the thing just not the thing
[+] [-] Traubenfuchs|2 years ago|reply
[+] [-] hn_throwaway_99|2 years ago|reply
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.
[+] [-] y42|2 years ago|reply
https://primes.nickyreinert.de/
[+] [-] m3kw9|2 years ago|reply
[+] [-] mlyle|2 years ago|reply
Or multiply by 19.
[+] [-] MayeulC|2 years ago|reply
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.
[+] [-] b33j0r|2 years ago|reply
-1 is a circle, brah!
[+] [-] peter_retief|2 years ago|reply
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?
[+] [-] Scubabear68|2 years ago|reply
[+] [-] hn_throwaway_99|2 years ago|reply
[+] [-] kfrzcode|2 years ago|reply
[+] [-] Poppys|2 years ago|reply
[+] [-] harles|2 years ago|reply
[+] [-] anoncow|2 years ago|reply
[+] [-] desertraven|2 years ago|reply
[+] [-] smackeyacky|2 years ago|reply
https://www.abc.net.au/news/science/2018-01-20/how-prime-num...
[+] [-] C-x_C-f|2 years ago|reply
[0] https://terrytao.wordpress.com
[1] https://www.math.ucla.edu/~tao/preprints/Slides/primes.pdf
[+] [-] mathgenius|2 years ago|reply
[1] https://math.ucr.edu/home/baez/motives.pdf
[+] [-] Taywee|2 years ago|reply
[+] [-] timetraveller26|2 years ago|reply
[+] [-] frogpelt|2 years ago|reply
[+] [-] zmmmmm|2 years ago|reply
Seems the title is a bit misleading!
[+] [-] Bytewave81|2 years ago|reply
[+] [-] gnarbarian|2 years ago|reply
[+] [-] onethought|2 years ago|reply
[+] [-] rarx|2 years ago|reply
[+] [-] smitty1e|2 years ago|reply
As far as we know, for now.
[+] [-] jacknews|2 years ago|reply
https://i.imgur.com/yFMPmtW.png
[+] [-] aaron695|2 years ago|reply
[deleted]
[+] [-] SchoolDaze6|2 years ago|reply
[deleted]
[+] [-] LoudNProud|2 years ago|reply
[deleted]
[+] [-] HotMess23|2 years ago|reply
[deleted]
[+] [-] Amumulava5|2 years ago|reply
[deleted]