Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1   Report Post  
Old January 23rd 21, 06:34 PM
Junior Member
 
First recorded activity by ExcelBanter: Jan 2021
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…

  #2   Report Post  
Old January 24th 21, 10:19 AM
Junior Member
 
First recorded activity by ExcelBanter: Jan 2021
Posts: 4
Default

Update.
I have a solution and a remaining problem.

INTERSECTION
=LAMBDA(as,bs,LET(x,XMATCH(as,bs,0),INDEX(bs,FILTE R(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.
  #3   Report Post  
Old January 24th 21, 04:25 PM
Junior Member
 
First recorded activity by ExcelBanter: Jan 2021
Posts: 4
Default New much simpler solution

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

TEST

=LAMBDA(n,a,ps,IF(an,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

Last edited by ExcelBen : January 24th 21 at 04:28 PM


Reply
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Preventing Recursion? egun Excel Programming 2 January 22nd 09 10:37 PM
Recursion in VBA macros? Peter Chatterton[_4_] Excel Programming 5 November 27th 06 07:27 PM
how do I find prime factors of a number Jeff Excel Worksheet Functions 16 November 30th 05 11:41 AM
Abort recursion Mike NG Excel Programming 2 June 29th 05 09:08 AM
Recursion Mike NG Excel Programming 4 June 2nd 05 11:07 PM


All times are GMT +1. The time now is 09:58 PM.

Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright ©2004-2021 ExcelBanter.
The comments are property of their posters.
 

About Us

"It's about Microsoft Excel"

 

Copyright © 2017