iconEuler Home

The Prime Spiral

We want to make a spiraling pattern starting in the center of a matrix and going outward counter clockwise.

For this we define two functions which compute the row and the column index of the number n in the pattern. It takes a bit to find and debug these.

>function map col (n) ...
 if n==1 then return 0; endif;
 k=ceil(sqrt(n)); // on bounary of k*k square
 if mod(k,2)==0 then k=k+1; endif; // k must be odd
 d=n-(k-2)^2; // d-th element there
 u=(k^2-(k-2)^2)/4; // 4*u elements on this boundary
 k=(k-1)/2; // distance from center of the boundary
 if d<=u then return k;
 elseif d<=2*u then return k-(d-u);
 elseif d<=3*u then return -k;
 else return -k+(d-3*u)
 endif;
 endfunction
>function map row (n) ...
 if n==1 then return 0; endif;
 k=ceil(sqrt(n)); // on bounary of k*k square
 if mod(k,2)==0 then k=k+1; endif; // k must be odd
 d=n-(k-2)^2; // d-th element there
 u=(k^2-(k-2)^2)/4; // 4*u elements on this boundary
 k=(k-1)/2; // distance from center of the boundary
 if d<=u then return k-d;
 elseif d<=2*u then return -k;
 elseif d<=3*u then return -k+(d-2*u);
 else return k
 endif;
 endfunction

Tests.

>col(2:9)
[1,  1,  0,  -1,  -1,  -1,  0,  1]
>col(10:25)
[2,  2,  2,  2,  1,  0,  -1,  -2,  -2,  -2,  -2,  -2,  -1,  0,  1,  2]
>row(2:9)
[0,  -1,  -1,  -1,  0,  1,  1,  1]
>row(10:25)
[1,  0,  -1,  -2,  -2,  -2,  -2,  -2,  -1,  0,  1,  2,  2,  2,  2,  2]

Nowe a test, where the numbers are inserted into the matrix.

>function testspiral (n) ...
 k=2*n+1;
 A=zeros(k,k);
 c=col(1:k^2); r=row(1:k^2);
 for i=1 to k^2; 
    A[r[i]+n+1,c[i]+n+1]=i;
 end;
 return A
 endfunction

Seems to work as desired.

>shortest testspiral(3)
       37        36        35        34        33        32        31 
       38        17        16        15        14        13        30 
       39        18         5         4         3        12        29 
       40        19         6         1         2        11        28 
       41        20         7         8         9        10        27 
       42        21        22        23        24        25        26 
       43        44        45        46        47        48        49 

Now we define a function, which has 1 at each prime place.

>function makespiral (n) ...
 k=2*n+1;
 A=zeros(k,k);
 c=col(1:k^2); r=row(1:k^2);
 p=primes(k^2);
 for i=p;
    A[r[i]+n+1,c[i]+n+1]=1;
 end;
 return A
 endfunction
>shortest makespiral(3)
        1         0         0         0         0         0         1 
        0         1         0         0         0         1         0 
        0         0         1         0         1         0         1 
        0         1         0         0         1         1         0 
        1         0         1         0         0         0         0 
        0         0         0         1         0         0         0 
        1         0         0         0         1         0         0 

Here is the result.

>A=makespiral(250);
>insrgb(rgb(!A,!A,!A));

Prime Spiral

Euler Home