 ## Decomposing the Ulam spiral

By: on September 27, 2012

The Ulam spiral is a well-known mystery to mathematicians: draw a 1 in a grid, 2 in the cell to the right, 3 above the 2, and so on in a spiral:

 17 16 15 14 13 18 5 4 3 12 19 6 1 2 11 20 7 8 9 10 21 22 23 24 25

Colour the primes:

 17 16 15 14 13 18 5 4 3 12 19 6 1 2 11 20 7 8 9 10 21 22 23 24 25

For reasons unknown, long diagonal chains of primes appear. In this very small Ulam spiral, we don’t really see them (19, 7, 23), but we will.

How can we draw our own spiral? The essential elements of the spiral are two-fold: a primality test, and winding the line of positive integers round and round the origin of the complex plane. Hm, composing functions sounds promising!

Our primality test is a function from the positive integers to (True, False). Our traversal/map is a function from the positive integers to C, the complex plane. That is, given an integer n it tells us where on the plane that point will be after traversing the spiral n steps.

Squeak images have `Integer >> #isPrime` built in, so we need just write the map function.

Integer >> ulam
"Ulam maps integers to (the integral values of) the complex plane.
1 maps to 0@0, 2 maps to 1@0, 3 maps to 1@1, and so on in an
anticlockwise square spiral."

| n lastCorner squareSize sqModulus bottomLeft topLeft topRight |
n := self leastSatisfier: [:k | ((2 * k) + 1) squared].
squareSize := (2*n) + 1.
lastCorner := squareSize squared.
bottomLeft := lastCorner - (1 * (squareSize - 1)).
topLeft := lastCorner - (2 * (squareSize - 1)).
topRight := lastCorner - (3 * (squareSize - 1)).
sqModulus := squareSize // 2.
self = lastCorner ifTrue: [^ sqModulus @ sqModulus negated].
bottomLeft <= self ifTrue:
["bottom edge of square"
^ (sqModulus negated + (self - bottomLeft)) @ sqModulus negated].
topLeft < self ifTrue:
["left edge of square"
^ sqModulus negated @ (sqModulus - (self - topLeft))].
topRight < self ifTrue:
["top edge of square"
^ (sqModulus - (self - topRight)) @ sqModulus].
^ sqModulus @ (sqModulus - (topRight - self)).

Integer >> leastSatisfier: aUnaryBlock
"Can we find an integer value for which (aUnaryBlock value: n) = anInteger?"
| k n max |
"While this prevents nontermination, it means not being able to generate
large spirals. Hold your nose and move along."

max := 10000.
n := 0.
[k := aUnaryBlock value: n.
k >= self ifTrue: [^ n].
n = max ifTrue: [Error signal: 'Couldn''t satisfy equation ',
aUnaryBlock decompile printString, ' with value ', self printString].
n := n + 1] repeat.

With this in hand, the solution is simple: create a canvas, select the primes, and paint those points representing primes.

| form primes width |
width := 400.

primes := (1 to: width squared) select: #isPrime.
form := Form extent: width@width depth: 1.
primes do: [:p | | u |
u := p ulam.
"ulam returns origin-centred values, so we translate the points to the
middle of the form. Too, we flip the points in the x-axis to match
Form's layout, which as 1@1 at the top left."

u := (u flipBy: #vertical centerAt: 0@0)
translateBy: (width // 2)@(width // 2).

"Filling always fills Rectangles. The smallest Rectangle is
thus 1px wide. Let u = (x,y). Then u + 1 = (x + 1, y + 1)."

form fill: (u corner: (u + 1)) fillColor: Color black].

And result! As a result of our insight – decomposing the problem into separate traversal, find and do-something functions, we may now construct different spirals: rectangular spirals, clockwise spirals, and so on.

1. al deaprix says:

I solved this problem a long time ago and put it up in the internet in 2009. Basically, look at the problem as a series of embedded squares. Each square has eight points more than the one immediately inside. All primes follow one of two progressions: 1+6n and 5+6n. The rest of the solution rests on modularity generating prime-rich (or prime-poor) diagonals. The problem took less than 20 minutes to solve, but nearly 20 years to write up and self-publish. Its a lot like being able to see motion at zero time – you just have to know where to look. Most problems are simpler than they appear.

2. All prime numbers -except 2 & 3- are adjacent to a multiple of 6. Many composite numbers are ALSO adjacent to a multiple of 6.
When you populate an Ulam spiral with BOTH of these groups of numbers, the prime ones and the composite ones, you get

ENDLESS- UNINTERRUPTED- DIAGONAL rows of numbers in both diagonal directions.

All pairs of adjacent parallel rows of numbers are identically spaced. 2 subset-spirals can be derived from the foregoing:

one populated with ONLY the composite numbers adjacent to a multiple of 6 and one populated with ONLY the prime numbers adjacent to a multiple of 6.

This last subset-spiral is identical to the standard Ulam spiral except: 2 & 3 not shown, as they are not adjacent to a multiple of 6, while 1 is shown as it is adjacent to 0, which is amultiple of 6.

For more of this, please see:
https://www.ulamspiralmethod.com