Why do prime numbers make these spirals? (2019) • Hacker News Board

Re: Why do prime numbers make these spirals? (2019)

#101

Post by kazinator » Thu, Apr 27, 2023, 12:51 AM UTC

Arnt wrote: post #81

kazinator wrote: post #77

Earlier quoted context omitted.

> 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 c…

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.

Re: Why do prime numbers make these spirals? (2019)

#102

Post by kazinator » Thu, Apr 27, 2023, 12:53 AM UTC

viciousvoxel wrote: post #83

ihatepython wrote: post #60

Earlier quoted context omitted.

> You can also approximate pi as 22/7 Except in Indiana, where the legal value of pi is 3.2 by mandate.

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.

Re: Why do prime numbers make these spirals? (2019)

#103

Post by naniwaduni » Thu, Apr 27, 2023, 7:18 AM UTC

kazinator wrote: post #101

Arnt wrote: post #81

Earlier quoted context omitted.

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 i…

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.

Re: Why do prime numbers make these spirals? (2019)

#104

Post by csense » Thu, Apr 27, 2023, 2:49 PM UTC

westcort wrote: post #34

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…

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.