Gaussian primes

Gaussian primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A Gaussian Integer is a complex number such that its real and imaginary parts are both integers.

   a + bi where a and b are integers and i is √-1.

The norm of a Gaussian integer is its product with its conjugate.

   N(a + bi) = (a + bi)(a − bi) = a² + b²

A Gaussian integer is a Gaussian prime if and only if either its norm is a prime number, or it is the product of a unit (±1, ±i) and a prime integer of the form 4n + 3.

Prime integers that are not of the form 4n + 3 can be factored into a Gaussian integer and its complex conjugate so are not a Gaussian prime.

   E.G. 5 = (2 + i)(2 − i) So 5 is not a Gaussian prime

Gaussian primes are octogonally symmetrical on a real / imaginary Cartesian field. If a particular complex norm a² + b² is prime, then the additive inverse b² + a² is also prime, as are the complex conjugates and multiplicative inverses of both.

Task

Find and show, here on this page, the Gaussian primes with a norm of less than 100, (within a radius of 10 from the origin 0 + 0i on a complex plane.)

Plot the points corresponding to the Gaussian primes on a Cartesian real / imaginary plane at least up to a radius of 50.

See also

• Wikipedia: Gaussian integers
• Wikipedia: Gaussian primes
• OEIS: Gaussian primes

J

Implementation: <lang J>isgpri=: {{

 if. 1 p: (*+) y do. 1 return. end.
 int=. |(+.y)-.0
 if. 1=#int do. {.(1 p: int) * 3=4|int else. 0 end.

}}"0</lang>

Plot of gaussian primes up to radius 50: <lang J> 1j1#"1'#' (<"1]50++.(#~ isgpri * 50>:|) ,j./~i:100)} '+' (<50 50)} '|' 50}"1 '-' 50} 100 100$' '

                                                                                                   |                                                                                                   
                                                                                       #   #       |       #   #                                                                                       
                                                                         #                         |                         #                                                                         
                                                                               #   #           #   #   #           #   #                                                                               
                                                             #       #       #           #         |         #           #       #       #                                                             
                                                                   #   #           #           #   |   #           #           #   #                                                                   
                                                         #   #       #           #                 |                 #           #       #   #                                                         
                                                       #                   #   #   #               #               #   #   #                   #                                                       
                                                 #   #           #       #               #         |         #               #       #           #   #                                                 
                                               #           #           #                   #       |       #                   #           #           #                                               
                                         #           #           #           #               #   # | #   #               #           #           #           #                                         
                                                                   #           #                   |                   #           #                                                                   
                                                 #   #           #   #   #           #       #     |     #       #           #   #   #           #   #                                                 
                                   #   #   #                   #                   #           #   |   #           #                   #                   #   #   #                                   
                                         #                   #                           #       # | #       #                           #                   #                                         
                               #               #   #   #       #   #               #           #   |   #           #               #   #       #   #   #               #                               
                             #           #               #           #       #   #       #         |         #       #   #       #           #               #           #                             
                                   #       #               #                       #           #   |   #           #                       #               #       #                                   
                         #       #           #       #               #   #               #   #     |     #   #               #   #               #       #           #       #                         
                                       #       #           #       #           #       #   #       #       #   #       #           #       #           #       #                                       
                         #           #   #           #                   #   #                     |                     #   #                   #           #   #           #                         
                   #       #   #       #                           #           #       #   #       |       #   #       #           #                           #       #   #       #                   
                         #       #               #                   #   #               #         |         #               #   #                   #               #       #                         
                                   #                   #   #                   #               #   |   #               #                   #   #                   #                                   
                 #           #       #           #       #                   #   #       #       # | #       #       #   #                   #       #           #       #           #                 
               #       #                   #   #   #   #           #   #   #           #   #       |       #   #           #   #   #           #   #   #   #                   #       #               
                             #                   #           #                           #       # | #       #                           #           #                   #                             
               #   #   #           #   #               #   #   #           #       #               #               #       #           #   #   #               #   #           #   #   #               
             #               #               #   #   #           #   #   #               #         |         #               #   #   #           #   #   #               #               #             
           #                   #               #                               #           #       |       #           #                               #               #                   #           
                 #               #   #       #       #       #           #   #       #       #   # | #   #       #       #   #           #       #       #       #   #               #                 
       #   #               #                       #       #       #   #       #       #           #           #       #       #   #       #       #                       #               #   #       
                         #   #                       #           #                   #   #         |         #   #                   #           #                       #   #                         
               #   #   #                               #       #           #   #   #           #   |   #           #   #   #           #       #                               #   #   #               
         #           #       #       #   #       #           #                   #       #       # | #       #       #                   #           #       #   #       #       #           #         
       #   #           #       #   #       #           #               #                   #   #   |   #   #                   #               #           #       #   #       #           #   #       
         #       #                               #           #       #       #   #               # | #               #   #       #       #           #                               #       #         
   #           #       #           #   #   #           #   #               #   #   #           #   |   #           #   #   #               #   #           #   #   #           #       #           #   
             #                                   #   #           #       #           #             |             #           #       #           #   #                                   #             
       #           #           #       #       #           #           #               #   #       #       #   #               #           #           #       #       #           #           #       
     #       #       #               #   #   #           #   #   #       #       #   #       #   # | #   #       #   #       #       #   #   #           #   #   #               #       #       #     
           #                   #               #                   #   #       #           #       |       #           #       #   #                   #               #                   #           
     #   #   #           #   #   #                   #           #       #           #   #   #     |     #   #   #           #       #           #                   #   #   #           #   #   #     
                       #                                   #   #           #   #   #           #   #   #           #   #   #           #   #                                   #                       
 #                                   #   #       #           #               #           #       # | #       #           #               #           #       #   #                                   # 
       #       #           #   #   #       #   #   #   #       #   #               #   #   #   #   |   #   #   #   #               #   #       #   #   #   #       #   #   #           #       #       
 #               #                   #   #       #       #           #       #   #       #       # | #       #       #   #       #           #       #       #   #                   #               # 
                   #   #           #                       #                   #   #           #   #   #           #   #                   #                       #           #   #                   
     #   #               #   #   #           #                   #   #   #           #   #   #   # | #   #   #   #           #   #   #                   #           #   #   #               #   #     
                   #       #                   #   #       #       #   #       #       #   #   # # | # #   #   #       #       #   #       #       #   #                   #       #                   

- - - # - - - # - - - - - - - - - - - # - - - - - - - # - - - # - - - - - - - # - - - # - - - # - - + - - # - - - # - - - # - - - - - - - # - - - # - - - - - - - # - - - - - - - - - - - # - - - # - -

                   #       #                   #   #       #       #   #       #       #   #   # # | # #   #   #       #       #   #       #       #   #                   #       #                   
     #   #               #   #   #           #                   #   #   #           #   #   #   # | #   #   #   #           #   #   #                   #           #   #   #               #   #     
                   #   #           #                       #                   #   #           #   #   #           #   #                   #                       #           #   #                   
 #               #                   #   #       #       #           #       #   #       #       # | #       #       #   #       #           #       #       #   #                   #               # 
       #       #           #   #   #       #   #   #   #       #   #               #   #   #   #   |   #   #   #   #               #   #       #   #   #   #       #   #   #           #       #       
 #                                   #   #       #           #               #           #       # | #       #           #               #           #       #   #                                   # 
                       #                                   #   #           #   #   #           #   #   #           #   #   #           #   #                                   #                       
     #   #   #           #   #   #                   #           #       #           #   #   #     |     #   #   #           #       #           #                   #   #   #           #   #   #     
           #                   #               #                   #   #       #           #       |       #           #       #   #                   #               #                   #           
     #       #       #               #   #   #           #   #   #       #       #   #       #   # | #   #       #   #       #       #   #   #           #   #   #               #       #       #     
       #           #           #       #       #           #           #               #   #       #       #   #               #           #           #       #       #           #           #       
             #                                   #   #           #       #           #             |             #           #       #           #   #                                   #             
   #           #       #           #   #   #           #   #               #   #   #           #   |   #           #   #   #               #   #           #   #   #           #       #           #   
         #       #                               #           #       #       #   #               # | #               #   #       #       #           #                               #       #         
       #   #           #       #   #       #           #               #                   #   #   |   #   #                   #               #           #       #   #       #           #   #       
         #           #       #       #   #       #           #                   #       #       # | #       #       #                   #           #       #   #       #       #           #         
               #   #   #                               #       #           #   #   #           #   |   #           #   #   #           #       #                               #   #   #               
                         #   #                       #           #                   #   #         |         #   #                   #           #                       #   #                         
       #   #               #                       #       #       #   #       #       #           #           #       #       #   #       #       #                       #               #   #       
                 #               #   #       #       #       #           #   #       #       #   # | #   #       #       #   #           #       #       #       #   #               #                 
           #                   #               #                               #           #       |       #           #                               #               #                   #           
             #               #               #   #   #           #   #   #               #         |         #               #   #   #           #   #   #               #               #             
               #   #   #           #   #               #   #   #           #       #               #               #       #           #   #   #               #   #           #   #   #               
                             #                   #           #                           #       # | #       #                           #           #                   #                             
               #       #                   #   #   #   #           #   #   #           #   #       |       #   #           #   #   #           #   #   #   #                   #       #               
                 #           #       #           #       #                   #   #       #       # | #       #       #   #                   #       #           #       #           #                 
                                   #                   #   #                   #               #   |   #               #                   #   #                   #                                   
                         #       #               #                   #   #               #         |         #               #   #                   #               #       #                         
                   #       #   #       #                           #           #       #   #       |       #   #       #           #                           #       #   #       #                   
                         #           #   #           #                   #   #                     |                     #   #                   #           #   #           #                         
                                       #       #           #       #           #       #   #       #       #   #       #           #       #           #       #                                       
                         #       #           #       #               #   #               #   #     |     #   #               #   #               #       #           #       #                         
                                   #       #               #                       #           #   |   #           #                       #               #       #                                   
                             #           #               #           #       #   #       #         |         #       #   #       #           #               #           #                             
                               #               #   #   #       #   #               #           #   |   #           #               #   #       #   #   #               #                               
                                         #                   #                           #       # | #       #                           #                   #                                         
                                   #   #   #                   #                   #           #   |   #           #                   #                   #   #   #                                   
                                                 #   #           #   #   #           #       #     |     #       #           #   #   #           #   #                                                 
                                                                   #           #                   |                   #           #                                                                   
                                         #           #           #           #               #   # | #   #               #           #           #           #                                         
                                               #           #           #                   #       |       #                   #           #           #                                               
                                                 #   #           #       #               #         |         #               #       #           #   #                                                 
                                                       #                   #   #   #               #               #   #   #                   #                                                       
                                                         #   #       #           #                 |                 #           #       #   #                                                         
                                                                   #   #           #           #   |   #           #           #   #                                                                   
                                                             #       #       #           #         |         #           #       #       #                                                             
                                                                               #   #           #   #   #           #   #                                                                               
                                                                         #                         |                         #                                                                         
                                                                                       #   #       |       #   #                                                                                       

</lang>

Gaussian primes less than radius 10 (sorted by radius):<lang J> 10 10$(/: |)(#~ isgpri * 10>|) ,j./~i:10 _1j_1 _1j1 1j_1 1j1 _2j_1 _2j1 _1j_2 _1j2 1j_2 1j2

2j_1  2j1    _3 0j_3   0j3    3 _3j_2 _3j2 _2j_3 _2j3
2j_3  2j3  3j_2  3j2 _4j_1 _4j1 _1j_4 _1j4  1j_4  1j4
4j_1  4j1 _5j_2 _5j2 _2j_5 _2j5  2j_5  2j5  5j_2  5j2

_6j_1 _6j1 _1j_6 _1j6 1j_6 1j6 6j_1 6j1 _5j_4 _5j4 _4j_5 _4j5 4j_5 4j5 5j_4 5j4 _7 0j_7 0j7 7 _7j_2 _7j2 _2j_7 _2j7 2j_7 2j7 7j_2 7j2 _6j_5 _6j5 _5j_6 _5j6 5j_6 5j6 6j_5 6j5 _8j_3 _8j3 _3j_8 _3j8

3j_8  3j8  8j_3  8j3 _8j_5 _8j5 _5j_8 _5j8  5j_8  5j8
8j_5  8j5 _9j_4 _9j4 _4j_9 _4j9  4j_9  4j9  9j_4  9j4</lang>

Phix

Library: Phix/pGUI

Library: Phix/online

You can run this online here. Oddly there's a much stronger suggestion of a '+' in the plot in a browser than on the desktop.

--
-- demo/rosetta/Gaussian_primes.exw
-- ================================
--
with javascript_semantics

function gaussian_primes(integer radius)
    integer sq_radius = radius*radius
    sequence res = {}
    for i=1 to radius do
        if remainder(i,4)=3 then
            res = append(res,{i*i,i,0})
        end if
        integer i2 = i*i
        for j=i to radius do
            integer r = i2+j*j
            if r>sq_radius then exit end if
            if is_prime(r) then
                res = append(res,{r,j,i})
            end if
        end for
    end for
    res = sort(res)
    return res
end function

include builtins\complex.e
function gpp(integer i, j)
    return pad_head(complex_sprint({i,j}),6)
end function

function g4(integer i,j)
    sequence res = {gpp(i,j)}
    if i!=0 then
        res = append(res,gpp(-i,j))
        if j!=0 then
            res = append(res,gpp(-i,-j))
        end if
    end if
    if j!=0 then
        res = append(res,gpp(i,-j))
    end if
    return res
end function

function reflect(sequence g)
    sequence res = {}
    for p in g do
        integer {n,i,j} = p
        res &= g4(i,j)
        if i!=j then res &= g4(j,i) end if
    end for
    return res
end function

sequence g = gaussian_primes(10)

printf(1,"Gaussian primes with a norm less than 100 sorted by norm:\n%s\n",
         {join_by(reflect(g),1,10," ")})

--g = gaussian_primes(50) -- (radius of 50)
g = gaussian_primes(150) -- (radius of 150)

constant title = "Gaussian primes"
include pGUI.e

Ihandle dlg, canvas
cdCanvas cddbuffer, cdcanvas
integer cx, cy

procedure plot4(integer i,j)
    for im=+1 to -1 by -2 do
        for jm=+1 to -1 by -2 do
            cdCanvasPixel(cddbuffer, cx+im*i, cy+jm*j, CD_YELLOW) 
        end for
    end for
end procedure

function redraw_cb(Ihandle /*ih*/)
    integer {width, height} = IupGetIntInt(canvas, "DRAWSIZE")
    cx = floor(width/2)
    cy = floor(height/2)
    cdCanvasActivate(cddbuffer)
    cdCanvasClear(cddbuffer)
    for p in g do
        integer {n,i,j} = p
        plot4(i,j)
        plot4(j,i)
    end for
    cdCanvasFlush(cddbuffer)
    return IUP_DEFAULT
end function

function map_cb(Ihandle ih)
    cdcanvas = cdCreateCanvas(CD_IUP, ih)
    cddbuffer = cdCreateCanvas(CD_DBUFFER, cdcanvas)
    cdCanvasSetBackground(cddbuffer, CD_BLACK)
    return IUP_DEFAULT
end function

IupOpen()
--canvas = IupCanvas("RASTERSIZE=320x320")
canvas = IupCanvas("RASTERSIZE=340x340")
IupSetCallbacks(canvas, {"MAP_CB", Icallback("map_cb"),
                         "ACTION", Icallback("redraw_cb")})
dlg = IupDialog(canvas, `TITLE="%s",RESIZE=NO`,{title})
IupShow(dlg)
if platform()!=JS then
    IupMainLoop()
    IupClose()
end if

Output same as Raku

Raku

Plotting the points up to a radius of 150. <lang perl6>use List::Divvy;

my @next = { :1x, :1y, :2n },;

sub next-interval (Int $int) {

    @next.append: (^$int).map: { %( :x($int), :y($_), :n($int² + .²) ) };
    @next = |@next.sort: *.<n>;

}

my @gaussian = lazy gather {

   my $interval = 1;
   loop {
       my @this = @next.shift;
       @this.push: @next.shift while @next and @next[0]<n> == @this[0]<n>;
       for @this {
           .take if .<n>.is-prime || (!.<y> && .<x>.is-prime && (.<x> - 3) %% 4);
           next-interval(++$interval) if $interval == .<x>
       }
   }

}

1. Primes within a radius of 10 from origin

say "Gaussian primes with a norm less than 100 sorted by norm:"; say @gaussian.&before(*.<n> > 10²).map( {

    my (\i, \j) = .<x y>;
   flat ((i,j),(-i,j),(-i,-j),(i,-j),(j,i),(-j,i),(-j,-i),(j,-i)).map: {
       .[0] ?? .[1] ?? (sprintf "%d%s%di", .[0], (.[1] ≥ 0 ?? '+' !! ), .[1]) !! .[0] !! "{.[1]}i"
   }} )».subst('1i', 'i', :g)».fmt("%6s")».unique.flat.batch(10).join: "\n" ;

1. Plot points within a 150 radius

use SVG;

my @points = unique flat @gaussian.&before(*.<n> > 150²).map: {

   my (\i, \j) = .<x y>;
   do for (i,j),(-i,j),(-i,-j),(i,-j),(j,i),(-j,i),(-j,-i),(j,-i) {
       :use['xlink:href'=>'#point', 'transform'=>"translate({500 + 3 × .[0]},{500 + 3 × .[1]})"]
   }

}

'gaussian-primes-raku.svg'.IO.spurt: SVG.serialize(

   svg => [
       :width<1000>, :height<1000>,
       :rect[:width<100%>, :height<100%>, :style<fill:black;>],
       :defs[:g[:id<point>, :circle[:0cx, :0cy, :2r, :fill('gold')]]],
       |@points
   ],

);</lang>

Output:

Gaussian primes with a norm less than 100 sorted by norm:
   1+i   -1+i   -1-i    1-i    2+i   -2+i   -2-i    2-i   1+2i  -1+2i
 -1-2i   1-2i      3     -3     3i    -3i   3+2i  -3+2i  -3-2i   3-2i
  2+3i  -2+3i  -2-3i   2-3i    4+i   -4+i   -4-i    4-i   1+4i  -1+4i
 -1-4i   1-4i   5+2i  -5+2i  -5-2i   5-2i   2+5i  -2+5i  -2-5i   2-5i
   6+i   -6+i   -6-i    6-i   1+6i  -1+6i  -1-6i   1-6i   5+4i  -5+4i
 -5-4i   5-4i   4+5i  -4+5i  -4-5i   4-5i      7     -7     7i    -7i
  7+2i  -7+2i  -7-2i   7-2i   2+7i  -2+7i  -2-7i   2-7i   6+5i  -6+5i
 -6-5i   6-5i   5+6i  -5+6i  -5-6i   5-6i   8+3i  -8+3i  -8-3i   8-3i
  3+8i  -3+8i  -3-8i   3-8i   8+5i  -8+5i  -8-5i   8-5i   5+8i  -5+8i
 -5-8i   5-8i   9+4i  -9+4i  -9-4i   9-4i   4+9i  -4+9i  -4-9i   4-9i

Off-site SVG image: gaussian-primes-raku.svg