This is the third notebook in my posts on the Advent of Code challenges. The notebook in its original format can be found on my github.
Day 3: Spiral Memory¶
Numbers are arranged 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---> ...
Given an integer n, what is its Manhattan Distance from the center (1) of the spiral? For instance, the distance of 3 is $2 = 1 + 1$, since it’s one space to the right and one space up from the center.
Here’s my idea. The bottom right corner of the $k$th layer is the integer $(2k+1)^2$, since that’s how many integers are contained within that square. The other three corners in that layer are $(2k+1)^2 – 2k, (2k+1)^2 – 4k$, and $(2k+1)^2 – 6k$. Finally, the closest spot on the $k$th layer to the origin is at distance $k$: these are the four “axis locations” halfway between the corners, at $(2k+1)^2 – k, (2k+1)^2 – 3k, (2k+1)^2 – 5k$, and $(2k+1)^2 – 7k$.
For instance when $k = 1$, the bottom right is $(2 + 1)^2 = 9$, and the four “axis locations” are $9 – 1, 9 – 3, 9-5$, and $9-7$. The “axis locations” are $k$ away, and the corners are $2k$ away.
So I will first find which layer the number is on. Then I’ll figure out which side it’s on, and then how far away it is from the nearest “axis location” or “corner”.
My given number happens to be 289326.
import math
def find_lowest_larger_odd_square(n):
upper = math.ceil(n**.5)
if upper %2 == 0:
upper += 1
return upper
assert find_lowest_larger_odd_square(39) == 7
assert find_lowest_larger_odd_square(26) == 7
assert find_lowest_larger_odd_square(25) == 5
find_lowest_larger_odd_square(289326)
539**2 - 289326
It happens to be that our integer is very close to an odd square.
The square is $539^2$, and the distance to that square is $538$ from the center.
Note that $539 = 2(269) + 1$, so this is the $269$th layer of the square.
The previous corner to $539^2$ is $539^2 – 538$, and the previous corner to that is $539^2 – 2\cdot538 = 539^2 – 1076$.
This is the nearest corner.
How far away from the square is this corner?
539**2 - 2*538 - 289326
That’s really close to the corner. The corner is $538$ from the center, and the square is $119$ steps closer to the center. So the distance in this case is $538 – 119$.
538 - 119
And so we solved the first part quickly with a mixture of function and handiwork.
Part 2¶
In part two, the spiral has changed significantly. Build the spiral iteratively. Initially, start with 1. Then in the next square of the spiral, put in the integer that is the sum of the adjacent (including diagonal) numbers in the spiral. This spiral is
147 142 133 122 59
304 5 4 2 57
330 10 1 1 54
351 11 23 25 26
362 747 806---> ...
What is the first value that’s larger than 289326?
My plan is to construct this spiral. The central 1 will have coordinates (0,0), and the spiral will be stored in a dictionary whose key is the tuple of the location.
To construct the spiral, we note that the direction of adding goes in the pattern RULLDDRRRUUULLLLDDDD. The order is right, up, left, down: the number of times each direction is repeated goes in the sequence 1,1,2,2,3,3,4,4,….
spiral = {}
spiral[(0,0)] = 1
NEIGHBORS = [(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)]
DIRECTION = [(1,0), (0,1), (-1,0), (0,-1)] #Right Up Left Down
def spiral_until_at_least(n):
spiral = {} # Spiral dictionary
spiral[(0,0)] = 1
x,y = 0,0
steps_in_row = 1 # times spiral extends in same direction
second_direction = False # spiral extends in same direction twice: False if first leg, True if second
nstep = 0 # number of steps in current direction
step_direction = 0 # index of direction in DIRECTION
while True:
dx, dy = DIRECTION[step_direction]
x, y = x + dx, y + dy
total = 0
for neighbor in NEIGHBORS:
nx, ny = neighbor
if (x+nx, y+ny) in spiral:
total += spiral[(x+nx, y+ny)]
print("X: {}, Y:{}, Total:{}".format(x,y,total))
if total > n:
return total
spiral[(x,y)] = total
nstep += 1
if nstep == steps_in_row:
nstep = 0
step_direction = (step_direction + 1)% 4
if second_direction:
second_direction = False
steps_in_row += 1
else:
second_direction = True
spiral_until_at_least(55)
spiral_until_at_least(289326)
Mathematical Outerlude¶
The sequence in the part 2 grows really, really quickly. The sequence starts 1,1,2,4,5,10,11,23…
Many mathematicians (recreational, amateur, and professional alike) often delight in properties of sequences of integers. And sometimes they put them in Sloane’s Online Encyclopedia of Integer Sequences, the OEIS. Miraculously, the sequence from part 2 appears in the OEIS.
It’s OEIS A141481.
But I’ve never seen this sequence before.
I wonder: how quickly does it grow? This is one of the most fundamantal questions one can ask about a sequence.
Clearly it grows quickly — the entries are strictly increasing, and after each corner they roughly double (since the adjacent and diagonal are each there and roughly the same size).
But does this capture most of the growth?
spiral = {}
spiral[(0,0)] = 1
NEIGHBORS = [(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)]
DIRECTION = [(1,0), (0,1), (-1,0), (0,-1)] #Right Up Left Down
CORNERS = [1]
def spiral_until_at_least_print_corners(n):
spiral = {} # Spiral dictionary
spiral[(0,0)] = 1
x,y = 0,0
steps_in_row = 1 # times spiral extends in same direction
second_direction = False # spiral extends in same direction twice: False if first leg, True if second
nstep = 0 # number of steps in current direction
step_direction = 0 # index of direction in DIRECTION
while True:
dx, dy = DIRECTION[step_direction]
x, y = x + dx, y + dy
total = 0
for neighbor in NEIGHBORS:
nx, ny = neighbor
if (x+nx, y+ny) in spiral:
total += spiral[(x+nx, y+ny)]
if total > n:
return total
spiral[(x,y)] = total
nstep += 1
if nstep == steps_in_row:
print("X: {}, Y:{}, Total:{}".format(x,y,total))
CORNERS.append(total)
nstep = 0
step_direction = (step_direction + 1)% 4
if second_direction:
second_direction = False
steps_in_row += 1
else:
second_direction = True
spiral_until_at_least_print_corners(10**15)
In this version, I’ve added in a print statement at each corner, to see the growth. The sequence grows really, really quickly.
CORNERS
for a, b in zip(CORNERS, CORNERS[1:]):
print(b/a)
It appears that the size of the $(n+1)$st corner is roughly $\lambda$ times the size of the $n$th corner, where $\lambda \geq 2.5$. It actually appears like $\lambda$ grows slowly with $n$ (which makes some sense, as the lengths between each corner is increasing with each layer of the spiral). It would be interesting if one could actually show that this growth rate appears to be consistent, and if one could grasp how $\lambda$ behaves with $n$. But I’m not sure how to do that.
Yavor Kirov April 14, 2021 at 3:24 am on Long live opalstack!Thabk you! I was looking for an opinion of a long-term user of Opalstack so your answer was exactly what I needed. 
David Lowry-Duda April 13, 2021 at 9:32 pm on Long live opalstack!Hi Yavor, I'm very happy with Opalstack. After the initial transition, there have been almost no problems. I'll note that for a few months, opalstack's email setup was rocky, but they figured that out. I'd recommend it. They've been pretty responsive to problems, too. You can see what's troubling people now on their community/support forum: https://community.opalstack.com/. I know a somewhat ---
Tomek March 18, 2021 at 5:09 pm on A response to FtYoU’s question on RedditGod bless you David. Great explanation! 
Jan van Delden February 25, 2021 at 5:07 pm on phase_mag_plot: a sage package for plotting complex functionsI took the liberty to download your SageMath module and changed a few options. Since I was not completely clear on the interaction between lightness and color (defined by the argument of the function to be displayed) I decided to weigh these differently. Color, from the colorwheel by 0.8 and lightness by 0.2. I computed the color first and weighed ---
eliot December 23, 2020 at 4:07 pm on Trigonometric and related substitutions in integralsFor Euler substitutions, do you mind explaining the reasoning for the t term in x*sqrt(a) + t. Is there anywhere else I can read up on this? Thanks for this post! 
Nguyen Xuan Son April 11, 2020 at 4:53 pm on AboutHi Could you please share the python code to generating beautiful plots? I plan to use it for my son to get interested in python programming. Son