Fun Uncle with Prime Number Lookup

[RaviWildcat]

My young nephew is learning about factoring. The principle is that any non - prime number can be broken down into a series of prime numbers. For example, 9 = 3 x 3. My given number (9) can be broken down to a product of prime numbers (3 x 3). 12, can be broken into 2x2x3 and so on.

I'm looking at it like this: (Let's say my given number is in cell d7

Given number
40	=IFERROR(IF(MOD(D7,2)=0,D7/2,IF((MOD(D7,3)=0),D7/3,IF((MOD(D7,5)=0),D7/5,".."))),"..")	=IFERROR(IF(MOD(E7,2)=0,E7/2,IF((MOD(E7,3)=0),E7/3,"..")),"..")
40	20	10	5

you see how I'm first checking mods with prime numbers (2,3,5) - first checking does mod 2 = 0 , then divideby 2, else if mod 3 = 0 then divide by 3 else if mod 5 = 0 then divide by 5 - if none of these things are true then enter ".." then repeat with the result until I get to ..


Any thoughts about referencing a lookup table? I'm thinking about populating a lookup table with a prime number in each column - first the formula checks mod in row 1 of the table (which is 2) then it checks mod in row 2 of the table (which is the next prime number etc.) etc.

That would save me from having a monster if formula!

(There are other approaches that are alternatively cleverer / more cumbersome. I suppose I could write a recursive function in VBA too though the real fun comes from formulas

Any thoughts?

 

[RaviWildcat]

Dang - every so often I start think I'm the excel master and then I come on here and get humbled by y'all! These solutions are so cool! Thank you!

 

[saboh12617]

Hello all,

I am not sure on how to implement this idea on the formula given by Eric:

We know that the biggest divisor of a non-prime k is sqrt(k). But i noticed Eric's formula stops at k-1 in the sequences, making a huge matrice for the biggest numbers. By replacing the formula in E2 by

=LET(ub, C6,
p, SEQUENCE(ROUNDUP(SQRT(ub),0)-1,,2),
f, SEQUENCE(,ROUNDUP(SQRT(ub),0)-1,2),
nd, MMULT(--(MOD(p/f, 1)=0), p^0),
FILTER(p, nd=1))

We get the actual potential divisors of the number. But then i am stuck as I do not get how to adapt the other formula for the factorization. Doing like so should allow computations up to 99999 i believe.

 

[saboh12617]

Hello,

Please ignore my previous message, which is very wrong and incomplete.

I found the alternative solution below working for bigger numbers (i tested it to numbers up to 99999).

It is very ugly at the moment but i will refractor it with time.
Note : it goes up to power 30 for a prime. It can be tweaked.

=LET(
func, LAMBDA(x, LET(nb, x,
isPrime, LAMBDA(n,  OR(n<=3,  AND(MOD(n,  SEQUENCE(ROUNDUP(SQRT(n), 0), , 2))<>0))),
factors, REDUCE(, SEQUENCE(ROUNDUP(nb/2, 0), , 2), LAMBDA(acc, v,
IF(MOD(nb,  v)=0, VSTACK(acc, v), acc))),
factP, REDUCE(, factors, LAMBDA(acc, v, IF(isPrime(v), VSTACK(acc, v), acc))),
powers, MAP(factP, LAMBDA(k, MAX(SEQUENCE(30)*(MOD(nb, k^SEQUENCE(30))=0)))),
IF(isPrime(x), x, TEXTJOIN("", TRUE, LET(nbs, FILTER(factP, powers>0), pws, TAKE(powers, -ROWS(nbs)),
MAKEARRAY(1, 4*ROWS(nbs)-1, LAMBDA(r, c, SWITCH(MOD(c, 4),
1, INDEX(nbs, ROUNDDOWN(c/4, 0)+1),
2, "^",
3, INDEX(pws, ROUNDDOWN(c/4, 0)+1),
0, "*")))))))),
func(A2))

 

[djclements]

I had some fun with this one.

Create the following 2 lambda functions in Name Manager...

ISPRIME

=LAMBDA(number,IF(OR(number<2,number<>INT(number),AND(number>2,ISEVEN(number))),FALSE,OR(number=2,AND(MOD(number,SEQUENCE(ROUNDUP(SQRT(number),0)-1,,2))))))

PF

=LAMBDA(number,[opt],[p],[k],IF(OR(number<2,number<>INT(number)),NA(),IF(ISPRIME(number),IF(ISOMITTED(k),"prime",LET(k,k&" x "&number,CHOOSE(opt+1,k,TEXTJOIN(" = ",,k,PRODUCT(--TEXTSPLIT(k,"x"))),LET(v,--TEXTSPLIT(k,,"x"),TEXTJOIN(" x ",,BYROW(GROUPBY(v,v,ROWS,0,0),LAMBDA(r,TEXTJOIN("^",,r))))),LET(v,--TEXTSPLIT(k,, "x"),TEXTJOIN(" = ",,TEXTJOIN(" x ",,BYROW(GROUPBY(v,v,ROWS,0,0),LAMBDA(r,TEXTJOIN("^",,r)))),PRODUCT(v)))))),LET(p,IF(ISOMITTED(p),LET(a,SEQUENCE(MIN(number,100)),FILTER(a,MAP(a,ISPRIME))),FILTER(p,p<=number)),v,@FILTER(p,NOT(MOD(number,p))),IF(ISNUMBER(v),PF(number/v,opt,p,TEXTJOIN(" x ",1,k,v)),LET(a,SEQUENCE(CEILING.MATH(MAX(p),100)*2),PF(number,opt,FILTER(a,MAP(a,ISPRIME)),k)))))))

Notes:

• change "prime" to number in the PF formula definition, if desired
• do not use the optional [p] and [k] arguments

Optional [opt] argument:

• 0 - prime factors (default)
• 1 - prime factors with total
• 2 - grouped
• 3 - grouped with total

Examples:

=PF(999999,1)

-or-

=MAP(A2:A11,PF)

 

[saboh12617]

Very interesting proposition @djclements,
Here is mine, refactored
For a "one line result"

=LET(
  DecompFact, LAMBDA(k, 
    LET(
      isPrime, LAMBDA(n, OR(n<=3, AND(MOD(n, SEQUENCE(ROUNDUP(SQRT(n), 0), , 2))<>0))), 
      divisors, DROP(REDUCE(1, SEQUENCE(ROUNDUP(k/2, 0), , 2), LAMBDA(acc, v, IF(MOD(k, v)=0, VSTACK(acc, v), acc))), 1), 
      primeFact, REDUCE(, divisors, LAMBDA(acc, v, IF(isPrime(v), VSTACK(acc, v), acc))), 
      pMax, ROUNDUP(LN(k)/LN(INDEX(primeFact, 1)), 0), 
      powers, MAP(primeFact, LAMBDA(d, MAX(SEQUENCE(pMax)*(MOD(k, d^SEQUENCE(pMax))=0)))), 
      results, "-----------------------------------------------------------",
      IF(isPrime(k), k, TEXTJOIN(" * ", TRUE, BYROW(HSTACK(primeFact, powers), LAMBDA(r, TEXTJOIN("^", TRUE, r)))))
    )
  ), DecompFact(A1)
)

For a mini-table

=LET(
  DecompFact, LAMBDA(k, 
    LET(
      isPrime, LAMBDA(n, OR(n<=3, AND(MOD(n, SEQUENCE(ROUNDUP(SQRT(n), 0), , 2))<>0))), 
      divisors, DROP(REDUCE(1, SEQUENCE(ROUNDUP(k/2, 0), , 2), LAMBDA(acc, v, IF(MOD(k, v)=0, VSTACK(acc, v), acc))), 1), 
      primeFact, REDUCE(, divisors, LAMBDA(acc, v, IF(isPrime(v), VSTACK(acc, v), acc))), 
      pMax, ROUNDUP(LN(k)/LN(INDEX(primeFact, 1)), 0), 
      powers, MAP(primeFact, LAMBDA(d, MAX(SEQUENCE(pMax)*(MOD(k, d^SEQUENCE(pMax))=0)))), 
      resultats, "-----------------------------------------------------------",
      VSTACK(HSTACK("divisor", "power"), IF(isPrime(k), HSTACK(k, 1), HSTACK(primeFact, powers)))
    )
  ), DecompFact(A1)
)

 

[saboh12617]

Pasted the old formulas... This LN part is not working. Change pMax to

pMax,25,

 

[djclements]

A slight variation of my previous PF formula, with the totals on the left (instead of the right) for easier readability...

ISPRIME

=LAMBDA(number,IF(OR(number<2,number<>INT(number),AND(number>2,ISEVEN(number))),FALSE,OR(number=2,AND(MOD(number,SEQUENCE(ROUNDUP(SQRT(number),0)-1,,2))))))

PF

=LAMBDA(number,[opt],[p],[k],IF(OR(number<2,number<>INT(number)),NA(),IF(ISPRIME(number),IF(ISOMITTED(k),number&" (prime)",LET(k,k&" x "&number,CHOOSE(opt+1,k,PRODUCT(--TEXTSPLIT(k,"x"))&" = "&k,LET(v,--TEXTSPLIT(k,,"x"),TEXTJOIN(" x ",,BYROW(GROUPBY(v,v,ROWS,0,0),LAMBDA(r,TEXTJOIN("^",,r))))),LET(v,--TEXTSPLIT(k,,"x"),PRODUCT(v)&" = "&TEXTJOIN(" x ",,BYROW(GROUPBY(v,v,ROWS,0,0),LAMBDA(r,TEXTJOIN("^",,r)))))))),LET(p,IF(ISOMITTED(p),LET(a,SEQUENCE(MIN(number,100)),FILTER(a,MAP(a,ISPRIME))),FILTER(p,p<=number)),v,@FILTER(p,NOT(MOD(number,p))),IF(ISNUMBER(v),PF(number/v,opt,p,TEXTJOIN(" x ",1,k,v)),LET(a,SEQUENCE(CEILING.MATH(MAX(p),100)*2),PF(number,opt,FILTER(a,MAP(a,ISPRIME)),k)))))))

Optional [opt] argument:

• 0 - prime factors (default)
• 1 - prime factors with total
• 2 - grouped
• 3 - grouped with total

Examples:

=MAP(SEQUENCE(1000,,2),PF)

-or-

=MAP(SEQUENCE(100,,999900),LAMBDA(v,PF(v,3)))

PF (with line breaks and indentation):

=LAMBDA(number,[opt],[p],[k],
   IF(
      OR(number < 2, number <> INT(number)),
      NA(),
      IF(
         ISPRIME(number),
         IF(
            ISOMITTED(k),
            number & " (prime)",
            LET(
               k, k & " x " & number,
               CHOOSE(
                  opt + 1,
                  k,
                  PRODUCT(--TEXTSPLIT(k, "x")) & " = " & k,
                  LET(v, --TEXTSPLIT(k,, "x"), TEXTJOIN(" x ",, BYROW(GROUPBY(v, v, ROWS, 0, 0), LAMBDA(r, TEXTJOIN("^",, r))))),
                  LET(v, --TEXTSPLIT(k,, "x"), PRODUCT(v) & " = " & TEXTJOIN(" x ",, BYROW(GROUPBY(v, v, ROWS, 0, 0), LAMBDA(r, TEXTJOIN("^",, r)))))
               )
            )
         ),
         LET(
            p, IF(ISOMITTED(p), LET(a, SEQUENCE(MIN(number, 100)), FILTER(a, MAP(a, ISPRIME))), FILTER(p, p <= number)),
            v, @FILTER(p, NOT(MOD(number, p))),
            IF(
               ISNUMBER(v),
               PF(number / v, opt, p, TEXTJOIN(" x ", 1, k, v)),
               LET(a, SEQUENCE(CEILING.MATH(MAX(p), 100) * 2), PF(number, opt, FILTER(a, MAP(a, ISPRIME)), k))
            )
         )
      )
   )
)

Cheers!

 

[saboh12617]

Hi @djclements,

I've spent a long time studying the recursion in your PF function and I must say I'm very impressed. It's super efficient, and the progressive division of the initial number by its factors makes it possible to handle much larger numbers than I thought possible (with my rather “brute force” algorithm on the side ).

Recursive formulas when used correctly are definitely powerful.

Congratulations, that's great!

 

[djclements]

@saboh12617
Thanks a bunch! Truthfully, I spent more hours on this today than originally planned. I struggled at first to get the recursion working properly, as well as efficiently. It went through many variations but turned out well in the end. My brain's fried now, lol.

 

[RaviWildcat]

My favorite thing about this board isn't simply when someone posts the answer. (Although obviously that's cool!)

My favorite thing is when I can learn something new from the answer (sequence, mmult, lambda, map etc.), it goes hand in hand with learning that there is so much I don't know about Excel which is wonderful and humbling simultaneously.

Thank you all so much!