Spiral Challenge

Megan Schmidt is obsessed with spirals. Her obsession got me hooked — for hours — on a math problem. I thought it would take maybe an hour or two, but I’m still at it and I’ve probably been working four or five hours.

I’ve been having so much fun with it.

Here’s the problem. Look at the spiral below…

obsessed.png

We see that 1 is located at (0,0).
We see that 2 is located at (0,1).
We see that 8 is located at (-1,0).

If we continue this spiral in this manner, can you come up with a formula for the coordinates of the kth number?

So what I want to know is if we consider the number 2016, can we come up with a way to precisely define where it is? What about 820526487?

One easy way around this is to write a computer program that just brute forces our way through it. So here’s the constraint: I want a closed formula for the x-coordinate and y-coordinate. That means no recursion! No if/then statements! Just an equation that relies on k only.

You know one of the most frustrating things? Going down a path and feeling good about it, even though it is pretty complicated. And then having a new insight on how to attack the problem (which *just* happened to me now as I typed up the problem and look at the image I created for this post) [1]. And realizing that approach might yield it’s secrets so much easier!

In any case, I thought I’d share the problem because it’s given me so much enjoyment thus far. If you do get obsessed and solve it, please feel free to put your answer in the comments. I have a feeling there are a variety of valid solutions which look very different but yield the same answer.

[1] What this reminds me is how slight changes in representations can lead to new insights! Before I was using this image that Megan sent me:

megan

UPDATE!: I solved it!

If you want to see that I did solve it, check out this Geogebra sheet. It won’t give away how I solved it (unless you download it, look at how I defined each cell, and then reverse engineered it).

https://www.geogebra.org/m/cXhwYh3P

So yeah… 2016 is at (-22,13), and 820526487 is at (-14322, 4784).

I am so proud of myself! I came up with a closed form solution!!!

I am going to put a “jump” below here, and then show what my solution is, and write a little about it. So only read below the jump (meaning: after this) if you want some spoilers.

NOTE: There is a small error in the solution below… I defined M=floor(sqrt(k)-0.001). It turns out that almost always works until you hit huge k values near perfect squares (I know, I know). However the real solution has M=floor(sqrt(k-1)). That fixes all the problems, I think. You can read below about the solution, and then how I caught my error, and how I fixed it. 

Okay, so this was an insane problem. To make the formula for the coordinates where any k value exists simpler, I defined a new variable M [for Megan, who nerdsniped me with this problem!] which was equal to: M=floor(sqrt(k)-0.001).

ugly.png

I know, I know, it’s so ugly! And what I think is so insane about this is that now I see so much simplicity and structure in the equations. It doesn’t look like gobblygood to me. But looking at this as an outsider who maybe didn’t attack the problem, I wouldn’t know how in the world someone would come up with thisIt feels impossible!!!

I am going to try to give a little sense to the structure of this solution, without going into all the ugly details about how it came about. (I would actually love to show the process, but it would take a mini-novella to trace my thinking. And I have a terrible memory. Though when I ran out of paper at the coffeeshop I was working at, I did start working on a googledoc, so some of my thinking is archived.)

Let’s look at the pieces of the solution structurally:

spiralsoln2.png

There are three parts to the solution: the underlined bit, the swirl bit, and the zigzag bit.

Let’s look at the underlined bit. What this part of the solution does is find us a coordinate near the right coordinate. To see this concretely:

yellowsquares.png

For any k value, the underlined part will yield one of the yellow squares in that diagonal.

So for numbers like k=51, 55, 62 (the grey numbers), the underline bits put us at the coordinates for 57.
And for numbers like k=101, 114, 120 (the purple numbers), the underline bit puts us at 111.

Let’s say k=106. If we only had the underlined part of the solution, that would yield the coordinates (-5,-5), which is where 111 lives. If we say k=113, and we only had the underlined part of the solution, that would also yield the coordinates (-5,-5), which is where 111.

So the underlined part of the solution gets us close to the answer, but not quite fully there.

Once we’re at a yellow square, to get to the real coordinates, we need to move up/down or left/right from that yellow square. So for example, if I wanted 106, that would be me moving right 5 units from the 111 square. Or if I wanted 113, that would be me moving up 2 units from the 111 square. Or if I wanted 61, that would be me moving down 4 units from the 57 square. Or if I wanted 56, that would be me moving left 1 unit from the 57 square.

So all we need to do is figure out a way to move us up/down/left/right appropriately.

What the swirl bit of the equation does is precisely that. It calculates how far up/down/left/right I need to move (where up and right are positive values and down and left are negative values…).

However there’s a problem! How do you alter the equation so you are only moving up and not also right? You don’t want to move both directions from the yellow square — only one of them! (So, look at the 106 or 113… we only moved in one direction from 111, not both.) If we only had the underlined part and the swirl part of the equation (but not the zigzag part of the equation), we would always start at a yellow square near our true answer, but then we would move both horizontally and vertically. That’s a problem. To get to any of our values, we only need to move horizontally or vertically.

Thus, the stopgap for that is in the zigzag part of the equation. That part of the equation looks super complicated. But in actually it’s not. Let’s look at a similar equation (which is where I came up with it):

onoffswitch.png

That’s basically what the zigzag piece means in the x-coordinate equation. It’s an on/off switch. It yields a value of 1 when we want to move in the x-direction, and it yields a value of 0 when we don’t. Because the swirl and zigzag piece are multiplied together, we have two options…
If the x-zigzag piece is “on”, we are saying: start at the yellow square and move horizontally the number of units that the swirl piece of the equation says to move!
If the x-zigzag piece is “off”, we are saying: start at the yellow square and do not move horizontally.

Similarly for the y-coordinate equation, we have the exact opposite zigzag piece…

offonswitch.png

What I mean by opposite is that if the x-zigzag piece yields 1, the y-zigzag piece yields 0 (and if the x-zigzag piece yields 0, the y-zigzag piece yields 1).

So similarly:
If the y-zigzag piece is “on”, we are saying: start at the yellow square and move vertically the number of units that the swirl piece of the equation says to move!
If the y-zigzag piece is “off”, we are saying: start at the yellow square and do not move vertically.

And since the two zigzag pieces are “opposite,” what we only ever move horizontally or vertically, but never both.

An example.

Let’s look at a specific example. Let’s consider k=113.

yellowsquares

 

Evaluating k=113, we get the following for the x- and y-coordinates:

x=(-5)+(-2)(0)
y=(-5)+(2)(1)

Where the red number is the value of the underlined part, the green value is the value of the is swirl part, the blue value is value of the zigzag part.

Notice the underlined part put us at the coordinates (-5,-5) (the yellow square with 111). That fixed us near the true value of the coordinate. Then the swirl part said we need to move either up/down/left/right two units. And the blue part says: actually, we only want to move vertically, so ignore the horizontal motion.

Let’s do it one more time with a different k value. Let k=56, we get the following for the x- and y-coordinates:

x=(4)+(-1)(1)
y=(4)+(1)(0)

Where the red number is the value of the underlined part, the green value is the value of the is swirl part, the blue value is value of the zigzag part.

Notice the underlined part put us at the coordinates (4,4) (the yellow square with 57). That fixed us near the true value of the coordinate. Then the swirl part said we need to move either up/down/left/right one unit. And the blue part says: actually, we only want to move horizontally, so ignore the vertical motion.

Although the original equation looks super complicated, it may seem less complicated now! There’s some thinking behind the structure!

This being said, I am absolutely sure there are myriad equations which will work, and mine is probably one of the uglier ones. I started down a path that got a bit circuitous, and I have a feeling that if I were to try this again in an attempt to come up with a simpler answer, I would be able to do so!

Update 2: Of course there’s an error.

So when verifying my work on geogebra, I was hesitant about the fact that in order for me to make things work out when writing my solution, I had to shift things around a bit. So I had that weird thing called M which was floor(sqrt(k)-0.01). I had to subtract that 0.01 because I was having issues with perfect squares, but nothing else.

Turns out that was a bad idea… I started thinking about if that could mess things up for high values of k which happen to be near perfect squares (which, visually, means at the corners where you switch from going one direction to another as you walk along the spiral). And this is what I found… it does mess things up. Check it out…

argh.png

These two red dots represent 20166 and 20738. You can see they are just a bit away from the location they should actually be at!

So I changed that 0.01 in my equation for M, so M=floor(sqrt(k)-0.000001), and everything turned out well.

argh2.png

It’s a little annoying, because I wanted a perfect closed for solution.

Wait. WAIT. I have a fix I think… I am going to define M=floor(sqrt(k-1)). The whole idea of having M=floor(sqrt(k)-0.001) is that for values of k which were perfect squares, I wanted M to be one less than the number being squared… so I subtracted out a little piece to make the floor function round it down. But then problems occurred.

Instead of arbitrarily subtracting 0.001 (which causes trouble), I can get the same shift by simply taking the square root of the previous integer (so instead of the square root of k, I take the square root of k-1). This does the same thing… I think…

Let me check… AND… IT WORKS! And it looks slightly more elegant!

The fix works perfectly (I hope). Here it is in final form (I hope):

realsolution.png

Advertisements

9 comments

  1. You can come up with a formula fairly easily, though you’ll have to abuse the modulus, floor, and square root functions to replace the use of loops and branching.

    1. Haha, you mean YOU can come up with a formula easily! I’m still not there yet! I have been using the floor and square root functions, but I haven’t allowed myself modulus functions. I think I can get it without that, maybe!

  2. Here’s something interesting – the context of this problem (although spiraling counterclockwise and with step 0 at the origin instead of step 1) is the 1990 NYSML power question. In those years, the NYSML problems were written by Larry Zimmerman and Gil Kessler.

  3. This problem is REALLY hard! I started working on it today. I’m just working on a function for the x-coordinate for now (if you can figure out a function for x, it shouldn’t be too hard to figure out a function for y). Of course, there are some clear patterns. You have periods where:

    x stays the same
    followed by x increasing by 1
    followed by x staying the same
    followed by x decreasing by 1

    One crazy thought I had was that since every fourth period has x increasing by 1 and every fourth period (two after periods where the x-coordinate increases by 1) decreases by 1, the pattern could fit nicely with powers of i for the rate of change…IF you could find a way to make the rate of change be zero when a power of i leaves you with an imaginary number.

    Another thought I had involved using the greatest integer function (probably what you guys are calling “floor”) with a transformed sine function. For example, using f(x) = int( sin(x) + 0.4 ) gives you (successive domains of) results of 1, 0, -1, 0, 1, 0, -1, 0, 1,… which if they could be managed might be able to help us…

    Not sure if any of this leads us anywhere, but this will be on my mind again tomorrow during day #2 of a teacher conference I’m attending.

    Thanks for the great problem!

  4. Sam,

    I always enjoy reading your very interesting and informative blog. Thanks a lot for this problem in particular. I enjoyed working on it for quite a while and am very excited to have found a solution and wanted to share it with you. I don’t mean to be some sort of crank who offers unsolicited solutions to people who aren’t interested, so please feel free to remove this comment if you like. I am just very excited to have solved the problem, as you can imagine, and wanted to share it with you since you provided me with this great challenge in the first place. Thanks again!

    Given a positive integer n,
    define k = floor((sqrt(n) – 1)/2),
    define n0 = (2*k+1)^2,
    define m = n – n0,
    define p = floor(m/(2*(k+1))).

    Then the coordinates of the number n are given by:
    (1/6)*p*(1-p)*(2-p)*([-(k+1); -(k+1)] + (m – 6*(k+1))*[0;1]) – …
    (1/2)*p*(1-p)*(3-p)*([k+1; -(k+1)] + (m – 4*(k+1))*[-1;0]) + …
    (1/2)*p*(2-p)*(3-p)*([k+1; k+1] + (m – 2*(k+1))*[0;-1]) + …
    (1/6)*(1-p)*(2-p)*(3-p)*([-k;k] + (1 – kroneckerDelta(sym(m)))*[m-1;1])

    The above is the solution as one would type it in MATLAB. The coordinates are given as an ordered pair, i.e. a vector in MATLAB, denoted by [x; y]. The function kroneckerDelta(m) is defined to be 1 if m = 0 and 0 otherwise. Also, please note that, for whatever reason, I called the given integer n, whereas you refer to this value as k.

    I have a handwritten version (with an explanation) that is much easier to read. I had originally wanted to scan it and email it as a PDF, but I didn’t know where to send it. So I just tried to type the solution into the comments instead.

    Thanks again, and please keep up the fantastic blogging!

    1. Ooooh awesome!!! Sorry for the delay in responding — life has gotten the better of me. But it’s clear you had the same AMAZING FEELING when you finished it, and you wanted to share your insights! I’m so glad you did. I would never remove this comment! If you did want to email me your pdf solution, I can post it on this blogpost… My email is samjshah at gmail.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s