31:T6a1,md`A Gaussian integer is usually written in the form ${tex`a + bi`}, where ${tex`i^2 = -1`} and ${tex`a`} and ${tex`b`} are integers. In the Gaussian integers, multiplication takes the form ${tex`\left(a + bi\right) \left(c + di\right) = \left.(ac - bd\right) + \left(ad + bc)i\right.\!.`} The norm of a Gaussian integer is square of its absolute value, the product of the number and its conjugate, ${tex`\left|a + bi\right|^2 = \left(a + bi\right)\left(a + bi^{-1}\right) = \left.a^2 + b^2\right.\!.`} As with the ordinary integers, any Gaussian integer is either a unit (an integer with a multiplicative inverse, ${tex`\{\pm 1, \pm i\}`} in this case), prime (a number ${tex`p`} such that if ${tex`p`} divides ${tex`xy`}, then ${tex`p`} necessarily divides either ${tex`x`} or ${tex`y`}), or composite (a product of primes). For example, the Gaussian integer ${tex`2 = (1 + i)(1 - i)`} is composite. One way of determining the Gaussian primes is to make a [prime sieve](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) (as seen for the integers in [@tmcw/sieve-of-eratosthenes](@tmcw/sieve-of-eratosthenes), [@mbostock/the-sieve-of-eratosthenes](../@mbostock/the-sieve-of-eratosthenes), and [@mourner/fast-prime-generator](../@mourner/fast-prime-generator)) directly in terms of Gaussian integers. An alternative is to use integer primes as a shortcut. Any Gaussian integer ${tex`a + bi`} is a prime if either it is a product of a unit and an integer prime satisfying ${tex`p \equiv 3 \pmod 4`} (that is, ${tex`3, 7, 11, 19, 23, \ldots`}) or its norm is an integer prime (notice, ${tex`|q|^2 \not\equiv 3 \pmod 4`} for any Gaussian prime ${tex`q`}). `32:T4d9,md` An Eisenstein integer is usually written in the form ${tex`a + b\omega`} where ${tex`\omega(1 + \omega) = -1`}, and ${tex`a`} and ${tex`b`} are integers. In the Eisenstein integers multiplication takes the form ${tex`\left.(a + b\omega) \cdot (c + d\omega)\right. = \left.(ac - bd) + (ad + bc - bd)\omega\right.\!.`} The norm of an Eisenstein integer is ${tex`|a + b\omega|^2 = (a + b\omega)(a + b\omega^{-1}) = \left.a^2 - ab + b^2\right.\!.`} As with the ordinary integers, any Eisenstein integer is either a unit (an integer with a multiplicative inverse, ${tex`\{\pm 1, \pm \omega, \pm \omega^{-1} \}`} in this case), prime (a number ${tex`p`} such that if ${tex`p`} divides ${tex`xy`}, then ${tex`p`} necessarily divides either ${tex`x`} or ${tex`y`}), or composite (a product of primes). For example, the Eisenstein integer ${tex`7 = (3 + \omega)(3 + \omega^{-1})`} is composite. As with Gaussian primes, we can use integer primes as a shortcut in computing Eisenstein primes. Any Eisenstein integer ${tex`a + b\omega`} is a prime if either it is a product of a unit and an integer prime satisfying ${tex`p \equiv 2 \pmod 3`} (that is, ${tex`2, 5, 11, 17, 23, \ldots`}) or its norm is an integer prime. `33:[] 2f:{"title":"Gaussian and Eisenstein Primes","cells":[{"id":0,"value":"md`# Gaussian and Eisenstein Primes`","pinned":false,"hidden":false,"mode":"ojs"},{"id":606,"value":"md`The [Gaussian integers][] are points in the [complex plane][] on a square [grid][] of unit spacing, based on a primitive 4th [root of unity][] ${tex`i^4 = 1`}. The [Eisenstein integers][] are complex points on a hexagonal grid of unit spacing, based on a primitive 3rd root of unity ${tex`\\omega^3 = 1`}. Both are [Euclidean domains][].\n\n [Gaussian integers]: https://en.wikipedia.org/wiki/Gaussian_integer\n [complex plane]: https://en.wikipedia.org/wiki/Complex_plane\n [grid]: https://en.wikipedia.org/wiki/Lattice_(group)\n [root of unity]: https://en.wikipedia.org/wiki/Root_of_unity\n [Eisenstein integers]: https://en.wikipedia.org/wiki/Eisenstein_integer\n [Euclidean domains]: https://en.wikipedia.org/wiki/Euclidean_domain\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":237,"value":"{\n let width = figureWidth;\n let w = width/2;\n let v = 24;\n let m = 2*v;\n return svg`\n`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":338,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":663,"value":"md`* * *`","pinned":false,"hidden":false,"mode":"ojs"},{"id":124,"value":"{ \n let SQRT3 = Math.sqrt(3);\n let c = Math.sqrt(3/4)\n let width = figureWidth;\n let w = width/2;\n let v = 24;\n let m = Math.floor(1.6*v);\n return svg`\n`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":461,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":385,"value":"figureWidth = Math.min(width, 600)","pinned":false,"hidden":false,"mode":"ojs"},{"id":620,"value":"import {range} from '@jrus/itertools'","pinned":false,"hidden":false,"mode":"ojs"},{"id":226,"value":"gprimes_sector = (n) =>\n range(n).flatMap(i => range(i).map(j => [j, i-j])).filter(isgprime)","pinned":true,"hidden":false,"mode":"ojs"},{"id":10,"value":"eprimes_sector = (n) =>\n range(n).flatMap(i => range(i).map(j => [j, i-j])).filter(iseprime)","pinned":true,"hidden":false,"mode":"ojs"},{"id":221,"value":"isgprime = ([x, y]) => gprime_norms.has(x*x + y*y)","pinned":true,"hidden":false,"mode":"ojs"},{"id":67,"value":"iseprime = ([x, y]) => eprime_norms.has(x*x + y*y + x*y)","pinned":true,"hidden":false,"mode":"ojs"},{"id":229,"value":"gprimes = (n) => gprimes_sector(n).flatMap((X) => {\n let Y = X;\n return [Y, Y=grotate(Y), Y=grotate(Y), Y=grotate(Y)]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":170,"value":"eprimes = (n) => eprimes_sector(n).flatMap((X) => {\n let Y = X;\n return [Y, Y=erotate(Y), Y=erotate(Y), Y=erotate(Y), Y=erotate(Y), Y=erotate(Y)]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":38,"value":"erotate = ([Cx, Cy]) => [Cx + Cy, -Cx]","pinned":true,"hidden":false,"mode":"ojs"},{"id":234,"value":"grotate = ([Cx, Cy]) => [-Cy, Cx]","pinned":true,"hidden":false,"mode":"ojs"},{"id":46,"value":"// Adapted from @tmcw/sieve-of-eratosthenes\nprimes = {\n let n = 1e5;\n let candidates = (new Array(n)).fill(true);\n candidates[0] = candidates[1] = false;\n for (let i = 2; i < Math.sqrt(n); i++) {\n if (!candidates[i]) continue;\n for (let j = i + i; j < n; j += i) candidates[j] = false;\n }\n return candidates\n .map((x, i) => x ? i : false)\n .filter(x => x);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":76,"value":"eprime_norms = new Set(primes.map(x => ((x % 3) === 2) ? x*x : x))","pinned":true,"hidden":false,"mode":"ojs"},{"id":217,"value":"gprime_norms = new Set(primes.map(x => ((x % 4) === 3) ? x*x : x))","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}