Ulam spiral (for primes)
You are encouraged to solve this task according to the task description, using any language you may know.
An Ulam spiral (of primes numbers) is a method of visualizing prime numbers when expressed in a (normally counter-clockwise) outward spiral (usually starting at 1), constructed on a square grid, starting at the "center".
An Ulam spiral is also known as a prime spiral.
The first grid (green) is shown with all numbers (primes and non-primes) shown, starting at 1.
In an Ulam spiral of primes, only the primes are shown (usually indicated by some glyph such as a dot), and all non-primes as shown as a blank (or some other whitespace). Of course, the grid and border are not to be displayed (but they are displayed here when using these Wiki HTML tables).
Normally, the spiral starts in the "center", and the 2nd number is to the viewer's right and the number spiral starts from there in a counter-clockwise direction. There are other geometric shapes that are used as well, including clock-wise spirals. Also, some spirals (for the 2nd number) is viewed upwards from the 1st number instead of to the right, but that is just a matter of orientation.
Sometimes, the starting number can be specified to show more visual striking patterns (of prime densities).
| 65 | 64 | 63 | 62 | 61 | 60 | 59 | 58 | 57 |
| 66 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 56 |
| 67 | 38 | 17 | 16 | 15 | 14 | 13 | 30 | 55 |
| 68 | 39 | 18 | 5 | 4 | 3 | 12 | 29 | 54 |
| 69 | 40 | 19 | 6 | 1 | 2 | 11 | 28 | 53 |
| 70 | 41 | 20 | 7 | 8 | 9 | 10 | 27 | 52 |
| 71 | 42 | 21 | 22 | 23 | 24 | 25 | 26 | 51 |
| 72 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 |
[A larger than necessary grid (numbers wise) is shown here to illustrate the pattern of numbers on the diagonals (which may be used by the method to orientate the direction of spiral-construction algorithm within the example computer programs)].
Then, to show the Ulam prime spiral, a character (or glyph) is shown instead of each prime number, and a blank for all non-prime numbers. In the orange grid below, the prime numbers are left intact to see what numbers are to be changed to the character for viewing.
| 61 | 59 | |||||||
| 37 | 31 | |||||||
| 67 | 17 | 13 | ||||||
| 5 | 3 | 29 | ||||||
| 19 | 2 | 11 | 53 | |||||
| 41 | 7 | |||||||
| 71 | 23 | |||||||
| 43 | 47 | |||||||
| 73 | 79 |
Then, in the final transformation of the Ulam spiral (the yellow grid), translate the primes to a glyph such as a ∙ or some other suitable glyph.
| ∙ | ∙ | |||||||
| ∙ | ∙ | |||||||
| ∙ | ∙ | ∙ | ||||||
| ∙ | ∙ | ∙ | ||||||
| ∙ | ∙ | ∙ | ∙ | |||||
| ∙ | ∙ | |||||||
| ∙ | ∙ | |||||||
| ∙ | ∙ | |||||||
| ∙ | ∙ |
- Task
For any sized N x N grid, construct and show an Ulam spiral (counter-clockwise) of primes starting at some specified initial number (the default would be 1), with some suitably dotty representation to indicate primes, and the absence of dots to indicate non-primes.
You should demonstrate the generator by showing at Ulam prime spiral large enough to (almost) fill your terminal screen.
- Also see
-
- Wikipedia entry: Ulam spiral.
- MathWorld™ entry: Prime Spiral.
Ada
This is a generic solution. It is straightforward to use it to print spirals for any kind of numbers, rather than spirals of primes, only.
The specification of package generic_ulam is as follows:
<lang Ada>generic
Size: Positive;
-- determines the size of the square
with function Represent(N: Natural) return String;
-- this turns a number into a string to be printed
-- the length of the output should not change
-- e.g., Represent(N) may return " #" if N is a prime
-- and " " else
with procedure Put_String(S: String);
-- outputs a string, no new line
with procedure New_Line;
-- the name says all
package Generic_Ulam is
procedure Print_Spiral; -- calls Put_String(Represent(I)) N^2 times -- and New_Line N times
end Generic_Ulam;</lang>
Here is the implementation: <lang Ada>package body Generic_Ulam is
subtype Index is Natural range 0 .. Size-1; subtype Number is Positive range 1 .. Size**2;
function Cell(Row, Column: Index) return Number is
-- outputs the number at the given position in the square
-- taken from the Python solution
X: Integer := Column - (Size-1)/2;
Y: Integer := Row - Size/2;
MX: Natural := abs(X);
MY: Natural := abs(Y);
L: Natural := 2 * Natural'Max(MX, MY);
D: Integer;
begin
if Y >= X then
D := 3 * L + X + Y;
else
D := L - X - Y;
end if;
return (L-1) ** 2 + D;
end Cell;
procedure Print_Spiral is
N: Number;
begin
for R in Index'Range loop
for C in Index'Range loop
N := Cell(R, C);
Put_String(Represent(N));
end loop;
New_Line;
end loop;
end Print_Spiral;
end Generic_Ulam;</lang>
The folowing implementation prints a 29*29 spiral with the primes represented as numbers, and a 10*10 spiral with the primes as boxes. It uses the generic function Prime_Numbers.Is_Prime, as specified in Prime decomposition#Ada.
<lang Ada>with Generic_Ulam, Ada.Text_IO, Prime_Numbers;
procedure Ulam is
package P is new Prime_Numbers(Natural, 0, 1, 2);
function Vis(N: Natural) return String is
(if P.Is_Prime(N) then " <>" else " ");
function Num(N: Natural) return String is
(if P.Is_Prime(N) then
(if N < 10 then " " elsif N < 100 then " " else "") & Natural'Image(N)
else " ---");
procedure NL is
begin
Ada.Text_IO.New_Line;
end NL;
package Numeric is new Generic_Ulam(29, Num, Ada.Text_IO.Put, NL);
package Visual is new Generic_Ulam(10, Vis, Ada.Text_IO.Put, NL);
begin
Numeric.Print_Spiral; NL; Visual.Print_Spiral;
end Ulam;</lang>
- Output:
--- --- --- --- --- --- --- --- --- --- --- --- 773 --- --- --- 769 --- --- --- --- --- --- --- 761 --- --- --- 757
--- 677 --- --- --- 673 --- --- --- --- --- --- --- --- --- --- --- 661 --- 659 --- --- --- --- --- 653 --- --- ---
787 --- 577 --- --- --- --- --- 571 --- 569 --- --- --- --- --- 563 --- --- --- --- --- 557 --- --- --- --- --- ---
--- --- --- --- --- --- --- --- --- 479 --- --- --- --- --- --- --- --- --- --- --- 467 --- --- --- 463 --- --- ---
--- --- --- --- 401 --- --- --- 397 --- --- --- --- --- --- --- 389 --- --- --- --- --- 383 --- --- --- --- --- ---
--- --- --- 487 --- --- --- --- --- --- --- --- --- 317 --- --- --- 313 --- 311 --- --- --- 307 --- 461 --- 647 ---
--- --- --- --- --- --- 257 --- --- --- --- --- 251 --- --- --- --- --- --- --- --- --- 241 --- 379 --- --- --- 751
--- 683 --- --- --- --- --- 197 --- --- --- 193 --- 191 --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- --- --- --- --- --- --- --- 139 --- 137 --- --- --- --- --- 239 --- --- --- 547 --- ---
--- --- --- 491 --- --- --- 199 --- 101 --- --- --- 97 --- --- --- --- --- --- --- 181 --- --- --- 457 --- 643 ---
--- --- --- --- --- --- --- --- --- --- --- --- --- --- 61 --- 59 --- --- --- 131 --- --- --- --- --- --- --- ---
--- --- --- --- --- 331 --- --- --- 103 --- 37 --- --- --- --- --- 31 --- 89 --- 179 --- --- --- --- --- 641 ---
797 --- 587 --- 409 --- 263 --- 149 --- 67 --- 17 --- --- --- 13 --- --- --- --- --- --- --- 373 --- --- --- ---
--- --- --- --- --- --- --- --- --- --- --- --- --- 5 --- 3 --- 29 --- --- --- --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- --- 151 --- --- --- 19 --- --- 2 11 --- 53 --- 127 --- 233 --- --- --- 541 --- 743
--- 691 --- --- --- --- --- --- --- 107 --- 41 --- 7 --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- --- --- --- 71 --- --- --- 23 --- --- --- --- --- --- --- --- --- --- --- --- --- ---
--- --- --- 499 --- 337 --- --- --- 109 --- 43 --- --- --- 47 --- --- --- 83 --- 173 --- --- --- 449 --- --- ---
--- --- 593 --- --- --- 269 --- --- --- 73 --- --- --- --- --- 79 --- --- --- --- --- 229 --- 367 --- --- --- 739
--- --- --- --- --- --- --- --- --- --- --- 113 --- --- --- --- --- --- --- --- --- --- --- 293 --- --- --- --- ---
--- --- --- --- --- --- 271 --- 157 --- --- --- --- --- 163 --- --- --- 167 --- --- --- 227 --- --- --- --- --- ---
--- --- --- 503 --- --- --- 211 --- --- --- --- --- --- --- --- --- --- --- 223 --- --- --- --- --- --- --- 631 ---
--- --- --- --- 419 --- --- --- --- --- 277 --- --- --- 281 --- 283 --- --- --- --- --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- --- --- 347 --- 349 --- --- --- 353 --- --- --- --- --- 359 --- --- --- 443 --- --- ---
809 --- 599 --- 421 --- --- --- --- --- --- --- --- --- 431 --- 433 --- --- --- --- --- 439 --- --- --- --- --- 733
--- 701 --- --- --- 509 --- --- --- --- --- --- --- --- --- --- --- 521 --- 523 --- --- --- --- --- --- --- --- ---
811 --- 601 --- --- --- --- --- 607 --- --- --- --- --- 613 --- --- --- 617 --- 619 --- --- --- --- --- --- --- ---
--- --- --- --- --- --- --- 709 --- --- --- --- --- --- --- --- --- 719 --- --- --- --- --- --- --- 727 --- --- ---
--- --- --- --- --- --- --- --- 821 --- 823 --- --- --- 827 --- 829 --- --- --- --- --- --- --- --- --- 839 --- ---
<>
<> <>
<> <> <>
<> <> <>
<> <> <>
<> <> <> <>
<> <>
<> <>
<> <> <>
<> <>
C
<lang c>
- include <stdio.h>
- include <stdint.h>
- include <stdlib.h>
- include <math.h>
typedef uint32_t bitsieve;
unsigned sieve_check(bitsieve *b, const unsigned v) {
if ((v != 2 && !(v & 1)) || (v < 2))
return 0;
else
return !(b[v >> 6] & (1 << (v >> 1 & 31)));
}
bitsieve* sieve(const unsigned v) {
unsigned i, j; bitsieve *b = calloc((v >> 6) + 1, sizeof(uint32_t));
for (i = 3; i <= sqrt(v); i += 2)
if (!(b[i >> 6] & (1 << (i >> 1 & 31))))
for (j = i*i; j < v; j += (i << 1))
b[j >> 6] |= (1 << (j >> 1 & 31));
return b;
}
- define max(x,y) ((x) > (y) ? (x) : (y))
/* This mapping taken from python solution */ int ulam_get_map(int x, int y, int n) {
x -= (n - 1) / 2; y -= n / 2;
int mx = abs(x), my = abs(y); int l = 2 * max(mx, my); int d = y > x ? l * 3 + x + y : l - x - y;
return pow(l - 1, 2) + d;
}
/* Passing a value of 0 as glyph will print numbers */ void output_ulam_spiral(int n, const char glyph) {
/* An even side length does not make sense, use greatest odd value < n */ n -= n % 2 == 0 ? 1 : 0;
const char *spaces = "................."; int mwidth = log10(n * n) + 1;
bitsieve *b = sieve(n * n + 1); int x, y;
for (x = 0; x < n; ++x) {
for (y = 0; y < n; ++y) {
int z = ulam_get_map(y, x, n);
if (glyph == 0) {
if (sieve_check(b, z))
printf("%*d ", mwidth, z);
else
printf("%.*s ", mwidth, spaces);
}
else {
printf("%c", sieve_check(b, z) ? glyph : spaces[0]);
}
}
printf("\n");
}
free(b);
}
int main(int argc, char *argv[]) {
const int n = argc < 2 ? 9 : atoi(argv[1]);
output_ulam_spiral(n, 0);
printf("\n");
output_ulam_spiral(n, '#');
printf("\n");
return 0;
} </lang>
- Output:
Run with a side-length of 29
... ... ... ... ... ... ... ... ... ... ... ... 773 ... ... ... 769 ... ... ... ... ... ... ... 761 ... ... ... 757 ... 677 ... ... ... 673 ... ... ... ... ... ... ... ... ... ... ... 661 ... 659 ... ... ... ... ... 653 ... ... ... 787 ... 577 ... ... ... ... ... 571 ... 569 ... ... ... ... ... 563 ... ... ... ... ... 557 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 479 ... ... ... ... ... ... ... ... ... ... ... 467 ... ... ... 463 ... ... ... ... ... ... ... 401 ... ... ... 397 ... ... ... ... ... ... ... 389 ... ... ... ... ... 383 ... ... ... ... ... ... ... ... ... 487 ... ... ... ... ... ... ... ... ... 317 ... ... ... 313 ... 311 ... ... ... 307 ... 461 ... 647 ... ... ... ... ... ... ... 257 ... ... ... ... ... 251 ... ... ... ... ... ... ... ... ... 241 ... 379 ... ... ... 751 ... 683 ... ... ... ... ... 197 ... ... ... 193 ... 191 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 139 ... 137 ... ... ... ... ... 239 ... ... ... 547 ... ... ... ... ... 491 ... ... ... 199 ... 101 ... ... ... 97 ... ... ... ... ... ... ... 181 ... ... ... 457 ... 643 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 61 ... 59 ... ... ... 131 ... ... ... ... ... ... ... ... ... ... ... ... ... 331 ... ... ... 103 ... 37 ... ... ... ... ... 31 ... 89 ... 179 ... ... ... ... ... 641 ... 797 ... 587 ... 409 ... 263 ... 149 ... 67 ... 17 ... ... ... 13 ... ... ... ... ... ... ... 373 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5 ... 3 ... 29 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 151 ... ... ... 19 ... ... 2 11 ... 53 ... 127 ... 233 ... ... ... 541 ... 743 ... 691 ... ... ... ... ... ... ... 107 ... 41 ... 7 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 71 ... ... ... 23 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 499 ... 337 ... ... ... 109 ... 43 ... ... ... 47 ... ... ... 83 ... 173 ... ... ... 449 ... ... ... ... ... 593 ... ... ... 269 ... ... ... 73 ... ... ... ... ... 79 ... ... ... ... ... 229 ... 367 ... ... ... 739 ... ... ... ... ... ... ... ... ... ... ... 113 ... ... ... ... ... ... ... ... ... ... ... 293 ... ... ... ... ... ... ... ... ... ... ... 271 ... 157 ... ... ... ... ... 163 ... ... ... 167 ... ... ... 227 ... ... ... ... ... ... ... ... ... 503 ... ... ... 211 ... ... ... ... ... ... ... ... ... ... ... 223 ... ... ... ... ... ... ... 631 ... ... ... ... ... 419 ... ... ... ... ... 277 ... ... ... 281 ... 283 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 347 ... 349 ... ... ... 353 ... ... ... ... ... 359 ... ... ... 443 ... ... ... 809 ... 599 ... 421 ... ... ... ... ... ... ... ... ... 431 ... 433 ... ... ... ... ... 439 ... ... ... ... ... 733 ... 701 ... ... ... 509 ... ... ... ... ... ... ... ... ... ... ... 521 ... 523 ... ... ... ... ... ... ... ... ... 811 ... 601 ... ... ... ... ... 607 ... ... ... ... ... 613 ... ... ... 617 ... 619 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 709 ... ... ... ... ... ... ... ... ... 719 ... ... ... ... ... ... ... 727 ... ... ... ... ... ... ... ... ... ... ... 821 ... 823 ... ... ... 827 ... 829 ... ... ... ... ... ... ... ... ... 839 ... ... ............#...#.......#...# .#...#...........#.#.....#... #.#.....#.#.....#.....#...... .........#...........#...#... ....#...#.......#.....#...... ...#.........#...#.#...#.#.#. ......#.....#.........#.#...# .#.....#...#.#............... ..............#.#.....#...#.. ...#...#.#...#.......#...#.#. ..............#.#...#........ .....#...#.#.....#.#.#.....#. #.#.#.#.#.#.#...#.......#.... .............#.#.#........... ........#...#..##.#.#.#...#.# .#.......#.#.#............... ..........#...#.............. ...#.#...#.#...#...#.#...#... ..#...#...#.....#.....#.#...# ...........#...........#..... ......#.#.....#...#...#...... ...#...#...........#.......#. ....#.....#...#.#............ .........#.#...#.....#...#... #.#.#.........#.#.....#.....# .#...#...........#.#......... #.#.....#.....#...#.#........ .......#.........#.......#... ........#.#...#.#.........#..
The following shows a spiral that's not necessarily square, which has questionable merit: <lang c>#include <stdio.h>
- include <stdlib.h>
int isprime(int n) { int p; for (p = 2; p*p <= n; p++) if (n%p == 0) return 0; return n > 2; }
int spiral(int w, int h, int x, int y) { return y ? w + spiral(h - 1, w, y - 1, w - x - 1) : x; }
int main(int c, char **v) { int i, j, w = 50, h = 50, s = 1; if (c > 1 && (w = atoi(v[1])) <= 0) w = 50; if (c > 2 && (h = atoi(v[2])) <= 0) h = w; if (c > 3 && (s = atoi(v[3])) <= 0) s = 1;
for (i = 0; i < h; i++) { for (j = 0; j < w; j++) putchar(isprime(w*h + s - 1 - spiral(w, h, j, i))[" #"]); putchar('\n'); } return 0; }</lang>
D
<lang d>import std.stdio, std.math, std.algorithm, std.array, std.range;
int cell(in int n, int x, int y, in int start=1) pure nothrow @safe @nogc {
x = x - (n - 1) / 2; y = y - n / 2; immutable l = 2 * max(x.abs, y.abs); immutable d = (y > x) ? (l * 3 + x + y) : (l - x - y); return (l - 1) ^^ 2 + d + start - 1;
}
void showSpiral(in int n, in string symbol="# ", in int start=1, string space=null) /*@safe*/ {
if (space is null)
space = " ".replicate(symbol.length);
immutable top = start + n ^^ 2 + 1;
auto isPrime = [false, false, true] ~ [true, false].replicate(top / 2);
foreach (immutable x; 3 .. 1 + cast(int)real(top).sqrt) {
if (!isPrime[x])
continue;
foreach (immutable i; iota(x ^^ 2, top, x * 2))
isPrime[i] = false;
}
string cellStr(in int x) pure nothrow @safe @nogc {
return isPrime[x] ? symbol : space;
}
foreach (immutable y; 0 .. n)
n.iota.map!(x => cell(n, x, y, start)).map!cellStr.joiner.writeln;
}
void main() {
35.showSpiral;
}</lang>
- Output:
# # # #
# # # # #
# # # #
# # # # #
# # # # #
# # # # # #
# # # # #
# # # # #
# # # # # # # #
# # # # # #
# # # # #
# # # # #
# # # # # # # #
# # #
# # # # # # # # # #
# # # # # # # # # #
# # # #
# # # # # # # # # #
# # # #
# #
# # # # # # # # # # #
# # # # # # #
# #
# # # # # #
# # # # #
# # # # #
# # # # # #
# # # # # # # # #
# # # #
# # # # # #
# # # # # #
# # # # #
# # # # #
# # # #
# # # # #
Alternative Version
This generates a PGM image, using the module from the Grayscale Image Task; <lang d>import std.stdio, std.math, std.algorithm, std.array, grayscale_image;
uint cell(in uint n, int x, int y, in uint start=1) pure nothrow @safe @nogc {
x = x - (n - 1) / 2; y = y - n / 2; immutable l = 2 * max(x.abs, y.abs); immutable d = (y > x) ? (l * 3 + x + y) : (l - x - y); return (l - 1) ^^ 2 + d + start - 1;
}
bool[] primes(in uint n, in uint top, in uint start=1) pure nothrow @safe {
auto isPrime = [false, false, true] ~ [true, false].replicate(top / 2);
foreach (immutable x; 3 .. 1 + cast(uint)real(top).sqrt)
if (isPrime[x])
for (uint i = x ^^ 2; i < top; i += x * 2)
isPrime[i] = false;
return isPrime;
}
void main() {
enum n = 512; enum start = 1; immutable top = start + n ^^ 2 + 1; immutable isPrime = primes(n, top, start); auto img = new Image!Gray(n, n);
foreach (immutable y; 0 .. n)
foreach (immutable x; 0 .. n)
img[x, y] = isPrime[cell(n, x, y, start)] ? Gray.black : Gray.white;
img.savePGM("ulam_spiral.pgm");
}</lang>
ERRE
<lang ERRE>PROGRAM SPIRAL
!$INTEGER
CONST RIGHT=1,UP=2,LEFT=3,DOWN=4
!$DYNAMIC DIM SPIRAL$[0,0]
PROCEDURE PRT_ULAM(N)
FOR ROW=0 TO N DO
FOR COL=0 TO N DO
PRINT(SPIRAL$[ROW,COL];)
END FOR
PRINT
END FOR
PRINT
GET(K$)
FOR ROW=0 TO N DO
FOR COL=0 TO N DO
IF VAL(SPIRAL$[ROW,COL])<>0 THEN PRINT(" * ";) ELSE PRINT(SPIRAL$[ROW,COL];) END IF
END FOR
PRINT
END FOR
END PROCEDURE
PROCEDURE IS_PRIME(A->RES%)
LOCAL N
IF A=2 THEN RES%=TRUE EXIT PROCEDURE END IF
IF A<=1 OR (A MOD 2=0) THEN RES%=FALSE EXIT PROCEDURE END IF
MAX=SQR(A)
FOR N=3 TO MAX STEP 2 DO
IF (A MOD N=0) THEN RES%=FALSE EXIT PROCEDURE END IF
END FOR
RES%=TRUE
END PROCEDURE
PROCEDURE GEN_ULAM(N,I)
DIR=RIGHT
J=I
Y=INT(N/2)
IF (N MOD 2=0) THEN X=Y-1 ELSE X=Y END IF ! shift left for even n's
WHILE J<=(N*N)-1+I DO
IS_PRIME(J->RES%)
IF RES% THEN SPIRAL$[Y,X]=RIGHT$(" "+STR$(J),4) ELSE SPIRAL$[Y,X]=" ---" END IF
CASE DIR OF
RIGHT->
IF (X<=(N-1) AND SPIRAL$[Y-1,X]="" AND J>I) THEN DIR=UP END IF
END ->
UP->
IF SPIRAL$[Y,X-1]="" THEN DIR=LEFT END IF
END ->
LEFT->
IF (X=0) OR SPIRAL$[Y+1,X]="" THEN DIR=DOWN END IF
END ->
DOWN->
IF SPIRAL$[Y,X+1]="" THEN DIR=RIGHT END IF
END ->
END CASE
CASE DIR OF
RIGHT-> X=X+1 END ->
UP-> Y=Y-1 END ->
LEFT-> X=X-1 END ->
DOWN-> Y=Y+1 END ->
END CASE
J=J+1
END WHILE
PRT_ULAM(N)
END PROCEDURE
BEGIN
N=9
!$DIM SPIRAL$[N,N]
GEN_ULAM(N,1)
END PROGRAM</lang>
- Output:
--- --- --- --- 61 --- 59 --- --- --- 37 --- --- --- --- --- 31 --- 67 --- 17 --- --- --- 13 --- --- --- --- --- 5 --- 3 --- 29 --- --- --- 19 --- --- 2 11 --- 53 --- 41 --- 7 --- --- --- --- --- 71 --- --- --- 23 --- --- --- --- --- 43 --- --- --- 47 --- --- --- 73 --- --- --- --- --- 79 --- --- --- --- --- --- * --- * --- --- --- * --- --- --- --- --- * --- * --- * --- --- --- * --- --- --- --- --- * --- * --- * --- --- --- * --- --- * * --- * --- * --- * --- --- --- --- --- * --- --- --- * --- --- --- --- --- * --- --- --- * --- --- --- * --- --- --- --- --- * --- ---
Fortran
Only works with odd sized squares <lang fortran>program ulam
implicit none
integer, parameter :: nsize = 49 integer :: i, j, n, x, y integer :: a(nsize*nsize) = (/ (i, i = 1, nsize*nsize) /) character(1) :: spiral(nsize, nsize) = " " character(2) :: sstr character(10) :: fmt n = 1 x = nsize / 2 + 1 y = x if(isprime(a(n))) spiral(x, y) = "O" n = n + 1
do i = 1, nsize-1, 2
do j = 1, i
x = x + 1
if(isprime(a(n))) spiral(x, y) = "O"
n = n + 1
end do
do j = 1, i
y = y - 1
if(isprime(a(n))) spiral(x, y) = "O"
n = n + 1
end do
do j = 1, i+1
x = x - 1
if(isprime(a(n))) spiral(x, y) = "O"
n = n + 1
end do
do j = 1, i+1
y = y + 1
if(isprime(a(n))) spiral(x, y) = "O"
n = n + 1
end do
end do
do j = 1, nsize-1 x = x + 1 if(isprime(a(n))) spiral(x, y) = "O" n = n + 1 end do
write(sstr, "(i0)") nsize
fmt = "(" // sstr // "(a,1x))"
do i = 1, nsize
write(*, fmt) spiral(:, i)
end do
contains
function isprime(number)
logical :: isprime
integer, intent(in) :: number
integer :: i
if(number == 2) then
isprime = .true.
else if(number < 2 .or. mod(number,2) == 0) then
isprime = .false.
else
isprime = .true.
do i = 3, int(sqrt(real(number))), 2
if(mod(number,i) == 0) then
isprime = .false.
exit
end if
end do
end if
end function end program</lang> Output:
O O O O O O O
O O O O O O O
O O O O O
O O O O O O O
O O O O O O O
O O O O O O O
O O O O O O O O O O
O O O O O
O O O O O O
O O O O O
O O O O O O O
O O O O O O
O O O O O O O O O
O O O O O O O O
O O O O O O O
O O O O O O O O O O
O O O O O O O O O O O
O O O O O O
O O O O O O O O
O O O O O O O O O O
O O O O
O O O O O O O O O O O O
O O O O O O O O O O O O O
O O O O
O O O O O O O O O O O O
O O O O O O
O O
O O O O O O O O O O O O O O
O O O O O O O O O O
O O O
O O O O O O O O O
O O O O O O O
O O O O O
O O O O O O O O
O O O O O O O O O O O O
O O O O
O O O O O O O O O O
O O O O O O O
O O O O O O O
O O O O O O O
O O O O O
O O O O O O
O O O O
O O O O O O O
O O O O O O
O O O O O O
O O O O O O O O
O O O
O O O O O O O O
J
Let's start with our implementation of spiral:
<lang J>spiral =: ,~ $ [: /: }.@(2 # >:@i.@-) +/\@# <:@+: $ (, -)@(1&,)</lang>
We can get a spiral starting with 1 in the center of the square by subtracting these values from the square of our size argument:
<lang J> spiral 5
0 1 2 3 4
15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
(*: - spiral) 5
25 24 23 22 21 10 9 8 7 20 11 2 1 6 19 12 3 4 5 18 13 14 15 16 17</lang>
Next, we want to determine which of these numbers are prime:
<lang J> (1 p: *: - spiral) 5 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1</lang>
And, finally, we want to use these values to select from a pair of characters:
<lang J> (' o' {~ 1 p: *: - spiral) 5
o o
oo o
o o
o o</lang>
If we want our spiral to start with some value other than 1, we'd add that value - 1 to our numbers right before the prime check. For this, we want a function which returns 0 when there's no left argument and one less than the left argument when it that value present. We can use : for this -- it takes two verbs, the left of which is used when no left argument is present and the right one is used when a left argument is present. (And note that in J, : is a token forming character, so we will need to leave a space to the left of : so that it does not form a different token):
<lang J> (0: :(<:@[)) 0
3 (0: :(<:@[))
2</lang>
We also want to specify that our initial computations only respect the right argument, and we should maybe add a space after every character to get more of a square aspect ratio in typical text displays:
<lang J>ulam=: 1j1 #"1 ' o' {~ 1 p: 0: :(<:@[) + *:@] - spiral@]</lang>
And here it is in action:
<lang J> ulam 16
o o
o o o
o o o
o o o o
o o o
o o o o o
o o o o
o o o
o o o o o o o
o o o
o o
o o o o o
o o o
o
o o o o
o o
9 ulam 12 o o
o o o o
o o o o
o o o
o o
o o o o o
o o
o
o o o o
o
o o o </lang>
To transform these spirals to the orientation which has recently been added as a part of the task, you could flip them horizontally (|."1) and vertically (|.)
It should also be possible to redefine the original spiral treatment in some other ways.
Java
<lang java5>import java.util.Arrays;
public class Ulam{ enum Direction{ RIGHT, UP, LEFT, DOWN; }
private static String[][] genUlam(int n){ return genUlam(n, 1); }
private static String[][] genUlam(int n, int i){ String[][] spiral = new String[n][n]; Direction dir = Direction.RIGHT; int j = i; int y = n / 2; int x = (n % 2 == 0) ? y - 1 : y; //shift left for even n's while(j <= ((n * n) - 1 + i)){ spiral[y][x] = isPrime(j) ? String.format("%4d", j) : " ---";
switch(dir){ case RIGHT: if(x <= (n - 1) && spiral[y - 1][x] == null && j > i) dir = Direction.UP; break; case UP: if(spiral[y][x - 1] == null) dir = Direction.LEFT; break; case LEFT: if(x == 0 || spiral[y + 1][x] == null) dir = Direction.DOWN; break; case DOWN: if(spiral[y][x + 1] == null) dir = Direction.RIGHT; break; }
switch(dir){ case RIGHT: x++; break; case UP: y--; break; case LEFT: x--; break; case DOWN: y++; break; } j++; } return spiral; }
public static boolean isPrime(int a){ if(a == 2) return true; if(a <= 1 || a % 2 == 0) return false; long max = (long)Math.sqrt(a); for(long n = 3; n <= max; n += 2){ if(a % n == 0) return false; } return true; }
public static void main(String[] args){ String[][] ulam = genUlam(9); for(String[] row : ulam){ System.out.println(Arrays.toString(row).replaceAll(",", "")); } System.out.println();
for(String[] row : ulam){ System.out.println(Arrays.toString(row).replaceAll("\\[\\s+\\d+", "[ * ").replaceAll("\\s+\\d+", " * ").replaceAll(",", "")); } } }</lang>
- Output:
[ --- --- --- --- 61 --- 59 --- ---] [ --- 37 --- --- --- --- --- 31 ---] [ 67 --- 17 --- --- --- 13 --- ---] [ --- --- --- 5 --- 3 --- 29 ---] [ --- --- 19 --- --- 2 11 --- 53] [ --- 41 --- 7 --- --- --- --- ---] [ 71 --- --- --- 23 --- --- --- ---] [ --- 43 --- --- --- 47 --- --- ---] [ 73 --- --- --- --- --- 79 --- ---] [ --- --- --- --- * --- * --- ---] [ --- * --- --- --- --- --- * ---] [ * --- * --- --- --- * --- ---] [ --- --- --- * --- * --- * ---] [ --- --- * --- --- * * --- * ] [ --- * --- * --- --- --- --- ---] [ * --- --- --- * --- --- --- ---] [ --- * --- --- --- * --- --- ---] [ * --- --- --- --- --- * --- ---]
Perl
<lang perl>use ntheory qw/is_prime/; use Imager;
my $n = shift || 512; my $start = shift || 1; my $file = "ulam.png";
sub cell {
my($n, $x, $y, $start) = @_; $y -= $n>>1; $x -= ($n-1)>>1; my $l = 2*(abs($x) > abs($y) ? abs($x) : abs($y)); my $d = ($y > $x) ? $l*3 + $x + $y : $l-$x-$y; ($l-1)**2 + $d + $start - 1;
}
my $black = Imager::Color->new('#000000'); my $white = Imager::Color->new('#FFFFFF'); my $img = Imager->new(xsize => $n, ysize => $n, channels => 1); $img->box(filled=>1, color=>$white);
for my $y (0 .. $n-1) {
for my $x (0 .. $n-1) {
my $v = cell($n, $x, $y, $start);
$img->setpixel(x => $x, y => $y, color => $black) if is_prime($v);
}
}
$img->write(file => $file) or die "Cannot write $file: ", $img->errstr, "\n";</lang>
- Output:
Creates an image file ulam.png in current directory similar to the one on MathWorld. The square dimension can be optionally specified.
Perl 6
<lang perl6>sub MAIN($max = 160, $start = 1) {
(my %world){0}{0} = 0;
my $loc = 0+0i;
my $dir = 1;
my $n = $start;
my $side = 0;
while ++$side < $max {
step for ^$side; turn-left; step for ^$side; turn-left;
}
braille-graphics %world;
sub step {
$loc += $dir; %world{$loc.im}{$loc.re} = $n if (++$n).is-prime;
}
sub turn-left { $dir *= -i; }
sub turn-right { $dir *= i; }
}
sub braille-graphics (%a) {
my ($ylo, $yhi, $xlo, $xhi);
for %a.keys -> $y {
$ylo min= +$y; $yhi max= +$y; for %a{$y}.keys -> $x { $xlo min= +$x; $xhi max= +$x; }
}
for $ylo, $ylo + 4 ...^ * > $yhi -> \y {
for $xlo, $xlo + 2 ...^ * > $xhi -> \x { my $cell = 0x2800; $cell += 1 if %a{y + 0}{x + 0}; $cell += 2 if %a{y + 1}{x + 0}; $cell += 4 if %a{y + 2}{x + 0}; $cell += 8 if %a{y + 0}{x + 1}; $cell += 16 if %a{y + 1}{x + 1}; $cell += 32 if %a{y + 2}{x + 1}; $cell += 64 if %a{y + 3}{x + 0}; $cell += 128 if %a{y + 3}{x + 1}; print chr($cell); } print "\n";
}
}</lang>
- Output:
⠔⠀⠀⠀⢐⠀⠁⠀⠀⠀⢐⠁⠀⢀⠀⠄⠄⠀⢀⠀⠀⠅⢀⠁⢅⢄⠀⢀⠔⠁⠀⠀⠀⢀⢀⠀⠀⠀⠁⢀⢀⠀⠀⢔⠁⢔⠄⠀⢄⠐⠀⠀⢀⠁⠐⠄⠀⢑⠄⠁⠄⠀⠁⠄⠀⠀⠀⢐⠀⠄⠐⠀⢁⢀⠀⠀⠄⠀⢕⠐ ⠄⠁⠁⠄⠀⠄⢀⠀⠐⠀⠀⠁⢁⢀⠐⠀⠀⠀⢁⠐⠄⠀⠀⠔⠀⢐⠁⠄⠀⠑⠀⢀⠁⠀⠐⠐⠁⠀⠄⠀⢀⠀⠀⠀⠐⠀⠐⠀⠅⠀⠀⢄⢀⠐⠁⠐⠄⠁⢀⠀⠀⠐⠁⠀⠀⠄⢄⠀⠕⠁⠀⠐⢄⠀⠀⢀⠐⠄⠁⠀ ⠀⠀⢀⠁⢀⠀⠑⢀⠀⠄⠀⠀⠅⢑⠀⠁⠐⠀⠀⠐⠀⠄⠁⢄⠀⢑⠀⠄⢑⠀⠁⠀⢀⠑⢐⠀⠁⢀⠄⠐⢀⠄⠁⠀⠀⠀⠀⢀⠄⠀⠀⠑⠀⢀⠔⢁⠀⠀⠀⠀⠐⠁⠀⠑⢀⠀⠐⠀⢄⠔⢐⠄⠅⠐⠀⠅⢁⠀⠁⠁ ⠅⢀⠄⠑⠀⠀⠅⠄⠀⢐⠐⠀⠀⠄⠀⢁⠄⠀⢔⢀⠁⠀⠔⠁⠑⢐⠀⠐⠀⠁⢑⠀⠀⢁⠀⠀⠄⠀⠀⠑⢀⠀⠄⠔⠁⠀⠄⠀⠐⢀⠀⠀⠔⠁⠀⠐⠀⠀⠐⠁⠐⠀⠀⢀⠄⠁⢁⠀⠀⠐⠀⠁⢐⠀⠐⠀⠄⠑⠐⠄ ⠀⠀⠀⢐⠑⠑⢀⠁⠑⢀⠐⠀⠄⠀⠀⢀⢐⠕⠄⠀⠀⠀⠐⠀⠀⢀⠄⠀⠀⠀⠄⠐⠐⠀⠀⠁⢄⠐⠅⢀⠐⠄⠁⠐⠀⠅⢀⠐⢁⢀⠀⠁⠐⠕⠀⠀⠀⠀⢐⠀⠅⠐⠔⢁⠀⠐⠅⠐⠄⢀⠀⢄⠀⢀⠄⠀⠀⢀⠁⠐ ⢀⠀⠀⢀⠁⠀⠀⠀⢁⠁⠐⠀⠁⢐⢀⠀⠁⠀⠔⠁⢄⠁⠁⠄⠀⢀⠄⠀⢐⠀⠔⠁⢀⠕⠁⢀⠁⠀⢀⠔⢐⠀⠀⠁⢀⠀⠀⢀⠔⠀⠄⠄⠁⠀⠄⢐⠄⠁⢁⠀⠄⠀⠀⠄⠀⢄⠀⢀⢀⠁⠄⢀⠄⠀⢀⠁⢁⠀⠀⠀ ⠁⠄⠀⠀⠄⠀⠄⠀⠄⠑⢄⠔⠁⠀⠁⠀⠐⠀⠀⠀⠀⠀⢀⠀⠀⠄⠁⢁⠐⠀⠀⢀⠀⠄⠐⠀⢐⠀⠁⠀⠀⠁⠁⠄⠁⢄⠔⠀⠐⠀⠀⠔⢄⠀⠀⢐⠀⢅⠀⠁⢀⠀⠀⠀⠀⠀⠄⠀⠐⠀⠀⠀⠄⠀⠀⠀⠐⠀⠄⠄ ⠀⠑⠐⠔⠀⢀⢀⠀⢁⠔⠁⢁⠄⠁⠀⠀⠀⠅⠀⢀⠀⠁⢀⠀⢄⠀⠀⠀⠐⠀⢀⠐⠁⢀⠀⠀⠀⢀⠁⠀⠐⠀⠄⢀⠔⢁⠀⠀⢅⠐⠑⠅⠀⠐⠀⢀⠁⢄⠀⠀⢁⠐⠄⠀⠐⢕⢀⠁⢀⠁⠑⠅⠀⢁⠐⠀⠁⠀⢁⢐ ⢀⠁⠄⠀⠀⢄⠁⠄⠀⠀⠐⠅⠁⠁⢀⢀⢅⠄⠐⢁⠀⠄⠀⠄⠅⠑⢀⠔⢀⠀⠀⢁⠀⠕⠐⠀⠀⠐⢄⠐⢀⠄⠀⠁⢀⠁⢀⠀⠄⢀⠀⠀⠀⢀⠑⢐⠀⠀⠁⠄⠐⠁⠄⠄⠀⠀⠐⢄⢀⠀⠄⠄⠀⠀⠀⠄⢄⢀⠄⠀ ⠐⠄⠐⠁⠀⠔⠑⠀⠀⠐⠀⠀⠑⠀⠐⠄⠀⠀⠐⠀⠁⢀⠄⠀⠀⢐⠀⠔⠀⠀⢄⠄⠁⢐⠀⠀⢄⠔⠀⢀⢐⠁⠅⢀⠀⠄⠐⠀⢐⠀⠁⢕⠄⠀⠀⢔⠁⠀⢐⠀⢀⠄⠑⠄⠀⠀⠄⠀⠀⠄⠐⠁⠄⠀⠐⠔⠄⠀⠀⠀ ⢀⠐⢀⢐⠀⠀⠄⠑⠑⠐⠐⠀⠔⠑⠀⠐⠀⢀⠀⠀⢀⠄⠀⠁⢄⠀⠁⠀⢀⠁⢀⠀⠀⠀⠐⠄⠁⢐⠔⠅⢐⠅⠀⠀⠅⠀⠀⠀⠁⠀⠔⠄⠀⠔⢀⠀⠄⢁⠐⢁⢀⢁⢀⢀⢁⠄⠁⢀⠀⠀⢁⢑⠀⢀⢐⠁⠀⠀⠀⠁ ⠀⠄⠅⠀⠁⠅⠁⢁⠄⠀⠀⢀⠀⢄⠀⠁⠁⢁⠀⠄⢅⢁⠄⠄⠐⢀⢀⠄⠁⠀⠀⠀⢄⠔⠁⢀⠐⠁⠄⠐⠀⠀⠁⢐⠀⠀⢀⢀⠀⠀⠀⠐⠀⠄⠐⠀⠀⠁⠄⠀⠁⠀⠀⠁⢄⠀⠁⢅⠀⠄⠁⠀⠁⠅⢀⠀⠀⠀⠐⠁ ⠁⠀⠀⠀⠀⠀⠀⢄⠀⠐⢀⠀⠐⠄⠄⠁⠀⠔⠔⠄⠀⠁⠀⠐⠄⢀⠀⠄⠔⠀⠁⠀⠀⢐⢔⠁⠅⠀⠀⢐⠀⠀⠄⠄⠀⠑⠔⠀⠅⢀⠁⠔⢀⠀⢔⠀⠁⠐⠐⠐⢐⠔⠀⠐⠀⠐⠀⠀⠐⢐⠄⠐⠐⠀⠑⢐⠐⠑⠐⠐ ⢀⠁⠁⠀⠀⢑⢀⠀⠑⢀⠀⢀⠀⠀⠁⢔⠀⠀⠀⠀⢀⢀⠁⠁⢄⠀⢁⠀⠀⠐⠁⢀⠐⢁⠐⠐⢁⠐⠀⢄⠐⠅⠀⢐⠄⢁⢀⠐⠄⠐⠐⠀⠀⠔⠀⠑⢔⢀⠑⠀⠀⠐⠑⠀⠀⠐⢀⢀⠑⠀⠐⢀⠀⠁⠐⠁⠀⢁⠀⠀ ⠀⠔⠀⢀⠀⠀⢀⠑⠄⠁⠄⠄⢀⠐⠁⠁⠅⠁⢁⢀⠁⠀⢐⠀⠁⠅⢀⢁⠀⢀⠑⢑⠄⠀⠀⠄⠀⠁⢄⠀⢐⠄⠁⠑⢀⠅⢑⠀⠀⠀⠄⠄⢄⠄⠕⢀⠀⠔⢄⢀⠀⠀⠀⠁⢄⠄⠀⠁⠀⠐⠄⠀⠁⢀⠄⠔⠁⠀⠁⠄ ⠀⠀⠐⠀⠄⠀⠀⢀⠄⠄⢄⠔⠐⢄⠀⠀⠄⠀⠀⠀⠀⠀⢄⠔⠐⠀⠔⠐⠀⠀⠔⠀⠀⢕⢔⠀⠁⢐⠁⢑⠐⠁⠀⠀⠀⢄⠀⠀⢅⠐⠑⠐⠀⠀⢐⠔⠀⠄⠀⠑⢔⠀⠀⠔⠀⠁⢀⠄⠀⠀⠀⠀⠀⠐⠀⠀⠐⠀⠐⠀ ⠄⠐⠀⠄⠀⢀⠐⠀⢀⢐⠀⢀⠄⠀⢐⠀⠀⠀⠀⠐⠐⢄⠀⠀⠔⠀⢀⠀⠀⢐⢔⠀⢀⢄⠀⠄⢀⢀⠐⠁⢐⠅⠅⢀⠑⠄⠐⠐⠀⢀⠀⠁⠁⠑⠀⢁⠅⠀⠁⠄⠀⠁⠀⠀⠁⠁⠁⠐⠑⠁⠁⠀⢀⠐⢀⢀⠀⠁⠀⢀ ⢁⢀⠄⠁⠐⠀⢁⠀⠀⠀⠀⠁⠀⢑⠀⢁⠐⠀⠀⠀⢁⠁⢐⠀⢀⠀⠀⠀⢕⢄⢁⢑⠄⠀⠔⢀⠐⠁⢀⠄⠐⠄⠄⢑⢄⠅⢄⠀⠁⢁⢀⠐⠁⢀⠀⠄⠀⠐⠀⠀⠀⢀⠀⠁⢄⠀⠄⠀⢀⠅⢁⠀⠀⢀⠀⠅⠄⠀⠑⠀ ⠁⠄⠄⠁⠄⠀⠀⠀⠀⠁⠀⠄⠁⠀⠀⠄⠀⠀⠁⠄⠀⠁⠄⠀⠀⠄⠄⠄⠀⠀⠄⠀⠄⠁⠄⠀⠅⠄⠁⢕⢐⠀⢀⠔⠀⠔⠄⠑⠐⠀⠑⢔⠐⠁⠐⠐⠀⢄⠐⠐⠄⠀⠀⠀⠔⠑⠄⠄⠀⠀⠀⠀⢀⠄⠀⠀⠀⠁⢐⠔ ⠐⠀⠑⢐⠁⠀⢐⠑⢁⢀⠐⢀⢐⠑⠁⠀⠀⢀⠀⠁⠑⠀⠑⢐⢀⠑⢐⠀⠁⢑⠀⠑⠐⠐⠐⠑⢐⠑⢑⠄⣔⢅⢁⢁⠐⢀⢁⢅⠁⠐⢐⠀⠀⠄⢀⢐⢅⢁⠀⠀⠀⠀⠐⠁⢁⠔⢀⢑⠁⢁⠐⢀⠀⠀⢄⢀⢁⢅⢀⠀ ⢀⠀⠀⠁⠀⠀⠀⢐⢀⠁⠀⠀⠁⠀⠅⠀⠔⢁⢀⠀⠀⠀⢁⢁⠁⢐⠀⢀⠅⠅⢀⠀⠄⢁⠄⢄⠀⢕⠅⠑⢄⠀⠄⢄⢀⠄⢀⠄⠄⠀⢄⠀⠄⢄⠀⠀⢀⠄⢀⢀⠄⠀⠄⠄⠀⢀⠀⢄⠄⠀⢄⢀⠄⢀⢀⠄⠀⠄⠀⢀ ⠐⢄⠀⠄⠀⠄⠐⠀⠀⠁⢀⠀⠅⠀⠄⠄⠀⠀⠀⢀⠔⠕⠄⠄⠑⠀⠀⠁⠀⠐⠔⢄⠀⠀⢄⠐⠔⢀⠁⢐⢀⠐⠄⠐⠁⠀⠄⠐⠐⠄⠁⠀⠐⠀⠄⠀⠑⠄⠐⠀⠀⠐⠀⠔⠀⠁⠔⠀⠁⠀⠀⠑⠄⠔⠀⠀⠀⠑⠐⠀ ⠀⠀⢀⠄⠐⠀⠀⠀⢀⠄⠀⢑⢀⠁⠐⢀⠑⠀⠔⠐⢁⢐⠀⠐⢀⠀⠑⢐⠀⠀⢀⠐⢐⢔⠐⠄⢀⠁⠁⢐⠑⢄⢄⠑⠀⠁⠐⠐⢁⠐⠑⢁⠑⢀⢀⢀⠐⠁⢐⢐⠀⠐⠐⠀⢀⠑⢁⠁⠀⠀⠀⠑⠀⠁⢐⢀⠑⠀⢀⢀ ⠁⢀⠀⠀⢁⠀⠀⠅⠀⠀⠅⠀⠀⠐⢀⢀⢀⠄⠀⠅⠀⢁⠔⠀⠁⢁⠁⠁⠑⢄⠀⠁⠁⢀⢀⠄⠑⢔⠀⠐⠔⠁⠀⠄⠀⠑⢀⠀⠕⠄⠀⠀⠄⢀⠀⠁⢄⠁⢄⠄⠐⠄⢄⠔⠀⠀⠐⠁⢀⠐⠀⠀⠅⠀⠀⠔⠀⢀⠁⠀ ⠀⢄⠐⠁⠀⠐⠕⠀⠄⠐⠀⠐⠀⢀⠐⠐⠀⠀⠅⠀⠄⠁⢀⠄⠀⠄⠔⠑⢀⠀⠅⠀⠅⠄⠀⠄⠁⢀⠄⠀⢀⠀⢁⢀⠕⠀⠀⠑⠀⠐⠀⢄⠐⠁⢄⠄⠁⠐⠄⠐⢀⠀⠁⠄⠔⠀⢄⠀⠁⠄⠔⠁⢐⠄⠐⠀⠀⠑⢀⠔ ⢀⠐⢀⠀⠀⠐⠄⠁⠐⠄⠐⠀⢀⠑⠁⠄⠀⠁⠐⠀⢀⠀⠁⢀⠀⠐⠐⠔⠁⢀⠀⠑⠀⠀⠐⠀⢔⠑⠀⢐⠀⢁⢀⠐⠀⢀⠐⢀⠄⠁⢄⠁⠀⠀⠁⠀⠀⠀⢐⢀⢁⢑⠀⢀⠑⠐⠁⠀⢀⢀⠀⠁⢀⢀⠀⠀⠐⢀⠀⠐ ⢀⢁⠀⠀⢑⢅⢁⢄⢀⢀⠅⠀⠀⠄⢀⢁⢐⢁⢀⢅⢄⠀⠀⢀⢀⠐⠅⠁⠀⠀⢁⠐⠀⢀⠀⠀⠐⢀⠀⢀⠄⠅⠐⢐⠀⠀⠔⠁⠑⠐⠄⠀⠄⠀⠅⠁⠄⠐⠀⠀⠁⠁⠀⠄⠅⠀⠀⠄⠄⠅⠀⠄⠀⠄⠀⠁⠀⠀⠔⠀ ⠁⠀⠀⠁⠀⠀⠀⢀⠄⠀⠀⠀⠀⠄⠄⠀⢀⠀⠐⢀⠀⠀⢄⠔⠄⠀⠄⠀⠀⠔⠕⢀⠔⠀⠀⠄⠄⠀⠁⠐⠀⠀⠕⢀⠕⠁⠀⠁⢑⠀⠀⢀⢀⠐⠄⠀⠑⠀⠀⠁⢄⠔⠑⢐⠀⠑⢄⠐⠀⠀⠐⠀⠀⠀⠀⠀⠄⠁⢀⠄ ⠀⠁⠐⠀⠁⠀⠄⠀⠑⠀⠀⢀⠀⠐⠀⠄⠀⠑⠀⠀⢐⠀⠁⢅⠀⠀⠀⠐⠀⢀⠄⠀⢁⢄⠀⠁⠔⠑⠄⠀⠑⢄⠔⠁⢀⠀⠀⢄⠄⠀⠀⠐⠁⠁⢀⠐⠄⠀⠁⠐⠁⢀⢑⠁⠐⠐⢀⠑⠔⠀⠁⠀⢁⢀⠄⠁⢐⠀⠀⠀ ⠀⠅⠁⢀⠐⠀⠁⠐⠀⠁⠐⢄⠀⢄⢀⠀⠄⢀⠁⢁⠄⠀⠐⠀⢑⠄⠀⠑⠐⠀⠁⠀⠁⠐⠐⠀⠁⠄⠄⢀⠄⠁⠐⢀⠄⠐⠀⠄⠀⠄⠀⠀⢀⠄⢀⢐⠀⠑⠀⠀⠄⢄⢄⠀⢅⠀⠀⠄⠀⠅⠀⠄⠐⢀⠀⠔⠅⠀⠄⢁ ⠄⠀⠄⠄⠀⠄⠀⢀⠀⠐⠀⠀⠁⠀⠔⠄⠀⠀⠁⠀⠄⢄⠀⠐⠀⠀⠄⢑⠀⠁⠅⠀⠁⠀⢀⠄⠑⢀⠄⢀⢀⠔⢀⠀⠑⠄⠀⠅⠀⠀⠅⢕⠀⠐⢐⠀⠄⠕⠀⠀⢀⠀⠀⢀⠀⠁⠀⠀⠐⢀⠐⠁⢀⠔⠁⢐⠀⠀⠐⠀ ⠀⠐⢁⢀⠐⠀⢀⠁⠀⠀⠁⠑⠄⠀⢁⠐⠁⠅⢀⠐⢀⠄⠀⠀⠐⠀⠅⢀⠐⢀⢀⠁⠅⢀⠀⠄⠔⠑⠁⠀⠁⠀⠐⠁⢀⠀⠀⢀⠀⠐⠄⠔⠐⠁⢄⠀⠅⢄⠑⠀⢀⠐⠀⠀⢁⢀⠀⢀⠁⢀⠁⠅⠁⠀⠁⠀⠀⠄⠀⠁ ⠀⠀⢀⠀⠄⢁⠀⠀⠄⠀⢁⢁⠀⠀⠀⠐⠀⠄⠀⠐⠀⢀⢀⠁⠁⠄⠄⢀⠀⠀⠑⢀⠀⠑⠐⠁⠀⠀⠁⢐⠄⠀⢀⠐⠄⠐⢀⠁⠑⢀⠀⠀⠐⠀⢑⠄⠀⠁⠀⠅⠐⠄⠀⠀⠄⠀⠄⠁⠀⠄⢁⢀⠁⠁⠄⠀⠀⠀⠀⢄ ⠑⠀⠀⠀⢀⠀⠁⠄⠐⠀⠀⠄⢄⠀⠐⠐⠀⠑⢁⠀⠔⠀⠀⠀⠀⠀⠕⢄⠀⠐⠀⢀⠔⠅⢀⠀⠐⠀⠅⢐⠀⠕⠐⢀⠀⠔⠀⠅⠀⠀⠀⠄⢀⠁⢀⠀⠀⠔⠀⠐⠁⢀⠀⠁⢀⠁⠀⠐⠐⠄⠐⠐⠄⠀⠀⠀⠀⠀⠔⠐ ⠐⠀⢐⠀⠀⠀⢀⠀⠐⠐⠀⠀⠐⠀⠄⢀⠁⢄⠀⠑⢀⠀⠐⢀⢄⠀⠀⢀⠀⢅⢔⠁⠄⠐⠀⠁⠀⠑⠀⠀⠐⠁⠄⠀⢁⢀⠀⠁⠐⠁⠀⠀⠀⠀⠀⠀⠀⠀⠐⢀⠄⠀⢀⢔⠑⢅⠀⠐⢄⠁⢀⠄⢁⢀⠐⠀⠀⢀⢀⢑ ⠀⠄⠅⢀⠁⠀⠀⠅⠁⠀⢄⠀⠁⠐⠁⢀⠀⠀⠀⠀⠀⠑⠀⠄⢀⠀⠀⢀⠐⠀⠀⢀⠁⠐⢀⠄⠁⢔⠄⠀⠄⠄⠑⠄⠁⠀⠀⠁⠐⠐⠄⠁⢄⠀⢀⠄⠁⠀⠔⠁⢀⠐⠄⠀⠀⠀⢁⢐⠀⠀⠄⠀⠀⢀⠀⠅⠀⠀⠀⠀ ⠔⠀⠄⠀⢀⠄⠁⢀⠁⠄⠀⠀⠑⠀⠐⠁⠀⠐⠑⢀⠄⠄⠀⠀⢄⠀⠔⠔⢀⠀⠁⠀⠔⠀⢀⠄⠀⠀⠁⢐⠀⠑⠀⠀⠀⢅⠀⠀⢀⠀⠁⠄⠀⠁⢀⠀⠔⠐⠀⠀⢅⠀⠐⢀⠀⠀⠄⢀⠐⠔⠀⠁⠄⠀⠁⠀⠔⠐⠀⠀ ⠀⠐⢀⠐⠀⠁⢀⠀⠀⠐⠐⢀⢄⠐⢄⠐⠀⠅⠀⠁⠁⠄⠐⢁⠄⠀⠀⢄⠀⠅⠔⠀⢁⠀⠐⠄⢀⠀⠁⠀⠐⠀⢀⠑⢀⠄⠀⠅⠀⠀⠅⠀⠀⢀⢔⠐⠄⠀⠁⠀⠐⠀⠀⢀⠑⠀⠄⠐⢁⢀⠀⢄⢄⠁⢀⠀⢐⠐⠁⠁ ⠁⠄⠄⠀⠀⠁⠀⢐⠀⠐⠀⠄⢑⠀⠀⠑⠄⠁⢁⢀⠀⢑⠔⠁⠀⠄⠄⠀⢀⠀⠑⠔⠁⢁⠀⠄⢁⠔⠀⢀⠔⠀⢐⠀⠀⠀⠄⠄⠀⠐⠁⢁⠔⠁⠐⠐⠁⢀⢀⠀⠁⠔⠀⠀⠀⠅⠁⠀⠄⠀⠔⠁⢑⠀⠀⠀⠀⠀⠐⠀ ⠁⠀⠅⠐⠀⠁⠀⠀⠐⠁⠀⠀⠕⠀⠀⠅⠀⠐⠀⠀⠕⠁⠀⠄⠅⠀⠀⠐⠀⠐⠅⠀⠀⠄⠀⠀⠀⠀⠀⠐⠀⠀⠀⠀⠁⠀⠀⠀⠄⠀⠐⠁⠀⠄⠁⠀⠁⠄⠀⠐⠄⠀⠅⠀⠀⠔⠁⠀⠀⠕⠀⠀⠀⠀⠀⠁⠀⠁⠀⠀
Python
<lang python># coding=UTF-8 from __future__ import print_function, division from math import sqrt
def cell(n, x, y, start=1):
d, y, x = 0, y - n//2, x - (n - 1)//2 l = 2*max(abs(x), abs(y)) d = (l*3 + x + y) if y >= x else (l - x - y) return (l - 1)**2 + d + start - 1
def show_spiral(n, symbol='# ', start=1, space=None):
top = start + n*n + 1
is_prime = [False,False,True] + [True,False]*(top//2)
for x in range(3, 1 + int(sqrt(top))):
if not is_prime[x]: continue
for i in range(x*x, top, x*2):
is_prime[i] = False
cell_str = lambda x: f(x) if is_prime[x] else space f = lambda _: symbol # how to show prime cells
if space == None: space = ' '*len(symbol)
if not len(symbol): # print numbers instead
max_str = len(str(n*n + start - 1))
if space == None: space = '.'*max_str + ' '
f = lambda x: ('%' + str(max_str) + 'd ')%x
for y in range(n):
print(.join(cell_str(v) for v in [cell(n, x, y, start) for x in range(n)]))
print()
show_spiral(10, symbol=u'♞', space=u'♘') # black are the primes show_spiral(9, symbol=, space=' - ')
- for filling giant terminals
- show_spiral(1001, symbol='*', start=42)</lang>
- Output:
♘♘♘♞♘♘♘♘♘♘ ♘♘♘♘♞♘♞♘♘♘ ♘♞♘♘♘♘♘♞♘♞ ♞♘♞♘♘♘♞♘♘♘ ♘♘♘♞♘♞♘♞♘♘ ♘♘♞♘♘♞♞♘♞♘ ♘♞♘♞♘♘♘♘♘♘ ♞♘♘♘♞♘♘♘♘♘ ♘♞♘♘♘♞♘♘♘♞ ♞♘♘♘♘♘♞♘♘♘ - - - - 61 - 59 - - - 37 - - - - - 31 - 67 - 17 - - - 13 - - - - - 5 - 3 - 29 - - - 19 - - 2 11 - 53 - 41 - 7 - - - - - 71 - - - 23 - - - - - 43 - - - 47 - - - 73 - - - - - 79 - -
Racket
<lang racket>#lang racket (require (only-in math/number-theory prime?))
(define ((cell-fn n (start 1)) x y)
(let* ((y (- y (quotient n 2)))
(x (- x (quotient (sub1 n) 2)))
(l (* 2 (if (> (abs x) (abs y)) (abs x) (abs y))))
(d (if (> y x) (+ (* l 3) x y) (- l x y))))
(+ (sqr (- l 1)) d start -1)))
(define (show-spiral n
#:symbol (smb "# ")
#:start (start 1)
#:space (space (and smb (make-string (string-length smb) #\space))))
(define top (+ start (sqr n) 1))
(define cell (cell-fn n start))
(define print-cell
(if smb
(λ (i p?) (display (if p? smb space)))
(let* ((max-len (string-length (~a (+ (sqr n) start -1))))
(space (or space (make-string (string-length (~a (+ (sqr n) start -1))) #\_))))
(λ (i p?)
(display (if p? (~a #:width max-len i #:align 'right) space))
(display #\space)))))
(for* ((y (in-range 1 (add1 n))) #:when (unless (= y 1) (newline)) (x (in-range 1 (add1 n))))
(define c (cell x y))
(define p? (prime? c))
(print-cell c p?))
(newline))
(show-spiral 9 #:symbol #f) (show-spiral 10 #:symbol "♞" #:space "♘") ; black are the primes (show-spiral 50 #:symbol "*" #:start 42)
- for filling giant terminals
- (show_spiral 1001 "*" 42)</lang>
- Output:
37 __ __ __ __ __ 31 __ 89
__ 17 __ __ __ 13 __ __ __
__ __ 5 __ 3 __ 29 __ __
__ 19 __ __ 2 11 __ 53 __
41 __ 7 __ __ __ __ __ __
__ __ __ 23 __ __ __ __ __
43 __ __ __ 47 __ __ __ 83
__ __ __ __ __ 79 __ __ __
11 __ __ __ __ __ __ __ __
♘♘♘♞♘♞♘♘♘♞
♞♘♘♘♘♘♞♘♞♘
♘♞♘♘♘♞♘♘♘♘
♘♘♞♘♞♘♞♘♘♘
♘♞♘♘♞♞♘♞♘♞
♞♘♞♘♘♘♘♘♘♘
♘♘♘♞♘♘♘♘♘♘
♞♘♘♘♞♘♘♘♞♘
♘♘♘♘♘♞♘♘♘♘
♞♘♘♘♘♘♘♘♘♘
* * * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * *
* * * * * * *
* * * * *
* * * * * * * * *
* * * * * * *
* * * * * *
* * * * * * * * *
* * * * * * * *
* * * * * *
* * * * * * * * * *
* * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * *
* * * * * * * * * * *
* * * * * * * * *
* * * * *
* * * * * * * * *
* * * * * *
* * * * * * * *
* * * * * * * * * * *
* * * * * *
* * * *
* * * * * * * * * * * * * * *
* * * * * * * *
* * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * * * * * * *
* * * * * *
* * * * *
* * * * * * * *
* * * * * *
* * * * * *
* * * * *
* * * *
* * * * *
* * * * * * * * *
* * * * * * * *
* * * * * *
* * * * * * *
* * * * * *
* * * *
REXX
Programming note for the showing of the spiral: because images can't be uploaded at this time on Rosetta Code, the glyphs for primes was chosen to be a solid glyph (or in ASCII or XML terminology, a "block").
This then allows the REXX program to compress two rows of the Ulam spiral into one by processing two rows at a time by comparing each character to the character on the next line (when comparing two lines as a pair):
- if a char on row k is a block, and the char on row k+1 is a block, then a "block" is used.
- if a char on row k is a block, and the char on row k+1 is a blank, then a "uhblk" is used.
- if a char on row k is a blank, and the char on row k+1 is a block, then a "lhblk" is used.
- if a char on row k is a blank, and the char on row k+1 is a blank, then a blank is used.
For codepage 437:
- a "block" is 'db'x █
- a "uhblk" is 'df'x ▄
- a "lhblk" is 'dc'x ▀
Or, to show all three characters in the (above) ordered next to each other (separated by a blank): █ ▄ ▀
This allows the displaying of the Ulam prime spiral to keep a (mostly) square aspect ratio.
The characters chosen allow for the HTML on Rosetta Code to shrink (via STYLE font-size) the displayed output.
counter-clockwise
<lang rexx>/*REXX pgm shows cntr-clockwise Ulam spiral of primes in a square matrix*/ parse arg size init char . /*get the matrix size from the CL*/ if size== | size==',' then size=79 /*No size? Then use default of 79*/ if init== | init==',' then init= 1 /*No init? Then use default of 1 */ if char== then char='█' /*No char? Then use default of █ */ tot=size**2; offset=init-1 /*numbers in spiral; start offset*/ uR.=0; bR.=0 /*the upper/bottom right corners.*/
do od=1 by 2 to tot; _=od**2+1+offset; uR._=1; _=_ + od; bR._=1; end
bL.=0; uL.=0 /*the bottom/upper left corners. */
do ev=2 by 2 to tot; _=ev**2+1+offset; bL._=1; _=_ + ev; uL._=1; end
$.= bigP=0; #p=0; app=1; inc=0; r=1; $=0; minR=1; maxR=1; $=0; !.= /*──────────────────────────────────────────────construct the spiral #s.*/
do i=init for tot; r=r+inc; minR=min(minR,r); maxR=max(maxR,r)
x=isPrime(i); if x then bigP=max(bigP,i); #p=#p+x /*bigP, #primes.*/
if app then $.r=$.r || x /*append token.*/
else $.r= x || $.r /*prepend token.*/
if uR.i then do; app=1; inc=+1; iterate; end /*advance ↓ */
if bL.i then do; app=0; inc=-1; iterate; end /* " ↑ */
if bR.i then do; app=0; inc= 0; iterate; end /* " ► */
if uL.i then do; app=1; inc= 0; iterate; end /* " ◄ */
end /*i*/
do j=minR to maxR by 2; jp=j+1; $=$+1 /*fold two lines*/
do k=1 for length($.j); top=substr($.j,k,1) /*the 1st line*/
bot=word(substr($.jp,k,1) 0,1) /*2nd line*/
if top then if bot then !.$=!.$'█' /*has top & bot.*/
else !.$=!.$'▀' /*has top,¬ bot.*/
else if bot then !.$=!.$'▄' /*¬ top, has bot*/
else !.$=!.$' ' /*¬ top, ¬ bot.*/
end /*k*/
end /*j*/ /* [↓] show prime# spiral matrix*/
do m=1 for $; say !.m; end /*m*/
say; say init 'is the starting point,' ,
tot 'numbers used,' #p "primes found, largest prime:" bigP
exit /*stick a fork in it, we're done.*/ /*───────────────────────────────────ISPRIME subroutine──────────────────────────────*/ isPrime: procedure; parse arg x; if x<2 then return 0 if wordpos(x,'2 3 5 7')\==0 then return 1 if x//2==0 then return 0; if x//3==0 then return 0
do j=5 by 6 until j*j>x; if x//j==0 then return 0; if x//(j+2)==0 then return 0; end
return 1</lang>
- Output:
when the default inputs are used
▀ ▀ ▀ ▄ ▀ ▄ ▄▀ ▄▀ ▀ ▀ ▄ ▄ ▀ ▄▀
▄▀ ▀▄ ▄ ▄ ▀ ▄▀ ▀ ▄▀ ▀ ▀ ▀ ▀ ▄ ▀ ▄
▀ ▀ ▄ ▀ ▄▀ ▄▀ ▄ ▀ ▄ ▄ ▄ ▀
▀▄ ▄▀ ▀ ▄ ▄▀ ▀▄▀ ▄ ▀ ▄ ▄ ▄ ▀ ▀
▀ ▄ ▄ ▀ ▄ ▄▀ ▀ ▄ ▀▄ ▄ ▀ ▀ ▄ ▄ ▀ ▄ ▄
▀ ▄ ▀ ▀ ▄▀▄ ▀ ▄ ▀ ▀ ▀ ▀ ▄ ▀ ▄ ▀▄
▀ ▀ ▀ ▄▀ ▄▀ ▄ ▄▀ ▄ ▄▀ ▄ ▀ ▄ ▄ ▄ ▄ ▀▄ ▄ ▀▄
▄ ▄ ▀▄ ▄ ▄ ▄ ▄ ▀▄ ▀ ▄▀ ▄ ▄ ▀ ▀ ▀▄ ▄
▀ ▄ ▀ ▀ ▀ ▀▄▀▄ ▀ ▄ ▀ ▀▄ ▀ ▀▄ ▀▄ ▄
▄ ▀ ▄ ▄ ▄ ▄▀ ▀ ▀▄ ▄▀ ▄▀ ▄ ▀ ▀ ▀▄▀ ▀ ▄ ▀ ▀▄
▄ ▄ ▄ ▄ ▄ ▀▄ ▄ ▀ ▄▀ ▀▄ ▄▀ ▀ ▄▀▄ ▄ ▄ ▄ ▀
▀▄▀ ▀ ▀ ▀▄▀▄ ▄ ▄ ▀▄ ▀▄ ▄▀ ▀
▄ ▄ ▄ ▄ ▄▀ ▄▀ ▀ ▀▄ ▄ ▄ ▀ ▀ ▀▄ ▀ ▀ ▀
▀▄ ▀ ▄ ▄▀▄ ▄▀▄ ▀ ▄ ▄ ▄▀ ▀ ▄ ▀ ▄ ▄▀ ▀
▀ ▀ ▄ ▀▄ ▀ ▀▄ ▄ ▄▀ ▄ ▀▄ ▀ ▀ ▀ ▄▀ ▄
▄ ▄ ▄ ▀▄▀▄ ▄ ▄▀ ▀ ▄ ▄▀ ▀ ▀ ▄▀▄▀ ▀▄ ▄ ▄ ▄ ▀
▀ ▀ ▀ ▀ ▀▄ ▄ ▄ ▄ ▀▄ ▄ ▀▄ ▄ ▄▀ ▄ ▄ ▄
▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀▄ ▄ ▄▀ ▀ ▀ ▀▄ ▀▄
▀▄ ▀▄ ▄ ▀▄ ▄ ▀ ▀▄ ▀▄ ▄ ▄ ▄▀▄ ▄▀▄▀▄ ▄▀ ▀ ▀ ▄ ▀ ▀ ▀ ▄ ▄ ▄▀ ▀
▄ ▄ ▄ ▄ ▄ ▄▀ █▄▀▄ ▄ ▄ ▄ ▄▀▄ ▄ ▀ ▄ ▄▀▄ ▄
▀ ▀ ▀ ▄ ▀ ▀ ▀ ▀▄▀ ▀▄
▄ ▄ ▄ ▄▀ ▀ ▄ ▀ ▄▀ ▀▄ ▀▄▀ ▀▄ ▀ ▀▄ ▄▀ ▄▀ ▀ ▀▄ ▀ ▀▄ ▄▀ ▄
▄▀▄ ▀▄ ▀ ▄ ▄ ▄ ▄ ▀ ▄ ▄ ▄▀ ▄ ▄ ▀ ▄ ▀▄ ▄
▀ ▀ ▀ ▀ ▀ ▀▄ ▀▄ ▀ ▄ ▄ ▄ ▀ ▀ ▀ ▀ ▀
▀ ▄ ▄ ▀▄ ▄ ▄ ▄ ▄ ▄ ▀ ▀ ▄▀▄ ▀▄ ▀ ▄ ▄▀ ▄▀▄▀ ▀▄ ▄▀ ▄
▄ ▄ ▄ ▄ ▄ ▄▀▄ ▀ ▄ ▄ ▀▄▀▄ ▄ ▄ ▄ ▄ ▄ ▄
▀ ▄ ▀ ▀ ▀ ▀ ▀▄ ▀ ▀ ▀▄ ▄ ▄ ▄▀ ▀▄ ▀▄ ▀ ▀
▄▀ ▄ ▀▄ ▄ ▄▀ ▀▄ ▀ ▀ ▄ ▀ ▀ ▀ ▄ ▀▄ ▀▄▀
▀ ▄▀▄ ▀ ▀ ▀ ▀ ▀▄ ▀▄ ▄ ▄▀ ▀ ▄
▀ ▄▀ ▀ ▀ ▄ ▀ ▀ ▀ ▀ ▄▀ ▄ ▄ ▄▀ ▀▄ ▀▄▀ ▀
▀ ▄ ▄ ▄▀ ▀▄ ▄ ▄▀▄ ▄ ▀ ▄ ▄ ▀ ▀ ▀ ▄
▄ ▄ ▀ ▄ ▀▄ ▄ ▄ ▄ ▄ ▄▀ ▀▄ ▄
▄▀ ▀ ▀ ▄ ▄ ▀ ▄ ▄ ▄▀ ▀▄ ▄ ▀ ▀ ▄
▀▄ ▄ ▄ ▀ ▄ ▄ ▄ ▄▀ ▀ ▄ ▀ ▀ ▀ ▀ ▀
▄ ▄▀▄ ▄ ▀ ▄ ▀▄ ▀▄▀ ▀ ▀▄ ▄ ▀▄ ▀
▀▄▀ ▀ ▀ ▀ ▀ ▄▀ ▀ ▀ ▀ ▄▀ ▄ ▄ ▄ ▀
▄ ▀ ▀ ▄ ▀ ▀ ▄▀▄ ▀▄ ▄▀ ▄▀ ▀ ▄ ▀
▄ ▀▄ ▄▀ ▄▀▄ ▀ ▀ ▀▄▀ ▄ ▀▄▀ ▄ ▀
▄ ▀▄ ▀▄ ▄ ▀ ▀ ▄ ▄ ▀ ▀ ▄ ▄ ▄ ▀▄
▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀
1 is the starting point, 6241 numbers used, 811 primes found, largest prime: 6229
- Output:
when the following input is used
▀▄ ▄▀ ▄ ▀ ▄ ▀▄▀ ▄ ▀ ▀ ▀ ▄ ▀ ▄ ▄▀
▀ ▀ ▀▄ ▄ ▀ ▄▀ ▀ ▀▄ ▄ ▄ ▀ ▄▀
▄▀▄ ▄▀ ▀▄▀ ▄ ▄ ▀▄ ▄ ▄ ▀ ▀ ▄ ▀ ▄▀ ▄▀ ▀▄▀
▀ ▀ ▀ ▀ ▄▀ ▄ ▄ ▀ ▄ ▀ ▄▀ ▄ ▄▀ ▀▄▀ ▄
▀ ▄ ▄ ▀▄ ▀ ▄ ▄ ▀ ▄ ▄ ▀ ▀▄ ▀ ▄ ▀ ▄ ▄▀ ▄▀
▄ ▄ ▄ ▄ ▄ ▀▄▀ ▀ ▀ ▄ ▀ ▀ ▄▀ ▀ ▀▄ ▀
▀ ▄ ▀ ▀ ▀ ▀▄ ▄ ▄▀ ▄ ▀ ▄ ▄ ▄▀ ▄▀ ▄▀▄
▄▀ ▄ ▀ ▄ ▄ ▀ ▄ ▀ ▄ ▄▀ ▄ ▀ ▀ ▀
▀ ▄▀▄ ▀▄ ▀ ▀ ▀ ▀▄▀▄ ▀▄▀ ▄
▀ ▄▀ ▀ ▀ ▄ ▀▄ ▄▀ ▀ ▄▀▄ ▀▄ ▄ ▄ ▄ ▄ ▄ ▄▀ ▄ ▄ ▀
▀ ▄ ▄ ▄▀ ▀ ▀ ▄ ▀ ▄ ▄ ▀ ▄▀ ▀▄ ▄▀
▄ ▄ ▀ ▀ ▄▀▄ ▀ ▄▀▄ ▀▄ ▄▀ ▄▀ ▄ ▄ ▄
▄▀ ▀ ▀ ▀ ▀ ▄▀▄ ▀ ▄ ▄ ▀ ▄▀▄ ▄ ▄ ▄
▀▄ ▄ ▄ ▀ ▄ ▄ ▀▄ ▄ ▄ ▄ ▀ ▄ ▀▄ ▄ ▄▀ ▀ ▀
▄ ▀ ▄▀▄ ▀▄▀ ▄ ▄ ▀ ▄▀ ▀ ▀ ▀ ▀ ▀▄▀ ▀ ▀▄ ▀
▀▄▀ ▀ ▀ ▀ ▄ ▄▀ ▀ ▄▀▄▀▄ ▄ ▄ ▄ ▄ ▄
▄ ▀ ▀ ▄ ▀ ▀▄ ▄▀ ▀ ▄▀ ▀▄ ▀▄ ▀ ▄ ▀
▄ ▀ ▄ ▄▀ ▀ ▀▄▀▄ ▄▀ ▄ ▀▄ ▄▀ ▀ ▀ ▄ ▀ ▀ ▄
▀ ▄ ▄▀ ▀ ▀ ▄ ▀ ▄ ▀▄▀ ▄ ▄ ▄ ▀ ▄ ▀
▀ ▄ ▄▀ ▀▄ ▀ ▄ ▀ ▄ ▄▀▄ ▄▀ ▀▄ ▄▀ ▀▄▀ ▀ ▀ ▀
▄ ▀▄ ▄ ▄ ▄ ▄ ▄ ▄▀ ▀ ▄▀▄▀ ▀ ▀▄▀ ▀ ▀▄ ▄▀
▀ ▄ ▀ ▄ ▄ ▀ ▀ ▀▄▀ ▀ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄
▄ ▄ ▄ ▀▄ ▄ ▄ ▀▄▀▄ ▄▀▄ ▀ ▀ ▀ ▀ ▄▀ ▀▄ ▀ ▀
▄▀ ▄ ▄▀ ▄▀ ▄ ▀ ▀ ▀ ▄ ▀ ▀▄ ▀
▀ ▀ ▀▄ ▀ ▄▀▄ ▄▀ ▀ ▄▀ ▄ ▄▀ ▄▀▄ ▄ ▄ ▄ ▀ ▄ ▄
▄ ▄▀ ▀ ▄ ▄ ▄ ▄ ▄▀ ▄▀▄ ▄ ▀▄ ▀▄ ▄ ▀ ▀▄
▄ ▀ ▀▄ ▄▀ ▄ ▄ ▀▄ ▀ ▀ ▄ ▀▄▀ ▄ ▄ ▀▄ ▄ ▀▄
▀ ▀ ▀▄▀ ▀▄▀ ▄▀ ▄▀ ▄▀ ▄▀ ▄ ▀ ▀▄ ▄
▄▀ ▀ ▀▄ ▄ ▄▀ ▀▄ ▀ ▄ ▀ ▄ ▀▄ ▄
▀▄ ▄ ▄ ▄ ▀ ▀ ▄ ▄ ▄ ▀ ▀▄ ▀ ▀ ▄▀ ▀ ▀▄▀ ▀ ▄ ▀ ▀▄
▄▀ ▀ ▄ ▄ ▀ ▄ ▀ ▀ ▀ ▀▄▀ ▄▀ ▄ ▄ ▄ ▀
▄ ▀▄ ▀▄ ▄▀ ▀▄ ▀ ▄▀ ▄ ▄ ▀ ▀ ▀ ▄ ▄ ▄▀ ▀
▄ ▄ ▄▀ ▀▄ ▄ ▀ ▄ ▀ ▀ ▄ ▄ ▀ ▄ ▀▄ ▀ ▀ ▀
▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▄ ▄ ▄ ▄▀ ▀ ▄▀ ▀ ▄▀ ▀
▄ ▄▀ ▀ ▀▄ ▄ ▄ ▀ ▄ ▀▄ ▀ ▀ ▄ ▄
▄▀ ▄ ▄ ▄ ▀ ▄ ▄ ▄ ▄▀ ▄ ▀ ▀▄ ▄▀
▀ ▀▄▀ ▄▀ ▀ ▄ ▀ ▀ ▄▀ ▄▀▄▀ ▄▀ ▄ ▄ ▄
▀ ▄▀ ▄ ▀▄▀ ▄ ▀ ▄ ▀ ▀▄ ▄ ▀ ▀
▀ ▄ ▄ ▄ ▀▄ ▄ ▀ ▀ ▀ ▄▀ ▀ ▀ ▀
▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀
41 is the starting point, 6241 numbers used, 805 primes found, largest prime: 6277
- Output:
with an input of 416 can be viewed here at ───► Ulam spiral (for primes)/REXX
clockwise
This REXX version is presented here to show the difference between a clockwise and a counter-clockwise Ulam (prime) spiral. <lang rexx>/*REXX pgm shows a clockwise Ulam spiral of primes in a square matrix. */ parse arg size init char . /*get the matrix size from the CL*/ if size== | size==',' then size=79 /*No size? Then use default of 79*/ if init== | init==',' then init= 1 /*No init? Then use default of 1 */ if char== then char='█' /*No char? Then use default of █ */ tot=size**2; offset=init-1 /*numbers in spiral; start offset*/ uR.=0; bR.=0 /*the upper/bottom right corners.*/
do od=1 by 2 to tot; _=od**2+1+offset; uR._=1; _=_ + od; bR._=1; end
bL.=0; uL.=0 /*the bottom/upper left corners. */
do ev=2 by 2 to tot; _=ev**2+1+offset; bL._=1; _=_ + ev; uL._=1; end
$.= bigP=0; #p=0; app=1; inc=0; r=1; $=0; minR=1; maxR=1; $=0; !.= /*──────────────────────────────────────────────construct the spiral #s.*/
do i=init for tot; r=r+inc; minR=min(minR,r); maxR=max(maxR,r)
x=isPrime(i); if x then bigP=max(bigP,i); #p=#p+x /*bigP, #primes.*/
if app then $.r=$.r || x /*append token.*/
else $.r= x || $.r /*prepend token.*/
if uR.i then do; app=1; inc=+1; iterate; end /*advance ↓ */
if bL.i then do; app=0; inc=-1; iterate; end /* " ↑ */
if bR.i then do; app=0; inc= 0; iterate; end /* " ► */
if uL.i then do; app=1; inc= 0; iterate; end /* " ◄ */
end /*i*/
do j=minR to maxR by 2; jp=j+1; $=$+1 /*fold two lines*/
do k=1 for length($.j); top=substr($.j,k,1) /*the 1st line*/
bot=word(substr($.jp,k,1) 0,1) /*2nd line*/
if top then if bot then !.$=!.$'█' /*has top & bot.*/
else !.$=!.$'▀' /*has top,¬ bot.*/
else if bot then !.$=!.$'▄' /*¬ top, has bot*/
else !.$=!.$' ' /*¬ top, ¬ bot*/
end /*k*/
end /*j*/ /* [↓] show prime# spiral matrix*/
do m=1 for $; say !.m; end /*m*/
say; say init 'is the starting point,' ,
tot 'numbers used,' #p "primes found, largest prime:" bigP
exit /*stick a fork in it, we're done.*/ /*───────────────────────────────────ISPRIME subroutine──────────────────────────────*/ isPrime: procedure; parse arg x; if x<2 then return 0 if wordpos(x,'2 3 5 7')\==0 then return 1 if x//2==0 then return 0; if x//3==0 then return 0
do j=5 by 6 until j*j>x; if x//j==0 then return 0; if x//(j+2)==0 then return 0; end
return 1</lang>
- Output:
when using the default input
▀ ▄ ▄▀ ▄ ▄ ▄ ▄ ▀ ▀ ▀ ▄ ▀ ▄ ▀ ▀ ▀ ▄ ▄
▄ ▄▀ ▀ ▄▀ ▀▄ ▄ ▀ ▀▄ ▄ ▄ ▄ ▀
▄ ▀ ▄ ▀ ▀ ▀▄ ▄▀ ▄▀ ▀▄ ▀ ▀ ▄ ▄▀
▀▄▀ ▄▀ ▀ ▀ ▀ ▀▄ ▄ ▄▀▄▀ ▀
▀ ▀▄▀ ▀ ▀▄▀▄ ▀▄ ▀ ▀ ▄ ▀▄ ▀▄ ▄ ▄▀ ▄
▄ ▄ ▄ ▀▄ ▄ ▄▀ ▄ ▀ ▄▀ ▀ ▀ ▀ ▀ ▀
▀ ▄▀ ▄ ▄ ▀ ▀ ▄ ▄ ▀▄ ▄ ▄▀ ▀ ▀ ▀ ▄
▄ ▄ ▀ ▀ ▄▀ ▄ ▄ ▀▄ ▄ ▄ ▀▄▀ ▄ ▀ ▀ ▄
▄ ▄▀▄ ▄ ▄ ▀▄ ▄ ▄ ▄ ▄ ▀ ▀ ▄
▀▄ ▀▄ ▀ ▀▄ ▄▀ ▄ ▄ ▀ ▀▄ ▀▄
▀ ▀ ▀ ▀▄ ▄ ▀ ▀ ▀ ▀ ▀ ▀▄ ▄ ▄ ▀ ▄ ▀ ▀ ▄▀
▀▄ ▄ ▀ ▄▀ ▀ ▄ ▄ ▀ ▄ ▀ ▀ ▄▀ ▀▄ ▀▄ ▄
▀▄ ▄▀ ▀ ▄▀▄ ▄▀▄ ▀ ▄ ▀▄▀ ▀ ▀ ▀ ▀
▄▀▄ ▀▄▀ ▀ ▀▄▀ ▄▀ ▀▄ ▄ ▀▄ ▄ ▀▄ ▄ ▀ ▀▄ ▄ ▄ ▄▀▄ ▀ ▄
▄ ▄ ▄ ▄ ▄ ▄▀▄ ▄▀ ▄ ▄▀ ▀ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄
▀ ▀ ▄ ▄ ▀▄▀ ▄▀▄ ▀ ▀ ▀ ▀ ▀ ▀ ▀
▀▄▀▄▀ ▀ ▄ ▄▀▄▀ ▀ ▄▀▄ ▄ ▄▀ ▄ ▀ ▄ ▄▀ ▄ ▀ ▄▀ ▄
▀ ▄ ▄▀ ▄ ▀▄ ▄ ▄ ▄ ▄▀ ▄ ▄▀▄ ▄ ▀▄ ▄ ▀▄ ▄
▄ ▀ ▀ ▀ ▀ ▀ ▀▄▀ ▄▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀
▀ ▀▄▀▄ ▄ ▀ ▀▄ ▀ ▄▀ ▀▄▀ ▄▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄
▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄ ▄▀ ▀▄▀ ▄ ▀ ▄ ▄ ▀ ▄▀
▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▄ ▄▀ ▀▄▀ ▀ ▀ ▀ ▄ ▀ ▀▄
▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀▄ ▄ ▀▄ ▀▄▀ ▄ ▄ ▄▀▄ ▄ ▄ ▄ ▀ ▄
▄▀ ▄ ▄ ▄ ▄ ▄ ▄ ▀ ▄▀ ▀▄▀ ▄ ▄ ▄▀ ▄▀▄ ▀▄
▄ ▀▄▀ ▄▀ ▀▄ ▄ ▀ ▄▀ ▀ ▄▀ ▀ ▀ ▄ ▀ ▄
▀ ▀▄ ▄ ▀ ▄▀▄▀ ▄ ▄ ▄▀▄ ▄ ▀▄ ▀ ▀ ▀▄ ▀ ▄
▄▀ ▀▄ ▄▀▄ ▀ ▀ ▄ ▄▀ ▀ ▄▀ ▄ ▄ ▄ ▀ ▀
▄ ▄ ▄ ▄ ▀▄ ▀ ▀ ▀ ▄ ▄ ▀ ▀ ▀ ▄▀ ▀ ▀
▀ ▀▄ ▄ ▀▄ ▄ ▀▄ ▀▄▀▄ ▄ ▄ ▄ ▀ ▀ ▄ ▄ ▄ ▄▀▄ ▀
▄ ▄ ▄ ▄ ▄ ▀ ▀ ▀▄▀ ▄▀ ▄ ▄ ▀ ▀ ▄ ▄ ▄▀
▄ ▀ ▄ ▄▀ ▀ ▀ ▄▀ ▄ ▀ ▄ ▀ ▀ ▀ ▀ ▀▄ ▀▄▀
▀▄ ▄ ▀▄▀ ▄▀ ▀ ▀▄ ▄ ▄▀ ▄ ▀ ▀▄ ▀▄▀▄ ▀ ▄ ▄
▀ ▄ ▄ ▄ ▄ ▄ ▀ ▄▀ ▄▀ ▄▀ ▄ ▄ ▀▄ ▄▀▄ ▄
▀ ▀ ▄▀ ▀ ▀▄ ▄ ▀ ▄ ▀ ▀ ▄ ▄ ▄▀ ▀
▄▀ ▀ ▀▄ ▄▀▄ ▀ ▄ ▀ ▀ ▄▀▄ ▀ ▀▄ ▀▄ ▄ ▄
▄▀▄ ▄ ▄ ▀ ▄ ▀▄▀ ▄ ▀ ▄ ▄▀ ▀ ▀
▀ ▀ ▀ ▄ ▀ ▀ ▀▄ ▄ ▀ ▄ ▄ ▄ ▀ ▄ ▀
▀▄▀ ▄ ▀▄ ▄ ▀ ▀▄ ▄ ▀ ▄ ▀▄
▀ ▀ ▄▀ ▄▀▄▀ ▄▀ ▀ ▀▄▀ ▀▄ ▀ ▄
▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀ ▀
1 is the starting point, 6241 numbers used, 811 primes found, largest prime: 6229
Ruby
<lang ruby>require 'prime'
def cell(n, x, y, start=1)
y, x = y - n/2, x - (n - 1)/2 l = 2 * [x.abs, y.abs].max d = y >= x ? l*3 + x + y : l - x - y (l - 1)**2 + d + start - 1
end
def show_spiral(n, symbol=nil, start=1)
puts "\nN : #{n}"
format = "%#{(start + n*n - 1).to_s.size}s "
n.times do |y|
n.times do |x|
i = cell(n,x,y,start)
if symbol
print i.prime? ? symbol[0] : symbol[1]
else
print format % (i.prime? ? i : )
end
end
puts
end
end
show_spiral(9) show_spiral(25) show_spiral(25, "# ")</lang>
- Output:
N : 9
61 59
37 31
67 17 13
5 3 29
19 2 11 53
41 7
71 23
43 47
73 79
N : 25
577 571 569 563 557
479 467 463
401 397 389 383
487 317 313 311 307 461
257 251 241 379
197 193 191
139 137 239 547
491 199 101 97 181 457
61 59 131
331 103 37 31 89 179
587 409 263 149 67 17 13 373
5 3 29
151 19 2 11 53 127 233 541
107 41 7
71 23
499 337 109 43 47 83 173 449
593 269 73 79 229 367
113 293
271 157 163 167 227
503 211 223
419 277 281 283
347 349 353 359 443
599 421 431 433 439
509 521 523
601 607 613 617 619
N : 25
# # # # #
# # #
# # # #
# # # # # #
# # # #
# # #
# # # #
# # # # # #
# # #
# # # # # #
# # # # # # # #
# # #
# # ## # # # #
# # #
# #
# # # # # # # #
# # # # # #
# #
# # # # #
# # #
# # # #
# # # # #
# # # # #
# # #
# # # # #
zkl
Simulates turtle graphics, spiral by walking straight while holding left hand against the wall dropping prime breadcrumbs.
Using Extensible prime generator#zkl and the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl. <lang zkl>var primes=Utils.Generator(Import("sieve.zkl").postponed_sieve); var offsets=Utils.Helpers.cycle( T(0,1),T(-1,0),T(0,-1),T(1,0) ); const BLACK=0, WHITE=0xffffff, GREEN=0x00ff00, RED=0xff0000, EMPTY=0x0808080; fcn uspiral(N,n=1){
if((M:=N).isEven) M+=1; // need odd width, height
img:=PPM(M,M,EMPTY);
// collect all primes<=N*N+n
ps:=primes.filter('wrap(p){ p<=N*N+n and True or Void.Stop });
x:=N/2; y:=x; img[x,y]=GREEN; n+=1; x+=1;
while(True){
ox,oy:=offsets.next(); leftx,lefty:=offsets.peek();
while(True){
img[x,y]=( if(ps.holds(n)) WHITE else BLACK ); if(n==N*N) break(2); // all done n+=1; if(img[x+leftx,y+lefty]==EMPTY) // nothing to my left, turn left
{ x+=leftx; y+=lefty; break; }
x+=ox; y+=oy;
} } img
} uspiral(501).write(File("foo.ppm","wb"));</lang>
- Output:
A PPM image similar to that shown in Perl6 but denser. A green dot marks the center.
