Babylonian spiral

Discussion thread for Babylonian spiral.

The statement currently wrongfully indicates:

xᵢ² + yᵢ² = nᵢ² > nᵢ₋₁² where xᵢ, yᵢ and nᵢ are non-negative integers

but actually the nᵢ’s defined as such are not necessarily integers. More likely, they should simply not be squared here: This problem is not related to Pythagorean triples.

I would like to share a Python solution of mine, which uses several FP iterators to find all the possible moves and choose the best:

from math import atan2, tau
from itertools import chain, count, dropwhile, takewhile, starmap

def get_pairs(i: int, j: int):
    def _neg4(i, j):
        def _neg2(i, j):
            return (i, j), (-i, -j)
        return _neg2(i, j) + _neg2(i, -j)
    return _neg4(i, j) + (_neg4(j, i) if i != j else ())

def babylonian_spiral(n_steps):
    x = [0, 0]
    y = [0, 1]

    dx, dy = 0, 1
    n = 1        # dx² + dy² = n
    for _ in range(n_steps):
        possibles = []  # possible (d1,d2) pairs where d1 ≥ d2 and d1² + d2² = n
        angle = atan2(dy, dx)
        for n in count(n + 1):
            for d1 in takewhile(lambda i: i ** 2 <= n, dropwhile(lambda i: 2 * i ** 2 < n, count(1))):
                tmp = n - d1 ** 2
                for d2 in dropwhile(lambda i: i ** 2 != tmp, takewhile(lambda i: i <= d1 and i ** 2 <= tmp, count())):
                    possibles.append((d1, d2))
            if possibles:
                all_poss = set(chain.from_iterable(starmap(get_pairs, possibles)))  # all possible moves
                dx, dy = min(all_poss, key=lambda d: (atan2(d[1], d[0]) - angle) % tau)  # clockwise angular separation
                x.append(x[-1] + dx)
                y.append(y[-1] + dy)
                break

    return x, y

Could’ve used isqrt to improve if Python 3.8+ supported, though :slight_smile: