Forum Discussion
Formula Challenge: The most efficient way to generate a Number Spiral (Ulam spiral) ?
I found it best to avoid any iteration in order to not reach the calculation limit so quickly. This formula can return an 1120x1120 in less than 30 seconds. I must admit, I'm using Google Sheets, but I believe there's no compatibility issues with this formula. I'm not really sure what it's limit is in Sheets or Excel yet.
=let(n,1120,i,sequence(n),j,sequence(1,n),
index(n^2-
if(i<j+1,
if(j<=n-i+1,
4*n*i-4*i^2+7*i-4*n+j-4,
4*n*j-4*j^2+3*j+i-2*n-2),
if(j<n-i+1,
4*n*j-4*j^2+j-i,
4*n*i-4*i^2-2*n-j+5*i-2))))
This is terrific! May I ask how much time you've invested in studying the Ulam spiral?
Any time I post one of these out of the box problem-solving discussions I don't expect a lot of replies (It gives me hope that there may be an audience for the fractals Lambda I made months ago.).
I hadn't looked at this task since I posted it in July but would brainstorm alternatives solutions every so often.
For example:
-Create a sparse array and have SCAN finish the matrix by filling in the missing values
-Create an array of R/C coordinates in relation to the origin (1). There's a pattern to the coordinates but it's a slog.
-Recursive wrapping/flattening. I think this is theoretically possible but it's not terribly efficient.
It's funny I was messing with MAKEARRAY on/off this morning but being interrupted too much to finish it. I like this solution. MAKEARRAY gets a bad rap for being 'slow' but it's not a bad option when a matrix needs to be created where a target array doesn't exist. Also, MAKEARRAY doesn't need to stack.
Thanks for responding. About a month ago, someone needed some help creating the reverse spiral, or Pyramid Ascent as I like to call it. As you can imagine, that quickly turned into seeing who could come up with the shortest/fastest/most robust formula. Sheets kept reaching a calculation limit, and I knew that was highly affected by the use of LAMBDA helper functions.
After an all-nighter, I came up with this direct approach.
=lambda(n, makearray(n,n,lambda(i,j, let(a,min(n-i,j-1,i-1,n-j), b,if(i>j,4*n-j-i-6*a,j+i-2*a), 4*a*(n-a)+b-1))))It was still hitting the calc limit at 219 rows, so last week I was determined to:
- Get rid of MIN, since it's generating all four values at each coordinate.
- Remove the final LAMBDA helper function, MAKEARRAY.
That led to a formula similar to the one I subitted here. I thought that I could easily convert the Pyramid Ascent into the Ulam Spiral by simply adding n^1-1, but I now recognize that the Ulam Spiral is set by the spiral direction starting at 1 vs the Pyramid Ascent, which always begins with 1 in the upper left corner. I'm currently working on that fix.
As for any future improvements to efficiency, here's my thought. If the final matrix is generated row by row, would it be more efficient if at each row, stack together three arrays of numbers, which would avoid a bunch of conditional tests to determine which quadrant each coordinates is in. I've tried visualizing this below:
I've made a Named Function called SPIRAL that outputs the spiral (fix still pending from above) given the side length and type of spiral. This spreadsheet also includes some nice extras to visualize the prime numbers and demonstrate that it may not be the primes that have a pattern, but rather the non-primes. And when you remove a pattern from a canvas, what remains can appear to be a pattern.
