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?

 

[Sam_D_Ben]

May be something like this,

Book1
	A	B	C	D	E	F	G
5	Given Number	A	B	C	D	E	F
6	40	20	10	5	1	-	-
Sheet1

Cell Formulas
Range	Formula
B6:G6	B6	=IF(OR(A6=1,A6="-"),"-",IF(A6=1,"-",A6/INDEX(FILTER(SEQUENCE(100,1,2,1),MOD(A6,SEQUENCE(100,1,2,1))=0),1)))

 

[6StringJazzer]

I'm not clear on what result you are trying to get. Are you trying to determine the prime factors of any arbitrary number? Your example does not show that result for 40.

I think doing this with formulas would be rather onerous, mostly because the same factor can appear multiple times for a number (e.g., 40 = 2 x 2 x 2 x 5). With 365 some formula wizard might know how to do this with some kind of recursive Lambda function. I am very comfortable with VBA and could write a VBA UDF for this if you're open to that idea.

What is the largest number you would want to factor?

 

[6StringJazzer]

May be something like this

This seems to replicate the OP's example, but it does not show the prime factors of 40, so I think we need clarification of the objective.

 

[Eric W]

How about:

Book1
	A	B	C	D	E
1	Number	Factorization			Primes
2	72	2^3 * 3^2			2
3	18	2^1 * 3^2			3
4	12	2^2 * 3^1			5
5	17	17^1			7
6	85	5^1 * 17^1			11
7	77	7^1 * 11^1			13
8	40	2^3 * 5^1			17
9					19
10					23
11					29
12					31
13					37
14					41
15					43
16					47
17
Sheet1

Cell Formulas
Range	Formula
E2:E16	E2	=LET(ub,50,p,SEQUENCE(ub-1,,2),f,SEQUENCE(,ub-1,2),nd,MMULT(--(MOD(p/f,1)=0),p^0),FILTER(p,nd=1))
B2:B8	B2	=LET(n,A2,p,E$2#,m,ROUNDUP(LOG(n)/LOG(2),0),d,n/(p^SEQUENCE(,m)),f,MMULT(--(MOD(d,1)=0),SEQUENCE(m,,,0)),TEXTJOIN(" * ",1,IF(f>0,p&"^"&f,"")))
Dynamic array formulas.

The formula in E2 will calculate the primes up to the upper bound you want, which I have set to 50 in this case. Note that it is a very inefficient method, but it should work fine for reasonably small values.

Then you can use the formula in column B to find the prime factors of any number. Again, not an extremely efficient algorithm, but it should work for reasonably small values. I started noticing a lag around 1000.

Anyway, let us know if this is what you're looking for.

 

[RaviWildcat]

I'm not clear on what result you are trying to get. Are you trying to determine the prime factors of any arbitrary number? Your example does not show that result for 40.

I think doing this with formulas would be rather onerous, mostly because the same factor can appear multiple times for a number (e.g., 40 = 2 x 2 x 2 x 5). With 365 some formula wizard might know how to do this with some kind of recursive Lambda function. I am very comfortable with VBA and could write a VBA UDF for this if you're open to that idea.

What is the largest number you would want to factor?

You are correct - I did not factor the original 40 correctly! Eventually I'd want to factor a number up to 999999.

- I thank you for offering to write a VBA UDF , I'm simply curious about recursive functions.
- I also thank you for introducing me to recursive lambda functions.
- I finally thank you for pointing out my mistake before my nephew would have pointed it out since he would certainly lord it over me for all eternity

 

[RaviWildcat]

May be something like this,

Book1
	A	B	C	D	E	F	G
5	Given Number	A	B	C	D	E	F
6	40	20	10	5	1	-	-
Sheet1

Cell Formulas
Range	Formula
B6:G6	B6	=IF(OR(A6=1,A6="-"),"-",IF(A6=1,"-",A6/INDEX(FILTER(SEQUENCE(100,1,2,1),MOD(A6,SEQUENCE(100,1,2,1))=0),1)))

- Whoa - thank you! I'm familiar with index but filter and sequence and range are new tricks I'll need to investigate! Let me read up on how how they work and then try this cool solution you are proposing!

 

[RaviWildcat]

This seems to replicate the OP's example, but it does not show the prime factors of 40, so I think we need clarification of the objective.

I did not calculate the primes in my original post but I should have.

 

[RaviWildcat]

How about:

Book1
	A	B	C	D	E
1	Number	Factorization			Primes
2	72	2^3 * 3^2			2
3	18	2^1 * 3^2			3
4	12	2^2 * 3^1			5
5	17	17^1			7
6	85	5^1 * 17^1			11
7	77	7^1 * 11^1			13
8	40	2^3 * 5^1			17
9					19
10					23
11					29
12					31
13					37
14					41
15					43
16					47
17
Sheet1

Cell Formulas
Range	Formula
E2:E16	E2	=LET(ub,50,p,SEQUENCE(ub-1,,2),f,SEQUENCE(,ub-1,2),nd,MMULT(--(MOD(p/f,1)=0),p^0),FILTER(p,nd=1))
B2:B8	B2	=LET(n,A2,p,E$2#,m,ROUNDUP(LOG(n)/LOG(2),0),d,n/(p^SEQUENCE(,m)),f,MMULT(--(MOD(d,1)=0),SEQUENCE(m,,,0)),TEXTJOIN(" * ",1,IF(f>0,p&"^"&f,"")))
Dynamic array formulas.

The formula in E2 will calculate the primes up to the upper bound you want, which I have set to 50 in this case. Note that it is a very inefficient method, but it should work fine for reasonably small values.

Then you can use the formula in column B to find the prime factors of any number. Again, not an extremely efficient algorithm, but it should work for reasonably small values. I started noticing a lag around 1000.

Anyway, let us know if this is what you're looking for.

 

[RaviWildcat]

How about:

Book1
	A	B	C	D	E
1	Number	Factorization			Primes
2	72	2^3 * 3^2			2
3	18	2^1 * 3^2			3
4	12	2^2 * 3^1			5
5	17	17^1			7
6	85	5^1 * 17^1			11
7	77	7^1 * 11^1			13
8	40	2^3 * 5^1			17
9					19
10					23
11					29
12					31
13					37
14					41
15					43
16					47
17
Sheet1

Cell Formulas
Range	Formula
E2:E16	E2	=LET(ub,50,p,SEQUENCE(ub-1,,2),f,SEQUENCE(,ub-1,2),nd,MMULT(--(MOD(p/f,1)=0),p^0),FILTER(p,nd=1))
B2:B8	B2	=LET(n,A2,p,E$2#,m,ROUNDUP(LOG(n)/LOG(2),0),d,n/(p^SEQUENCE(,m)),f,MMULT(--(MOD(d,1)=0),SEQUENCE(m,,,0)),TEXTJOIN(" * ",1,IF(f>0,p&"^"&f,"")))
Dynamic array formulas.

The formula in E2 will calculate the primes up to the upper bound you want, which I have set to 50 in this case. Note that it is a very inefficient method, but it should work fine for reasonably small values.

Then you can use the formula in column B to find the prime factors of any number. Again, not an extremely efficient algorithm, but it should work for reasonably small values. I started noticing a lag around 1000.

Anyway, let us know if this is what you're looking for.

I think this is exactly what I'm looking for! (at least in terms of results) Wow!

Give me some time to investigate!