Lambda, Recursion, and Prime Factors

[ExcelBen]

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)=SEQUENCE(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,ArryLength))+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(LengthSecond,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)),FILTER(y,y>0)))

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,DONOTUSE(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…




--
ExcelBen

[ExcelBen]

Update.
I have a solution and a remaining problem.

INTERSECTION
=LAMBDA(as,bs,LET(x,XMATCH(as,bs,0),INDEX(bs,FILTER(x,ISNA(x)=FALSE))))

returns the intersection between two arrays.

So PRIMES becomes
=LAMBDA(n,INTERSECTION(FACTORS(n),DONOTUSE(n,{0})))

The remaining issue is that the largest integer this can handle is 334.
Very odd.




--
ExcelBen

[ExcelBen]

Two Lambda functions, one wrapper called PRIMESNEW and one recursive
called TEST

TEST

=LAMBDA(n,a,ps,IF(a>n,ps,IF(SUM((MOD(a,ps)=0)*1)=0,TEST(n,a+1,APPEND(a,ps)),TEST(n,a+1,ps))))

PRIMESNEW

=LAMBDA(n,INTERSECTION(FACTORS(n),TEST(n,2,{2})))

It has the great advantage of simplicity. It is limited at 255. Still
investigating why




--
ExcelBen