This is a Python script I wrote to generate generalized Ulam spirals.
I call the spirals generated by my code Ulamish spirals, they are one dimensional polylines that cross all two dimensional lattice points (points where both coordinates are integers), and they grow in a counterclockwise spiral manner. And my code can generate a single spiral, two spirals that don't cross each other, and four spirals:
In a single spiral, the spiral starts at the origin and goes right first, then turns up, left and down, and repeat. After every two turns the length until the next turn increments by one. The spiral is composed entirely of segments and right angles, the segments are always parallel to one of the axes. I know there can be a one-to-one mapping between natural numbers and lattice points, so I numbered the lattices as such.
In a pair of spirals, the spirals both start at the origin, and together they cross all lattice points, while each cross exactly half of the infinite lattice points (which is still the same amount of infinity, of course), and they never intersect with each other.
The growth of the spirals is similar to the first one, one of the spirals is rotated, and every two turns the length grows by two.
I know the number of integers is equal to the number of natural numbers, and I created the second variation to map all integers to all lattices, because in the first variation I can't do so.
Four spirals are the maximum I can come up with that together cross all lattice points and don't intersect with each other. They are like the two spirals variation, one spiral has three rotated copies, and the spirals' length grows by two after every turn.
I wanted to label the lattice points with unique numbers, so I chose real integers and integers with only imaginary parts (lattices on the imaginary axis), again, they have the same number of elements as the lattices.
I used infinite iterators to generate the points, and I did all these without using a single if condition, my code is very efficient, though not the most efficient as shown here.
But I have implemented two generalizations that weren't covered by the answer.
Below is my code:
import matplotlib.pyplot as plt
from itertools import cycle, islice, repeat
from PIL import Image
from typing import Generator, List, Tuple
def step_x(x: int, y: int, sign: int, length: int) -> Tuple[zip, int]:
return zip(range(x + sign, (end := x + sign * length) + sign, sign), repeat(y)), end
def step_y(x: int, y: int, sign: int, length: int) -> Tuple[zip, int]:
return zip(repeat(x), range(y + sign, (end := y + sign * length) + sign, sign)), end
def ulamish_spiral_gen() -> Generator:
x = y = length = 0
yield 0, 0
sign = cycle([1, 1, -1, -1])
while True:
length += 1
arm, x = step_x(x, y, next(sign), length)
yield from arm
arm, y = step_y(x, y, next(sign), length)
yield from arm
def gather(generator: Generator, n: int) -> List[Tuple[int]]:
return list(islice(generator, n))
def ulamish_spiral(n: int) -> List[Tuple[int]]:
return gather(ulamish_spiral_gen(), n)
def ulamish_spiral_2_gen(x: int, y: int, sign: int) -> Generator:
length = 1
yield 0, 0
yield x, y
while True:
arm, y = step_y(x, y, next(sign), length)
yield from arm
length += 2
arm, x = step_x(x, y, next(sign), length)
yield from arm
def ulamish_spiral_2(n: int) -> List[List[Tuple[int]]]:
return gather(ulamish_spiral_2_gen(1, 0, cycle([1, -1, -1, 1])), n), gather(
ulamish_spiral_2_gen(-1, 0, cycle([-1, 1, 1, -1])), n
)
def get_steps(quad: List[int]) -> cycle:
return cycle([[step_x, step_y][q] for q in quad])
def ulamish_spiral_4_gen(x: int, y: int, sign: cycle, order: List[int]) -> Generator:
steps = get_steps(order)
order = cycle(order)
stack = [x, y]
length = 2
yield 0, 0
yield x, y
while True:
arm, stack[next(order)] = next(steps)(*stack, next(sign), length)
yield from arm
length += 2
def ulamish_spiral_4(n: int) -> List[List[Tuple[int]]]:
return [
gather(ulamish_spiral_4_gen(x, y, cycle(sign), order), n)
for x, y, sign, order in (
(1, 0, [1, -1, -1, 1], [1, 0, 1, 0]),
(-1, 0, [-1, 1, 1, -1], [1, 0, 1, 0]),
(0, 1, [-1, -1, 1, 1], [0, 1, 0, 1]),
(0, -1, [1, 1, -1, -1], [0, 1, 0, 1]),
)
]
def get_figure(length: int, x: List[int], y: List[int]) -> Tuple[plt.Axes, plt.Figure]:
length /= 100
fig, ax = plt.subplots(figsize=(length, length), dpi=100, facecolor="black")
ax.set_axis_off()
fig.subplots_adjust(0, 0, 1, 1, 0, 0)
plt.axis("scaled")
ax.axis([x[0], x[1], y[0], y[1]])
return ax, fig
def get_data(n: int, level: int) -> List[List[Tuple[int]]]:
return [ulamish_spiral, ulamish_spiral_2, ulamish_spiral_4][level](n)
def process_level_1_data(
data: List[Tuple[int]], length: int
) -> Tuple[Tuple[List[int]], plt.Axes, plt.Figure]:
xs, ys = zip(*data)
ax, fig = get_figure(length, [min(xs) - 1, max(xs) + 1], [min(ys) - 1, max(ys) + 1])
return [(xs, ys)], ax, fig
def process_data(data: List[List[Tuple[int]]], length: int):
xmin = ymin = 1e309
xmax = ymax = -1e309
coords = []
for spiral in data:
xs, ys = zip(*spiral)
xmin = min(min(xs), xmin)
ymin = min(min(ys), ymin)
xmax = max(max(xs), xmax)
ymax = max(max(ys), ymax)
coords.append((xs, ys))
ax, fig = get_figure(length, [xmin - 1, xmax + 1], [ymin - 1, ymax + 1])
return coords, ax, fig
def get_label(n: int, vert: bool, sign: int) -> List[str]:
return [f'{i}{"i"*vert}' for i in range(0, n * sign, sign)]
def get_image(fig: plt.Figure) -> Image:
fig.canvas.draw()
image = Image.frombytes(
"RGB", fig.canvas.get_width_height(), fig.canvas.tostring_rgb()
)
plt.close(fig)
return image
def plot_spiral(n: int, level: int, length: int = 1080) -> Image:
data = get_data(n, level)
if not level:
coords, ax, fig = process_level_1_data(data, length)
else:
coords, ax, fig = process_data(data, length)
for (xs, ys), labels in zip(
coords,
(
get_label(n, 0, 1),
get_label(n, 0, -1),
get_label(n, 1, 1),
get_label(n, 1, -1),
),
):
ax.plot(xs, ys, "o-", color="cyan", lw=2)
for x, y, label in zip(xs, ys, labels):
ax.annotate(label, (x, y), color="white", fontsize=16)
return get_image(fig)
How can I make it more efficient?
Update
I have considered using mathematics myself, I tried to derive a quadratic equation for it myself, but of course the shape isn't a parabola.
I thought maybe the lengths of the segments are quadratic, but the curve doesn't agree with the series of lengths fully (0, 1, 1, 2, 2, 3, 3, 4, 4...), I tried to use a software to find a curve of best fit with n terms, but no matter how many terms I throw at it, the curve is always off. Surprisingly you can't write a simple equation for the above series.
Then I came across this answer on Mathematics Stack Exchange, and to find the coordinate of a given number you have four different equations, all of them quadratic, and the conditions for which equation to use are also quadratic, and contains a term that has to be calculated using square root and if conditions...
And the computational cost for a single term is much more expensive than just a single increment. Sure, it would be faster if I were to find the coordinate for large n, I don't need to calculate all the previous coordinates, but to get all coordinates before n, the method simply is very inefficient.
