View Single Post
  #1   Report Post  
ExcelBen ExcelBen is offline
Junior Member
 
Posts: 4
Default Lambda, Recursion, and Prime Factors

Hi,

I suspect that many people are playing with the new Lambda function which is now available on the beta version of Excel 365. Simply for fun I wanted to see if I could use a recursive lambda function to return a list of prime factors. To be clear I do not want to fully factorize it, that would be an alternative project, what I am looking for is an exclusive list of factors of n which are prime. So I am looking for PRIMES(12) = {2;3} and PRIMES(63) = {3;7}. I have failed so far, but I have managed to get part of the way. I have managed to get a list of numbers from 1 to n which are prime, with a leading zero (arrggg). My recursive PRIMES function is also deficient in that it requires priming (pun intended) with an addition input of an array containing the number 0 which I manage via a shell.

I hope this is of interest to people, and that we might be able to spark a discussion about excel lambda and recursion. My thanks goes to Scott Craner (who posted this function for joining two arrays on Stack Overflow) that formed the basis for my investigation; =MMULT( (ROW($A$1:INDEX($A:$A,ROWS($A$1:$A$4)+ROWS($B$1:$B $3))) =COLUMN($A$1:INDEX($1:$1,ROWS($A$1:$A$4))))+0, $A$1:$A$4) +MMULT( (ROW($A$1:INDEX($A:$A,ROWS($A$1:$A$4)+ROWS($B$1:$B $3))) =(COLUMN($A$1:INDEX($1:$1,ROWS($B$1:$B$3))))+ROWS( $A$1:$A$4))+0, $B$1:$B$3)

This is a long post, sorry about that.

JOIN. To start off I recreated Scott Craner’s function for joining two arrays. His formula used ROW(…INDEX(... to give a sequence of numbers from 1 to n at various points. This is no longer required since we now have the excellent SEQUENCE function.

I broke the JOIN problem down into several steps so please read through to see how it works (please remember this JOIN is not my original idea, I am working on top of the ideas from Scott’s function).

PUSHZEROS adds some zeros to the front of the array. We need to add a number of zeros equal to the length of the second array.
=LAMBDA(NumberOfZeros,Array,
LET(LengthArray,ROWS(Array),
MMULT((SEQUENCE(NumberOfZeros+LengthArray)=SEQUENC E(1,LengthArray,NumberOfZeros+1))+0,Array)
))

Similarly APPENDZEROS adds zeros to the end of an array, we use it to add zeros to the second array equal to the length of the first array.

APPENDZEROS
=LAMBDA(NumZeros,Arry,
LET(ArryLength,ROWS(Arry),
MMULT((SEQUENCE(ArryLength+NumZeros)=SEQUENCE(1,Ar ryLength))+0,Arry)
))

Then join uses those two functions to join two resulting arrays by addition.
JOIN
=LAMBDA(FirstArray,SecondArray,
LET(LengthFirst,ROWS(FirstArray),LengthSecond,ROWS (SecondArray),
PUSHZEROS(LengthFirst,SecondArray)+APPENDZEROS(Len gthSecond,FirstArray)
))

Next I employed a bit of elementary number theory. TAU function returns the count of the divisors of an integer, for example the divisors of 4 are 1,2 and of course 4, so TAU(4)=3. Since all prime numbers are only divisible by one and themselves then TAU(p) where p is a prime number is always equal to 2. Hence ISPRIME becomes a simple matter of checking whether TAU(n)=2.

ISPRIME
=LAMBDA(n,IF(TAU(n)=2,TRUE,FALSE))

The TAU function (divisor function; the count of the number of divisors) is defined as follows
TAU
=LAMBDA(n,SUM(IF(FACTORS(n)=0,0,1)))

The Tau function uses a FACTORS function which returns the array of factors

FACTORS
=LAMBDA(n,LET(x,SEQUENCE(n),y,x*(0=MOD(n,x)),FILTE R(y,y0)))

So now the primes bit. PRIMES is a shell which adds on the extra parameter

PRIMES
=LAMBDA(n,DONOTUSE(n,{0}))

This is the main recursive function

DONOTUSE
=LAMBDA(n,ns,IF(n=1,SORT(ns),IF(ISPRIME(n)=TRUE,DO NOTUSE(n-1,PUSH(n,ns)),DONOTUSE(n-1,ns))))

Which uses
PUSH
=LAMBDA(n,ns,JOIN(n,ns))

It is all a bit messy. I guess that Lambda is coming in to Excel through the influence of Simon Peyton-Jones at Microsoft Cambridge. Simon is one of the great lights of Haskell. Haskell is a functional programming language which relies on tightly defined nested functions. Essentially your entire program becomes one function. I have found it difficult to nest Lambda functions in Excel. In order to provide this seamlessly, Haskell requires a type definition as part of the definition of every function. I suspect the reason that Excel is not allowing me to nest functions easily is that what I am assuming is an array of integers has been transmuted on the way through one of these functions. It is annoying because you can often call functions from the spreadsheet and pass the resulting array from that cell to another function, but try defining a function nests the first function and it fails. I guess this is why it is on the beta program, and not release. All good fun, and I am sure it will improve over time. Love to hear your thoughts…