Formula Challenge: The most efficient way to generate a Number Spiral (Ulam spiral) ?

Silver Contributor

The goal:

Patrick2788_0-1689690396877.png

Ulam spiral - Wikipedia

 

The trick is creating a function capable of producing the largest matrix of numbers possible (this may rule out the recursive approach).

 

The approach I took:

The approach I took was creating 'frames' and working inward with REDUCE essentially performing repeated addition:

Patrick2788_1-1689691952412.png

REDUCE works its way through an array of odd numbers in descending order (1 is omitted) with 3 different situations:

1. The odd number is the largest so the matrix does not require padding.

2. The odd number is 3, the anomaly, so a 'padded core' is created.

3. The odd number is not the greatest nor 3 so a padded matrix is generated

 

Spiral Lambda:

=LET(
    s, ODD(INT(SQRT(n))),
    arr, UNIQUE(ODD(SEQUENCE(s - 1, , s, -1))),
    arrCore, {5, 4, 3; 6, 1, 2; 7, 8, 9},
    IFERROR(
        REDUCE(
            0,
            arr,
            LAMBDA(a, v,
                LET(
                    TopBottomPadding, EXPAND(0, (s - v) / 2, s, 0),
                    SidePadding, EXPAND(0, v, (s - v) / 2, 0),
                    top, SEQUENCE(, v, (v - 1) ^ 2 + 1, -1),
                    bottom, SEQUENCE(, v, (v - 1) ^ 2 + v, 1),
                    left_frame, EXPAND(SEQUENCE(v - 2, , (v - 1) ^ 2 + 2), , v - 1, 0),
                    right_frame, SEQUENCE(v - 2, , (v - 1) ^ 2 - (v - 1), -1),
                    core_stuffing, EXPAND(0, v, (s - v) / 2, 0),
                    core, VSTACK(
                        TopBottomPadding,
                        HSTACK(core_stuffing, arrCore, core_stuffing),
                        TopBottomPadding
                    ),
                    center, HSTACK(left_frame, right_frame),
                    nopad, VSTACK(top, center, bottom),
                    pad, VSTACK(
                        TopBottomPadding,
                        HSTACK(SidePadding, VSTACK(top, center, bottom), SidePadding),
                        TopBottomPadding
                    ),
                    a + IF(v = s, nopad, IF(v = 3, core, pad))
                )
            )
        ),
        "Please enter a number 17 or greater"
    )
)

The accuracy checks

Patrick2788_2-1689692352199.png

 

 

The highest number I've been able to get away with for is 300,001.  I'm interesting in any suggested improvements or different approaches to this task!

 

 

15 Replies

interesting. I already did something like this for that Fibonacci sequence challenge. I will have to pull out that file and see how I did it then

Ok so I used an approach inside out and here it is modified for this solution:

 

=IF(n > 1,
    LET(turns, 2 * INT(SQRT(n)) - 1,
        s, SEQUENCE(turns),
        all, REDUCE({1, 2},s,LAMBDA(p, q,
                CHOOSE(
                    MOD(q, 4) + 1,
                    HSTACK(p, SEQUENCE(ROWS(p), 1, MAX(p) + ROWS(p) + 1, -1)),
                    VSTACK(SEQUENCE(1, COLUMNS(p), COLUMNS(p) + MAX(p), -1), p),
                    HSTACK(SEQUENCE(ROWS(p), 1, MAX(p) + 1), p),
                    VSTACK(p, SEQUENCE(1, COLUMNS(p), MAX(p) + 1))
                )
            )
        ),
        final, IF(all > n, "", all),
        final
    ),
    "Parameter 'n' must be >=1"
)

 

it is far from optimized as excel has to find the MAX each loop when I could potentially add some parameters to the accumulator to pass the max and # rows/columns and even the next position

regardless it works relatively well and can do significant numbers (just how long you want to wait).

It's close. It looks like 10 is being skipped. I played with adjusting the 2nd VSTACK within the CHOOSE to remove the +1, this adds 10 back to the matrix but then causes a duplication. It's a good start!

@Patrick2788 dang I thought I fixed that.  the problem was on the first hstack.  When you add ROWS() you don't need the extra +1.  i fixed it on the vstack that uses COLUMNS() and thought I fixed it on that hstack but either forgot or lost the change when I did something else.  Check the attached

@mtarler 

It looks good! I put your function through the accuracy checks (elements, number of elements, max element - did not include the check on the top-left element because the wrapping is done differently) and it passes every time.

 

I put both our functions through some stress testing.

 

The record for seems to be about 1,250,000 for each.  The functions may be capable of handling a bit more but it's at a point where the calculation time takes a few minutes.

 

It's funny how this function bonked on 1.25 million but your Spiral did not:

=COUNT(UNIQUE(TOCOL(D1#)))

Patrick2788_0-1689782051176.png

 

 

@Patrick2788  As I mentioned it wasn't optimized much at all.  So here is one slightly more optimized (almost 1/2 the time).  Basically I halfed the loops so I do 2 sides each time instead of only 1:

uSpiral2 = lambda(n, IF(n >4,
    LET(
        turns, INT(SQRT(n - 1)) - 1,
        s, SEQUENCE(turns,,2),
        all, REDUCE(
            {4,3; 1, 2},
            s,
            LAMBDA(p, q,
                let(mx, q*q,
                if(
                    iseven(q),
                    VSTACK(hstack(SEQUENCE(q, 1, mx + 1),p), SEQUENCE(1, q+1, q + mx+1)),
                    VSTACK(SEQUENCE(1, q+1, mx + 2*q + 1, -1), hstack(p, SEQUENCE(q,1, mx + q,-1)))
                ))
            )
        ),
        final, IF(all > n, "", all),
        final
    ),
    "Parameter 'n' must be >4"
));

 

That is much more efficient. Maybe the only way to speed it up even more would be remove the stacking functions and go purely on EXPAND, if that's even possible (EXPAND would probably need recursion which would defeat the purpose).

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))))

 @Patrick2788 

@Patrick2788@mtarler 

 

It took about four 3-4 minutes to finish, but I was able to reach Sheets' 10 million cell threshhold using that formula with each side having length 3162. Overall N = 9,998,244

@Patrick2788 Interesting challenge. I took a slightly different approach, starting from the center of the spiral and working my way outwards, offsetting the row or column number by either 1 or -1 at each step. I used TOCOL / IF / SEQUENCE as the primary method of array manipulation, then SORTBY to sort the numeric sequence by row and column number, and WRAPROWS to output the final results. Due to the row limitations of the SEQUENCE function, the maximum output size is 1023 rows by 1023 columns (1,046,529 numbers), but it only takes 3 seconds to process.

 

The complete definition of the LAMBDA function is:

 

ULAMSPIRAL:
=LAMBDA(rows,
    LET(
        n, rows + ISEVEN(rows),
        adj, DROP(TOCOL(IF({1,1}, SEQUENCE(n))), -1),
        row, DROP(TOCOL(IF(SEQUENCE(n), {0,1})), -1),
        off, DROP(DROP(TOCOL(IF(SEQUENCE(n), {1,1,-1,-1})), 1), -2),
        rId, DROP(TOCOL(IFS(adj >= SEQUENCE(, MAX(adj)), SEQUENCE(ROWS(adj))), 2), -1),
        r, INDEX(row, rId),
        k, INDEX(off, rId),
        s, ROUNDUP(n/2, 0),
        POS, LAMBDA(int,arr, VSTACK(int, SCAN(int, arr, LAMBDA(a,v, a+v)))),
        spiral, WRAPROWS(SORTBY(SEQUENCE(n^2), POS(s, r*k), 1, POS(s, NOT(r)*k), 1), n),
        DROP(spiral, rows-n, n-rows)
    )
)

 

It's set up a little different, in that you enter the total number of rows to be generated (n=rows^2). Entering an odd number of rows will generate a perfect spiral, whereas an even number of rows will be truncated (the last row and first column will be dropped)...

@Patrick2788 Sorry, I wasn't happy with the row limitations of my first try, so I came up with another version using the MAKEARRAY function:

 

ULAMSPIRAL:
=LAMBDA(rows,
    LET(
        n, rows + ISEVEN(rows),
        s, ROUNDUP(n / 2, 0),
        spiral, MAKEARRAY(n, n, LAMBDA(r,c, LET(
            off_r, r - s,
            off_c, c - s,
            lvl, MAX(ABS(off_r), ABS(off_c)) + 1,
            lvl_n, lvl * 2 - 1,
            lvl_r, lvl + off_r,
            lvl_c, lvl + off_c,
            IFS(
                lvl_r = lvl_n, lvl_n ^ 2 - lvl_n + lvl_c,
                lvl_c = 1, lvl_n ^ 2 - lvl_n * 2 + lvl_r + 1,
                lvl_r = 1, lvl_n ^ 2 - lvl_n * 2 - lvl_c + 3,
                TRUE, lvl_n ^ 2 - lvl_n * 3 - lvl_r + 4)))),
        IF(ISODD(rows), spiral, DROP(spiral, -1, 1))
    )
)

 

Basically, the value of each cell is determined by its row and column number in relation to the center of the spiral. Surprisingly, this version was more efficient that my first, returning a 1023x1023 spiral in only 2 seconds. The maximum size I was able to achieve was a 7327x7327 spiral (53,684,929 numbers) in 2 minutes and 7 seconds. Attempting 7328 rows and above returned the "Excel ran out of resources" error message.

Very impressive. Building the list in one pass based on the four diagonal quadrants is the way to go. Did you happen to make any comparisons with the formula that I submitted? Sheets doesn't allow more than 10 million cells, plus I think making comparisons using the same platform would be nice.

@djclements 

@ShayCapehart When I first tried your formula, it didn't work in Excel as written. I just tried it again and realized the INDEX function was not needed. After removing that, it worked like a charm!

 

It's approximately twice as fast as my MAKEARRAY version, outputting a 1023x1023 spiral in 1 second, and a 7327x7327 spiral in 1 minute and 13 seconds. Again, 7328 rows and above returned the "Excel ran out of resources" error (I guess 7328^2 is too large).

 

The only little quirk I noticed was that the spiral order is different between odd and even numbers... with odd numbers, the first move from center is to the left, then down (as opposed to the right, then up). As a result, the final number is located in the top-left corner of the spiral, rather than the bottom-right. No big deal... it takes first prize in speed! :)

Oh that makes sense. I first started down this project building a reverse number spiral, A Pyramid Ascent, and I always started with 1 in the upper left corner. When I came across this post, I thought I could easily convert it into an Ulam Spiral by just adding n^2 at the beginning and start my ascent at 0 instead. But you're correct, the Ulam Spiral always moves in the same direction from where it starts, not where it ends.

I tried your formula in Sheets. Not only does Sheets not have the DROP formula yet, but even without that part, Sheets reaches it's calculation limit at 178 rows. That's the whole reason as to why I started looking for a direct one-pass approach. Thanks for running it.

@ShayCapehart 


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.

 

@djclements 

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.

@Patrick2788 

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:

  1. Get rid of MIN, since it's generating all four values at each coordinate.
  2. 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:

2024-03-25_11h02_00.jpg

 

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.