Programming with LAMBDA - Prime Numbers

LAMBDA makes Excel "Turing Complete." Virtually all programming languages are Turing complete. But can LAMBDA be used like other programming languages? This article approaches Gary Knott FCA BSc ?? primes challenge to Diarmuid Early as a programming challenge. The challenge is to find all 281 primes in a 7x7 matrix .

I solved the challenge then examined Diarmuid Early's solution . His is as elegant as one would expect from a phenomenal, two time Financial Modelling World Cup (FMWC) champion. I love watching his videos and always take away new learnings from them. My solution isn't as concise but it is, in my humble opinion, easier to follow.

My solution is easier to follow because I took the time to break the larger challenge into smaller challenges and isolate them into individual functions that have the potential to be reused as individual functions. I don't mind investing the extra time to make reusable, flexible, maintainable routines. This is at the heart of my 5g initiative .

The larger challenge is to find all 281 primes. The challenge's description tells us the prime numbers can be found going horizontally across the matrix, vertically, and diagonally. It also states they can be found going forwards or backwards. From these statements we can break down the larger challenge into smaller challenges:

1. Get all horizontal lines from the matrix
2. Get all vertical lines
3. Get all diagonal lines
4. Reverse all lines and add them to previous lines.
5. Get all possible numbers from each line
6. Determine which numbers are prime
7. Filter out non-prime numbers from all numbers

Getting horizontal and vertical lines (challenges #1, and #2)

Getting each horizontal line and vertical line is relatively simple using BYROW() and BYCOL() (respectively) with CONCAT() to convert each line from an array of digits to a single number. We can see this in the routine below in the LET() statements named Horizontal and Vertical. Getting the diagonals is a bit more involved and so we will use a function specifically for that purpose: GetDiagsλ().

Getting diagonal lines (challenge #3)

Below is my first solution at getting diagonals. It works but Diarmuid's approach is better. Before I get into that, let's examine my solution for finding diagonals.

I prototyped the formulas using the worksheet shown below. The worksheet along with the entire solution is here: https://www.dropbox.com/scl/fi/wfnsj5c3u1j4urr46snny/GetPrimes.xlsx?rlkey=wvbjoec1jf2jan790lh5xbl8v&dl=1

This prototype was then made into a LAMBDA subroutine shown below.

The essence of this routine is this formula:

INDEX( Array, SEQUENCE( , Len, Row, Direction), SEQUENCE( , Len, Col))

INDEX() syntax is:

INDEX( Array, Row number, Column number)

INDEX() can retrieve more than one number by using arrays for its row and column arguments. For example, to get the first three numbers from the test grid's (named Test) first row, we could use the formula:

INDEX( Test, 1; {1,2,3})

That returns the array 1,2,3. We can use that same array for the row argument:

INDEX( Test, {1,2,3}, {1,2,3})

That returns the numbers from Test's row 1 and column 1, row 2 and column 2, and row 3 and column 3 which is {1, 8, 15}.

To make this work for all diagonals, we need to create the row and column arrays for INDEX() that point the diagonal from top left to bottom right. We then move that diagonal starting from the array's bottom left corner, up column 1 and then across row 1 (See the column in the prototype labeled Up then over along with the Columns and Lengths arrays). The animation below illustrates this over the challeng's 7x7 grid.

We then need to reverse things and point the diagonal from bottom left to top right and move it starting from the arrays upper left corner, down column 1 then across the bottom row as shown below.

The arrays that govern the movement of the diagonal are calculated in the LET() steps named RowPos (Row Positions), ColPos (Column Positions) and Lengths (see code in figure GetDiagsλ above). The actual movement of the diagonal is create in the LET() step named Numbers. This uses the MAP() function to move the diagonal through the array using RowPos, ColPos, and Lengths, collect the diagonal array at each step, convert it to a single number using CONCAT(), and storeit in MAP()s array. We now have a subroutine that can be used over any rectangular matrix to extract diagonal arrays.

Whew!!! That's a lot more involved than I thought it would be. Fortunately, when I checked Diarmuid's solution I saw that his way was much better.

Better Ideas

Before we move on to the next challenge, let us talk about updating functions with better ideas. One of the strengths of creating small functions is they can be easily updated when we find better methods. As long as we keep the inputs and outputs the same we can just change the internal workings of this one function with no impact on the rest of our project. My project would be better incorporating Diarmuid's approach.

The basic premise of Diarmuid's solution is diagonals can be identified by subtracting the difference between row numbers and column numbers. The figure below helps illustrates this.

1. In C2# is a small sample matrix named Array. Array has 4 rows and 3 columns. It is created by the simple formula: =SEQUENCE( 4, 3).
2. In C9# is the formula =SEQUENCE( ,COLUMNS( Array)) which creates a row of 3 column numbers named ColNums. In B10# is the formula: =SEQUENCE( ROWS( Array)) which creates a column of 4 row numbers named RowNums. If we subtract the row of ColNums from the column of RowNums we get the matrix in cell C10#. We have highlighted all the zeros to show the same numbers sit in a diagonal.
3. In J6# is the formula =TOCOL( C10#) which converts the rectangular matrix into 1 column of numbers. In K6# is the formula =TOCOL( Array) which converts the small sample array in C2# to 1 column of numbers. The zeros in J6# are highlighted and show that 1, 5, and 9 from the Array in C2# correspond to the diagonal of zeros in C10#. In L6# is the formula: =GROUPBY(J6#,K6#,CONCAT,,0). That formula groups everything in K6# by J6# and concatenates (joins) the numbers found in J6#. Thus: 1, 5, 9 becomes 159. The 0 at the end of the formula tells GROUPBY() to not include a total line.

If, in step 2, we add RowNums to ColNums, the diagonals go from bottom left to top right.

Below is the much more concise GetDiagsλ() function.

Reversing all lines (challenge #4)

The challenge said we had to find all primes forwards and backwards through the matrix. We have solved for the forward horizontal, vertical, and diagonal lines. Now we must solve going backwards. This turned out to be an easy task and once again, we will leverage INDEX().

I want this routine to work for any array. I don't want to care if it is a row, column, square, or rectangle. So the first thing we must do is remember how many columns the array has. We do this in LET() step Cols (see below). We then convert the array to a row in LET() step RowArray and then determine how many elements are in the array by counting the number of columns in the RowArray in LET() step Elements. With the properties we need in hand, we use INDEX() in LET() step Reverse to traverse backwards through the array using SEQUENCE() to create a column count down. Our last LET() step restores the array to its original shape using WRAPROWS().

With the array reversed, we can process it exactly as we did before and we will have solved processing horizontal, vertical, and diagonal lines backwards.

After reversing the array, we need to repeat GetLinesλ() but this time with the reversed grid.

Getting all possible numbers from each line (challenge #5)

This also proved a relatively simple task. To get all possible sub numbers from a single number can be done using the MID() function and SEQUENCE() in columns and SEQUENCE() in rows as shown below.

As you can see from the animation, this creates all possible sub-numbers and a lot of duplicates so our subroutine uses UNIQUE() to get rid of duplicates, and TOCOL() to place results in a column which is the format we need for the rest of our project.

This works for a single number. We need to apply this to all the numbers created by GetAllLinesλ(). For this we will use the REDUCE() function to go through each line and convert the single number to all the unique sub-numbers (using DeriveNumbersλ) and stacking them into a very long column which we will deduplicate (using UNIQUE) and sort (using SORT).

Determining which numbers are prime (challenge #6)

This gets back to the central problem of this challenge, getting just the prime numbers. We have a list of all possible numbers in our matrix going forwards and backwards. Some of those numbers are prime numbers and some are not. The challenge tells use there are 281 prime numbers.

Just in case you are not familiar with what a prime number is, a prime number is a whole number greater than 1 that cannot be exactly divided by any whole number other than itself and 1. The first few prime numbers are 2, 3, 5, 7, and 11.

We know the first few and we will 'cheat' on 2 & 3 because the algorithm we are about to use doesn't work on those two primes. We also know any even number is divisible by 2 so we will exclude all those. The algorithm we will use divides the number-in-question by all odd numbers from 3 to the number-in-question's square root divided by 2. If any of those have no remainder, the number is NOT prime. Below is the subroutine. It uses the MOD() function to determine if there is a remainder. This leverages an Excel quirk - Excel sees zeros as FALSEs. If the MOD() function returns 0, the number is not prime and Excel translates 0 to FALSE when we AND() the results. Thus, if any denominators return 0, AND() returns FALSE.

Filtering out non-prime numbers from all numbers (challenge #7)

All that is left for us, is to run IsPrimeλ() against all the numbers created by DeriveAllNumbersλ() and use the result array as a filter against all those numbers. Sort the results and we are DONE!

Summary

The purpose of this article was to demonstrate how we can use the same coding best practices from all other programming languages in our LAMBDAs. These best practices urge us to create small, tightly focused functions and use those functions in other functions. As an example, I find it useful to create a child function that does something once, like the IsPrimeλ() function that only works on one number, and call that function from a parent function like ListAllPrimesλ() that cycles through all numbers and calls the child function to do the real work. The parent function can be quite generic because all it is doing is cycling through a list.

Creating small functions that we then assemble into the final routine allows us to focus on a small challenge, structure it, name the steps, solve it, test it, and then use it. On the down side, this approach creates more code because we sometimes duplicate calculations, like determining the number of rows and columns in an array, that we would do only once if we put everything into one monolithic LAMBDA. This also generates more code because I tend to make tiny LET() steps that most LAMBDA gurus would combine into longer LET() steps, and because I use long LET() step names. I encourage my LAMBDA guru friends to do the same.

Is more code worth it? If I can reuse these routines and not have to recreate them from scratch? Then - yeah - absolutely - it's worth it.

Appendix!

One of the best minds in the LAMBDA space is Bo Rydobon ???? . Here is his solution:

=LET( z,A1:G7,r,ROW(z),c,COLUMN(z),f,SORTBY(SORTBY(z,-r),-c),g,LAMBDA(x,DROP(GROUPBY(TOCOL(VSTACK(r+c,r-c-MAX(r,c)),3),TOCOL(VSTACK(x,x),3),CONCAT,,0),,1)),ip,LAMBDA(n,LET(c,{2,3,5,7},d,n/TOCOL(VSTACK(c,SEQUENCE(n^0.5/6,,2)*6+{-1,1}),3),OR(n=c,AND(d-INT(d),n>1)))),b,LAMBDA(b,x,LET(n,ROWS(x),IF(n=1,LET(s,SEQUENCE(LEN(@x)),UNIQUE(TOCOL(MID(x,s,TOROW(s))))),VSTACK(b(b,TAKE(x,n/2)),b(b,DROP(x,n/2)))))),all,SORT(UNIQUE(--b(b,UNIQUE(VSTACK(BYROW(IFNA(VSTACK(z,TRANSPOSE(z),f,TRANSPOSE(f)),""),CONCAT),g(z),g(f)))))),FILTER(all,MAP(all,IP)))        

This looks much more concise but it is very difficult to read. If we 'unpack' this, so we can read it more easily, and use long LET() step names so we can better understand what it is doing, the result would look something like this:

There is a lot to learn from Bo's routines.

Like all of these challenge solutions, Bo's solution is in one routine. Even so, he has created a few sub-functions within this routine. Examples are his LET() steps: GetDiagonals() and IsPrime(). These could easily be defined as separate functions which would make them easier to reuse if needed.