Counting factors
Problem
Counting Factors printable sheet
Charlie wants to know how many factors 360 has.
How would you work it out?
Click below to see what Alison did.
Alison divided 360 by each number in turn to see if it was a factor, and wrote down the factor pairs:
(2, 180
(3, 120)
(4, 90)
(5, 72)
(6, 60)
(8, 45)
(9, 40)
(10, 36)
(12, 30)
(15, 24)
(18, 20)
"I can stop there, because the next factor would be 20 and I've already got that. So there are 24 factors."
Charlie thought about it in a different way. Click below to see what he did.
Charlie started by working out the prime factorisation of 360.
$$\begin{align} 360 &= 2 \times 180 \\ &= 2 \times 2 \times 90 \\ &= 2 \times 2 \times 2 \times 45 \\ &= 2 \times 2 \times 2 \times 3 \times 15 \\ &= 2 \times 2 \times 2 \times 3 \times 3 \times 5 \end{align}$$
So $360 = 2^3 \times 3^2 \times 5$.
Then he made a table to list the 24 possible combinations of the prime factors.
|
$2^0$ |
|
||||||||||||
|
$2^1$ |
|
||||||||||||
|
$2^2$ |
|
||||||||||||
|
$2^3$ |
|
So the top branch gives us $2^0 \times 3^0 \times 5^0 =1$
the second branch gives us $2^0 \times 3^0 \times 5^1 =5$
the third branch gives us $2^0 \times 3^1 \times 5^0 =3$
the fourth branch gives us $2^0 \times 3^1 \times 5^1 =15$...
... and the eleventh branch gives us $2^1 \times 3^2 \times 5^0 = 18$
When she saw Charlie's method, Alison said "There must be lots of numbers which have exactly 24 factors!"
Charlie and Alison think all of these numbers have exactly 24 factors.
Can you use Charlie's method to explain why?
$25725 = 5^2 \times 3^1 \times 7^3$
$217503 = 11^1 \times 13^3 \times 3^2$
$312500 = 5^7 \times 2^2$
$690625 = 17^1 \times 13^1 \times 5^5$
$94143178827 = 3^{23}$
Here are some questions to consider:
How can I find a number with exactly 14 factors?
How can I find the smallest such number?
How can I find a number with exactly 15 factors?
How can I find the smallest such number?
How can I find a number with exactly 18 factors?
How can I find the smallest such number?
Which numbers have an odd number of factors?
Extension:
What is the smallest number with exactly 100 factors?
Which number less than 1000 has the most factors?
You may be interested in the other problems in our Hidden Treasures Feature.
Getting Started
Consider the prime factorisation of 12:
$$\begin{align} 12 &= 2 \times 6 \\ &= 2 \times 2 \times 3 \end{align}$$
So $12 = 2^2 \times 3^1$.
Can you see how the table below can be used to find the six factors of 12?
|
$2^0$ |
|
||
|
$2^1$ |
|
||
|
$2^2$ |
|
The first branch gives us $2^0 \times 3^0 =1$
The second branch gives us $2^0 \times 3^1 =3$
The third branch gives us $2^1 \times 3^0 =2$
The fourth branch gives us $2^1 \times 3^1 =6$
The fifth branch gives us $2^2 \times 3^0 =4$
The sixth branch gives us $2^2 \times 3^1 =12$
Student Solutions
Maud from Hymers College in England and Luke from Long Field Academy, both in England, used Alison's method to count the factors of 360. Maud wrote:
To find the factors you need to know what factors are, factors can't be above the number you are trying to find the factors for, so you would divide 360 by a number (I would start at 1 then keep going up) and that would be 360 so 360 and 1 are both factors and you would do this for the rest until it repeats itself.
Holly and Amy from Long Field Academy and Sanika from India used Charlie's method to count how many factors 360 has. This is Holly's work:
$360 = 2^3\times3^2\times5^1$
Number of factors $=4\times3\times2 = 24$
Alex and Amy from Long Field Academy and Sanika also used Charlie's method to show that Alison and Charlie's other numbers have 24 factors. This is Alex's work:
25725= 52$\times$31$\times$73
Click to see Alex's table
|
50 |
30 |
70 |
1 |
|
71 |
7 |
||
|
72 |
49 |
||
|
73 |
343 |
||
|
31 |
70 |
3 |
|
|
71 |
21 |
||
|
72 |
147 |
||
|
73 |
1029 |
||
|
51 |
30 |
70 |
5 |
|
71 |
35 |
||
|
72 |
245 |
||
|
73 |
1715 |
||
|
31 |
70 |
15 |
|
|
71 |
105 |
||
|
72 |
735 |
||
|
73 |
5145 |
||
|
52 |
30 |
70 |
25 |
|
71 |
175 |
||
|
72 |
1225 |
||
|
73 |
8575 |
||
|
31 |
70 |
75 |
|
|
71 |
525 |
||
|
72 |
3675 |
||
|
73 |
25725 |
So there will be 3 rows in the first column which match the 5. Also in the second column there will be 2 rows to match the 3. And there will be 4 that match the 7. The number of factors = 3 $\times$ 2 $\times$ 4 = 24.
217503 = 111$\times$133$\times$32
So there will be 2 rows in the first column which match the 11. Also in the second column there will be 4 rows to match the 13. And there will be 3 that match the 3. The number of factors = 2 $\times$ 4 $\times$ 3 = 24.
312500 = 57 $\times$ 22
So there will be 8 rows in the first column which match the 7. Also in the second column there will be 3 rows to match the 2. The number of factors = 8 $\times$ 3 = 24.
690625 = 171$\times$131$\times$ 55
So there will be 2 rows in the first column which match the 17. Also in the second column there will be 2 rows to match the 13. And there will be 6 that match the 5. The number of factors = 6 $\times$ 2 $\times$ 2 = 24.
94143178827 = 323
So there will be 24 rows in the first column which match the 3. The number of factors = 24 $\times$ 1 = 24.
Sanika and Amy found the smallest numbers with 14 and 15 factors. This is Amy's work:
To find the smallest number with 14 factors, you would list all of the factors of 14:
2 $\times$ 7
1 $\times$ 14
Then, you would pick the pair of numbers that have the least difference between them. In this case, it is 2 and 7. Then take 1 away from each of the numbers:
2$-$1 = 1
7$-$1 = 6
These numbers will be the powers. Then, you would pick the two smallest prime numbers, however, they must be different else the number of factors will be incorrect.
The two prime numbers that you would need to use are 2 and 3. Then, you would give the smallest prime number (2), the biggest power (6).
You need to do this in order to ensure that you get the smallest number possible.
So, the number would be:
26 $\times$ 31 = 192
This method would be the same to work out the smallest number of factors for any number, all that you need to change would be to swap the number 14 with the number of factors that you want your number to have. For example,
to find the smallest number with 15 factors:
Factors of 15:
3 $\times$ 5
1 $\times$ 15
Choose the pair of factors with the least difference:
3 and 5
Take away 1:
3$-$1 = 2
5$-$1 = 4
Smallest, different, prime numbers:
2 and 3
Powers:
24 $\times$ 32
24 $\times$ 32 = 144
This is Sanika's work for a number with 18 factors:
To find numbers with exactly 18 factors we must make sure the product of all the exponents (+1) of the prime factors give us 18. The factors of 18 include (1,18) (2,9) (3,6). We can further prime factorise the last two pairs to give us (2, 3, 3). Smaller the exponent the lesser the value is going to be. So we will take (2, 3, 3) as the exponents. We will take the first three primes as bases i.e. 2 3 & 5. This will give us a final answer of 22$\times$32$\times$5. This leaves us with 180.
Sanika also explained which numbers have an odd number of factors:
Numbers which are perfect squares will have an odd number of factors as one number will be repeated whilst writing down its factor pairs.
E.g. Let's consider 16= 24 $\rightarrow$ (1, 16) (2, 8) (4, 4)
So 16 has a total of 5 factors as 4 is repeated twice. This holds true for all other perfect squares.
Sanika found the smallest number with exactly 100 factors:
Prime factorising 100 gives us 2$\times$2$\times$5$\times$5, now we can assign the smallest prime bases to the largest powers, which will give us 24$\times34$\times$5$\times$7 = 45360.
Sanika and Amy both said that the number under 1000 with the most factors is 840 (32 factors). This is Amy's work:
Finally, to find the number less than 1000 that has the most factors, you have to try and multiply together the widest range of prime numbers, starting with the lowest:
2 $\times$ 3 $\times$ 5 $\times$ 7 $\times$ 11 $\gt$ 1000 but,
2 $\times$ 3 $\times$ 5 $\times$ 7 $\lt$ 1000 so these are the numbers that we will use.
2 $\times$ 3 $\times$ 5 $\times$ 7 = 210, so, now we can add powers to the number 2 until the number is as close to 1000 as possible.
Therefore, the answer is 23 $\times$ 31 $\times$ 51 $\times$ 71 = 840: this is the closest number to 1000.
Using the information above, the number of factors that it has must be 32.
Teachers' Resources
Why do this problem?
This problem invites students to explore the power of using a prime factorisation representation of a number.
Possible approach
This problem featured in an NRICH webinar in June 2020.
Start by inviting students to work out how many factors some numbers have, perhaps including the example 360 as in the problem. (It is plausible that someone might be interested in factors of 360, so you could make the connection to angle work and regular polygons.)
Once they have had a go, share strategies for working it out; most students will probably list all the factor pairs, prompting a discussion of systematic working, and deciding when to stop.
Students with an interest in programming may wish to consider how to write a simple program to find all the factors of a number. For very large numbers, the realisation that you only need consider potential factors less than the square root of the number speeds up a program considerably!
If no-one used a prime factorisation method similar to Charlie's, share his method from the problem and the tree-diagram or table structure he used to count the factors.
Then give students some time in pairs to discuss how we can be sure the following numbers all have exactly 24 factors:
$25725 = 5^2 \times 3^1 \times 7^3$
$217503 = 11^1 \times 13^3 \times 3^2$
$312500 = 5^7 \times 2^2$
$690625 = 17^1 \times 13^1 \times 5^5$
$94143178827 = 3^{23}$
Once students have had a chance to make sense of Charlie's method, challenge them to apply it to solve some of the questions below:
How can I find a number with exactly 14 factors?
How can I find the smallest such number?
How can I find a number with exactly 15 factors?
How can I find the smallest such number?
How can I find a number with exactly 18 factors?
How can I find the smallest such number?
Which numbers have an odd number of factors?
Possible support
Students might find it easier to explore the problem in the context of finding all possible rectangles with integer sides with a given area, and then considering the problem of working out how many such rectangles there would be without drawing them all.
Possible extension
What is the smallest number with exactly 100 factors?
Which number less than 1000 has the most factors?
These, and other similar questions, could be explored with paper and pencil using prime factorisation or could be an opportunity for students to use spreadsheets or simple programming.
Students might be interested in this page from the On-line Encyclopedia of Integer Sequences which lists the smallest number with exactly n divisors.