4 ms·

Prime Number Diagrams in Python and SVG

33 points by angeladur 14y ago

anonymouz 14y ago
The article essentially looks at the distribution of primes modulo a fixed number m (here m=40). Each "ray" of the diagram corresponds to a residue class modulo 40. As the author observes, if x and m share a common divisor, then there can be at most one prime congruent x modulo m [3]. The interesting classes are those with gcd(x,m) = 1. For those Dirichlet's Theorem on primes in arithmetic progressions [1] tells us that we will in fact find infinitely many primes in these residue classes. More refined, the prime number theorem for arithmetic progressions [2] tells us something about their distribution. As for the squares of primes: If m = 40 then the residue classes modulo m which will contain infinitely many primes can be represented by: 1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37 Therefore the only residue classes in which infinitely many square of primes can lie are the squares of these residue classes, which turn out to be represented by 1 and 9 modulo 40 (just square the previous numbers and take remainders of dividing by 40). This explains why all but finitely many of the squares of primes lie in the two rays corresponding to these residue classes. [1] https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arith... [2] https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_number_theorem_for_arithmetic_progressions https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_num... [3] Suppose d = gcd(x,m). If y is congruent x mod m, then m divides y-x. Since d therefore divides x and y-x, it divides y. If d is not 1, then y can only be a prime if y=d and d is a prime. (one more edit): We can also say which classes will contain a single prime and which ones will contain a unique prime square: If p is a prime that has a common divisor with m, then p mod m will contain a single prime (p itself). Then p^2 mod m will contain a single prime square (well, p^2). In the case m=40, we have that 2 and 5 are the prime divisors of 40. Therefore the residue classes represented by 2 and 5 contain a single prime, and those represented by 4 and 25 contain a single prime square.
alexkus 14y ago
p^2 mod 40 being one of a small set of numbers is related to quadratic reciprocity. All odd numbers have a p^2 mod 40 value that is 1, 9 or 25. The margin isn't big enough for my proof, but only odd numbers with a multiple of 5 will have a p^2 mod 40 value that is 25. Once you remove the case for p=5 (by ignoring the 'inner ring' of numbers where p^2 < 40) then the only valid residues for odd numbers (that aren't multiples of 5) are 1 or 9, but, more importantly this is true whether they are prime or not.
sbandyopadhyay 14y ago
I tried coming up with a proof, but instead I have a new observation I can't explain: FACT: No prime number can end in an even number (because all such numbers are divisible by 2) or in 5 (because all such numbers are divisible by 5). So, all prime numbers must end in: 1, 3, 7, or 9. FACT: When you multiply 2 numbers, the units digit of the product is the same as the units digit of the product of the units digits of the two numbers. FACT: Combining the last two facts, every prime number squared must end in 1 (if the prime ended in 1 or 9) or 9 (if the prime ended in 3 or 7). FACT: Thus, every prime square modulo 40 must be one of the following numbers (and cannot be any other number): 1, 9, 11, 19, 21, 29, 31, or 39. So, I just have to figure out now why 6 of those 8 numbers can't be prime squares modulo 40. That's when I noticed something odd: no number x, such that x modulo 40 is 11, 19, 21, 29, 31, or 39, is a perfect square. (Tried this through x = 1 million.) Anyone know why that is?
- alexkus 14y ago
  https://en.wikipedia.org/wiki/Quadratic_residue https://en.wikipedia.org/wiki/Quadratic_residue also the Legendre symbol. Also there's no need to consider numbers >= 40 when working mod 40 47 * 47 (mod 40) = (40+7) * (40+7) (mod 40) 40 * n = 0 (mod 40) for any integer n since 40*n will be a multiple of 40, so:- = 40*(40+7) + 7*(40+7) (mod 40) = 0 + 7*(40+7) (mod 40) = 7 * (40+7) (mod 40) = 7*7 + 7*40 (mod 40) = 7*7 + 0 (mod 40) = 7*7 So n^2 (mod 40) = (n mod 40)^2 (mod 40).
e12e 14y ago
Apparently down due to heavy load. Unable to get anything from Coral Cache, but the text is in the google cache: http://webcache.googleusercontent.com/search?q=cache%3Ahttp%3A%2F%2Falphapixel.com%2Fcontent%2Fprime-number-diagrams-python-and-svg http://webcache.googleusercontent.com/search?q=cache%3Ahttp%...
jasondavies 14y ago
Site is down, but I think this is one of the images: http://imgur.com/07ukx http://imgur.com/07ukx
lubujackson 14y ago
Just a question - what is the advantage of putting this in a circle? Wouldn't these patterns exist just as well in a normal chart? The only difference is you don't see column 1 next to column 40 but that doesn't seem to have much impact.

33 points by angeladur 14y ago

The article essentially looks at the distribution of primes modulo a fixed number m (here m=40). Each "ray" of the diagram corresponds to a residue class modulo 40. As the author observes, if x and m share a common divisor, then there can be at most one prime congruent x modulo m [3]. The interesting classes are those with gcd(x,m) = 1. For those Dirichlet's Theorem on primes in arithmetic progressions [1] tells us that we will in fact find infinitely many primes in these residue classes. More refined, the prime number theorem for arithmetic progressions [2] tells us something about their distribution. As for the squares of primes: If m = 40 then the residue classes modulo m which will contain infinitely many primes can be represented by: 1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37 Therefore the only residue classes in which infinitely many square of primes can lie are the squares of these residue classes, which turn out to be represented by 1 and 9 modulo 40 (just square the previous numbers and take remainders of dividing by 40). This explains why all but finitely many of the squares of primes lie in the two rays corresponding to these residue classes. [1] https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arith... [2] https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_number_theorem_for_arithmetic_progressions https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_num... [3] Suppose d = gcd(x,m). If y is congruent x mod m, then m divides y-x. Since d therefore divides x and y-x, it divides y. If d is not 1, then y can only be a prime if y=d and d is a prime. (one more edit): We can also say which classes will contain a single prime and which ones will contain a unique prime square: If p is a prime that has a common divisor with m, then p mod m will contain a single prime (p itself). Then p^2 mod m will contain a single prime square (well, p^2). In the case m=40, we have that 2 and 5 are the prime divisors of 40. Therefore the residue classes represented by 2 and 5 contain a single prime, and those represented by 4 and 25 contain a single prime square.

alexkus 14y ago

p^2 mod 40 being one of a small set of numbers is related to quadratic reciprocity. All odd numbers have a p^2 mod 40 value that is 1, 9 or 25. The margin isn't big enough for my proof, but only odd numbers with a multiple of 5 will have a p^2 mod 40 value that is 25. Once you remove the case for p=5 (by ignoring the 'inner ring' of numbers where p^2 < 40) then the only valid residues for odd numbers (that aren't multiples of 5) are 1 or 9, but, more importantly this is true whether they are prime or not.

sbandyopadhyay 14y ago

I tried coming up with a proof, but instead I have a new observation I can't explain: FACT: No prime number can end in an even number (because all such numbers are divisible by 2) or in 5 (because all such numbers are divisible by 5). So, all prime numbers must end in: 1, 3, 7, or 9. FACT: When you multiply 2 numbers, the units digit of the product is the same as the units digit of the product of the units digits of the two numbers. FACT: Combining the last two facts, every prime number squared must end in 1 (if the prime ended in 1 or 9) or 9 (if the prime ended in 3 or 7). FACT: Thus, every prime square modulo 40 must be one of the following numbers (and cannot be any other number): 1, 9, 11, 19, 21, 29, 31, or 39. So, I just have to figure out now why 6 of those 8 numbers can't be prime squares modulo 40. That's when I noticed something odd: no number x, such that x modulo 40 is 11, 19, 21, 29, 31, or 39, is a perfect square. (Tried this through x = 1 million.) Anyone know why that is?

alexkus 14y ago
https://en.wikipedia.org/wiki/Quadratic_residue https://en.wikipedia.org/wiki/Quadratic_residue also the Legendre symbol. Also there's no need to consider numbers >= 40 when working mod 40 47 * 47 (mod 40) = (40+7) * (40+7) (mod 40) 40 * n = 0 (mod 40) for any integer n since 40*n will be a multiple of 40, so:- = 40*(40+7) + 7*(40+7) (mod 40) = 0 + 7*(40+7) (mod 40) = 7 * (40+7) (mod 40) = 7*7 + 7*40 (mod 40) = 7*7 + 0 (mod 40) = 7*7 So n^2 (mod 40) = (n mod 40)^2 (mod 40).

e12e 14y ago

Apparently down due to heavy load. Unable to get anything from Coral Cache, but the text is in the google cache: http://webcache.googleusercontent.com/search?q=cache%3Ahttp%3A%2F%2Falphapixel.com%2Fcontent%2Fprime-number-diagrams-python-and-svg http://webcache.googleusercontent.com/search?q=cache%3Ahttp%...

jasondavies 14y ago

Site is down, but I think this is one of the images: http://imgur.com/07ukx http://imgur.com/07ukx

lubujackson 14y ago

Just a question - what is the advantage of putting this in a circle? Wouldn't these patterns exist just as well in a normal chart? The only difference is you don't see column 1 next to column 40 but that doesn't seem to have much impact.