user
f
The **Babylonian spiral** is a sequence of points in the plane that are created so as to
continuously minimally increase in vector length and minimally bend in vector direction,
while always moving from point to point on strictly integral coordinates. Of the two criteria
of length and angle, the length has priority.

Examples

P(1) and P(2) are defined to be at (x = 0, y = 0) and (x = 0, y = 1). The first vector is
from P(1) to P(2). It is vertical and of length 1. Note that the square of that length is 1.

Next in sequence is the vector from P(2) to P(3). This should be the smallest distance to a
point with integral (x, y) which is longer than the last vector (that is, 1). It should also bend clockwise
more than zero radians, but otherwise to the least degree.

The point chosen for P(3) that fits criteria is (x = 1, y = 2). Note the length of the vector
from P(2) to P(3) is √2, which squared is 2. The lengths of the vectors thus determined can be given by a sorted
list of possible sums of two integer squares, including 0 as a square.

Task

Find and show the first 40 (x, y) coordinates of the Babylonian spiral.

Stretch task

Show in your program how to calculate and plot the first 10000 points in the sequence. Your result
should look similar to the graph shown at the OEIS:

See also

* OEIS:A256111 - squared distance to the origin of the n-th vertex on a Babylonian Spiral. * OEIS:A297346 - List of successive x-coordinates in the Babylonian Spiral. * OEIS:A297347 - List of successive y-coordinates in the Babylonian Spiral.
assistant
**Translation of**: Wren

### Translation

```
sub babylonianSpiral (\nsteps) {
    my @squareCache = (0..nsteps).hyper.map: *²;
    my @dxys = [0, 0], [0, 1];
    my $dsq  = 1;

    for ^(nsteps-2) {
        my \Θ = atan2 |@dxys[*-1][1,0];
        my @candidates;

        until @candidates.elems {
            $dsq++;
            for @squareCache.kv -> \i, \a {
                last if a > $dsq/2;
                for reverse 0 .. $dsq.sqrt.ceiling -> \j {
                    last if $dsq > (a + my \b = @squareCache[j]);
                    next if $dsq != a + b;
                    @candidates.append: [i, j], [-i, j], [i, -j], [-i, -j],
                                        [j, i], [-j, i], [j, -i], [-j, -i]
                }
            }
        }
        @dxys.push: @candidates.min: { ( Θ - atan2 |.[1,0] ) % τ };
    }

    [\»+«] @dxys
}

# The task
say "The first $_ Babylonian spiral points are:\n",
(babylonianSpiral($_).map: { sprintf '(%3d,%4d)', @$_ }).batch(10).join("\n") given 40;

# Stretch
use SVG;

'babylonean-spiral-raku.svg'.IO.spurt: SVG.serialize(
    svg => [
        :width<100%>, :height<100%>,
        :rect[:width<100%>, :height<100%>, :style<fill:white;>],
        :polyline[ :points(flat babylonianSpiral(10000)),
          :style("stroke:red; stroke-width:6; fill:white;"),
          :transform("scale (.05, -.05) translate (1000,-10000)")
        ],
    ],
);

```

Output:

```
The first 40 Babylonian spiral points are:
(  0,   0) (  0,   1) (  1,   2) (  3,   2) (  5,   1) (  7,  -1) (  7,  -4) (  6,  -7) (  4, -10) (  0, -10)
( -4,  -9) ( -7,  -6) ( -9,  -2) ( -9,   3) ( -8,   8) ( -6,  13) ( -2,  17) (  3,  20) (  9,  20) ( 15,  19)
( 21,  17) ( 26,  13) ( 29,   7) ( 29,   0) ( 28,  -7) ( 24, -13) ( 17, -15) ( 10, -12) (  4,  -7) (  4,   1)
(  5,   9) (  7,  17) ( 13,  23) ( 21,  26) ( 28,  21) ( 32,  13) ( 32,   4) ( 31,  -5) ( 29, -14) ( 24, -22)
```

Stretch goal:

(offsite SVG image - 96 Kb) - babylonean-spiral-raku.svg

### Independent implementation

Exact same output; about one tenth the execution time.

```
my @next = { :x(1), :y(1), :2hyp },;

sub next-interval (Int $int) {
     @next.append: (0..$int).map: { %( :x($int), :y($_), :hyp($int² + .²) ) };
     @next = |@next.sort: *.<hyp>;
}

my @spiral = [\»+«] lazy gather {
    my $interval = 1;
    take [0,0];
    take my @tail = 0,1;
    loop {
        my \Θ = atan2 |@tail[1,0];
        my @this = @next.shift;
        @this.push: @next.shift while @next and @next[0]<hyp> == @this[0]<hyp>;
        my @candidates = @this.map: {
            my (\i, \j) = .<x y>;
            next-interval(++$interval) if $interval == i;
            |((i,j),(-i,j),(i,-j),(-i,-j),(j,i),(-j,i),(j,-i),(-j,-i))
        }
        take @tail = |@candidates.min: { ( Θ - atan2 |.[1,0] ) % τ };
    }
}

# The task
say "The first $_ Babylonian spiral points are:\n",
@spiral[^$_].map({ sprintf '(%3d,%4d)', |$_ }).batch(10).join: "\n" given 40;

# Stretch
use SVG;

'babylonean-spiral-raku.svg'.IO.spurt: SVG.serialize(
    svg => [
        :width<100%>, :height<100%>,
        :rect[:width<100%>, :height<100%>, :style<fill:white;>],
        :polyline[ :points(flat @spiral[^10000]),
          :style("stroke:red; stroke-width:6; fill:white;"),
          :transform("scale (.05, -.05) translate (1000,-10000)")
        ],
    ],
);

```

Same output: