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.
David Lowry-Duda October 17, 2019 at 3:17 pm on Notes from a talk at the Maine-Quebec Number Theory ConferenceThanks Peter! You're right --- and it's a nice reference. 
Peter Humphries October 7, 2019 at 4:03 am on Notes from a talk at the Maine-Quebec Number Theory ConferenceOmega results of this form using this method are presented quite nicely in Chapter 15 of Montgomery and Vaughan; they give applications towards sign changes of the Chebyshev psi function and of partial sums of the Mobius function. 
David Lowry-Duda June 16, 2019 at 1:55 am on Choosing functions and generating figures for “When are there continuous choices for the mean value abscissa?”At first, we chose 2 because it was the other "obvious" point that we hadn't yet specified. We already controlled the values at 0, 1, and 3. But I later realized it doesn't matter what point we choose. What we're really doing is adding one extra degree of freedom and using it to minimize the L2 norm of the derivative ---
PC June 16, 2019 at 1:14 am on Choosing functions and generating figures for “When are there continuous choices for the mean value abscissa?”Why did you choose 2 for the pt in the L2 part? What if you chose 1.5 or something? 
Donna ebert September 27, 2018 at 3:55 pm on AboutI appreciate your taking the time to reply. The version of FreeCell I play online does count taking a card from the tableau (and the Freecells) as a move when adding them to the foundation. I never realized others did not. 
Luis Alberto Torres Cruz September 23, 2018 at 9:50 am on An intuitive introduction to calculusGreat post! Thank you for taking the time to write this. Regarding the example on population growth, you state that if P'(t) = k*P(t), then P(t) = ae^(kt). But wouldn't a more general expression be: P(t) = ae^(kt+C1), where C1 is a constant?