Hacker News Reader

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.

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

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.

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

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

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

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 :)

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.

Trivial correction:

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

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

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.

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.

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