Finding Divisors, Number of Divisors and Summation of Divisors

Finding Divisors,
Number of Divisors
and
Summation of Divisors
by
Jane Alam Jan
Finding Divisors
If we observe the property of the numbers, we will find some interesting facts. Suppose we have
a number 36.
36 is divisible by 1, 2, 3, 4, 6, 9, 12, 18 and 36. It is clear that if a is divisible by b, then a is also

divisible by (a/b). That means, 36 is divisible by 3, so, this property helps us to find that 36 will
also be divisible by 12 (36/3). Now we will make two lists, if a is divisible by b, then we will
take b into the first list and (a/b) into the second list.
So, for 36, we will evaluate our idea.
36 is divisible by 1. So, it will be added in list 1, and (36/1) = 36 will be added in list 2.
List 1: 1
List 2: 36
List 1: 1 2
List 2: 36 18
List 1: 1 2 3
List 2: 36 18 12
List 1: 1 2 3 4
List 2: 36 18 12 9
List 1: 1 2 3 4 6
List 2: 36 18 12 9 6
Now, see that if we move further we will find the numbers again (some numbers from list 2,
which will try to insert into list 1) So, it is clear that, if we have list 1, we can generate list 2
(from this position).
1|Page
Document prepared by Jane Alam Jan
So, we can stop checking if we find b, for which a/b is less than or equal to b. If we try to divide
by numbers greater than b, we would actually repeat the same steps. For 36, (check the lists) the
next number that will be included to list 1 is 9, but 36/9 = 4, which is already in list 1.
Now we have to find b for which a/b is less than or equal to b. If we think mathematically,
b >= a/b
or, b2 >= a
or, b >= sqrt(a)
so, bminimum = sqrt(a)
So, we have already found an idea to find divisors of a number in complexity - sqrt(N). And of
course, we can count them to find the number of divisors and summing them to find the
summation of divisors.
2|Page
Finding Number of Divisors
Now, we want to find the number of divisors of an integer. It can be done easily by finding all
the divisors and finally counting them as described above. But there is a simpler idea. If we
know the prime factorization of a number, we can easily find the number of divisors.
For example, 18 has 6 divisors. If we prime factorize 18, we find that
18 = 21 * 32
We can say that any divisor of 36 should be in the form
2x * 3y where 0 <= x <= 1 and 0 <= y <= 2
This can be proved easily, but if we think a bit we will find that the reason is obvious.
So, the divisors are,
20 * 30 = 1
20 * 31 = 3
20 * 32 = 9
21 * 30 = 2
21 * 31 = 6
21 * 32 = 18
That means we are taking all possible solutions. These form the number of divisors. Just see the
pattern of the prime factors of the divisors. So, we can say that the number of divisors of 18 is
(1 + 1) * (2 + 1) = 6
So, if a number is factorized as
2x * 3y
Then the number of divisors is (x+1) * (y+1). Again, the reason is
20 * 30
20 * 31
... y + 1 divisors
20 * 3y-1
20 * 3y
21 * 30
21 * 31
... y + 1 divisors
21 * 3y-1
21 * 3y
3|Page
...
2x * 30
2x * 31
... y + 1 divisors
2x * 3y-1
2x * 3y
So, there are (x+1) sections each having (y+1) divisors, which means a total of (x+1) *
(y+1) divisors.
Now, let's find the total number of divisors of 60.
60 = 22 * 3 * 5
So, similarly the divisors are
20 * 30 * 50 = 1
20 * 30 * 51 = 5
20 * 31 * 50 = 3
20 * 31 * 51 = 15
21 * 30 * 50 = 2
21 * 30 * 51 = 10
21 * 31 * 50 = 6
21 * 31 * 51 = 30
22 * 30 * 50 = 4
22 * 30 * 51 = 20
22 * 31 * 50 = 12
22 * 31 * 51 = 60
So, total number of divisors is 12. Let's check it in another way.
For each section of 2 (20, 21 or 22) the number of divisors are same. So, there are 3
sections for 2. Now for each section of 2, there are two sections for 3 (30, 31). Now for any
combination of 2 and 3 there are two sections for 5 (50, 51). So, it can be represented as
(20, 21, 22) and (30, 31) and (50, 51)
So, at first take any power of 2, after that take any power of 3 and after that take any power of 5
from the above sections. So, we can take 2 in three ways, 3 in two ways and 5 in two ways. So,
total ways (or total divisors) are
3 * 2 * 2
= 12
4|Page
Similarly, suppose a number is factorized as 2x * 3y * 5z, so, the total number of divisors is
(x + 1) * (y + 1) * (z + 1)
Now, the general formula is
If the prime factorization of an integer is
p1x1 * p2x2 * p3x3 * ... * pnxn
where, p1, p2, ..., pn are primes, then the number of divisors is
(x1 + 1) * (x2 + 1) * (x3 + 1) * ... * (xn + 1)
5|Page
Finding Summation of Divisors
Suppose we want to find the summation of all the divisors of an integer. We can do it by finding
all the divisors and then summing them. But we can make it better. The idea is as follows.
Let's say we want to find the summation of divisors of 60. From previous section, we know that
the divisors are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60; so the summation
is 168. The summation can be written as (summing up all the divisors in their factorized form),
20 * 30 * 50 + 20 * 30 * 51 + 20 * 31 * 50 + 20 * 31 * 51 +
21 * 30 * 50 + 21 * 30 * 51 + 21 * 31 * 50 + 21 * 31 * 51 +
22 * 30 * 50 + 22 * 30 * 51 + 22 * 31 * 50 + 22 * 31 * 51
It can be written as,
20 * (30 * 50 + 30 * 51 + 31 * 50 + 31 * 51) +
21 * (30 * 50 + 30 * 51 + 31 * 50 + 31 * 51) +
22 * (30 * 50 + 30 * 51 + 31 * 50 + 31 * 51)
can be written as
(20 + 21 + 22) * (30 * 50 + 30 * 51 + 31 * 50 + 31 * 51)
can be written as
(20 + 21 + 22) * (30 * (50 + 51) + 31 * (50 + 51))
can be written as
(20 + 21 + 22) * (30 + 31) * (50 + 51)
Now, we know that the summation of series
2 3
𝑟 𝑛+1 − 1
4 𝑛
1+𝑟+𝑟 + 𝑟 + 𝑟 + … + 𝑟 =
𝑟−1
So, the summation can be written as
23 − 1 32 − 1 52 − 1
∗ ∗ = 7 ∗ 4 ∗ 6 = 168
1 2 4
So, the result is same as we have calculated.
6|Page
So, if the prime factorization of an integer is
𝑝1 𝑥 1 ∗ 𝑝2 𝑥 2 ∗ … ∗ 𝑝𝑛 𝑥 𝑛
where, p1, p2, ..., pn are primes, then the summation of divisors is
𝑝1 𝑥 1 +1 − 1 𝑝2 𝑥 2 +1 − 1 𝑝𝑛 𝑥 𝑛 +1 − 1
∗ ∗…∗
𝑝1 − 1 𝑝2 − 1 𝑝𝑛 − 1
Discussion
After finding the prime factorization, these ideas are easy to code. Before get to coding, try to
understand them fully.
7|Page

Finding Divisors, Number of Divisors and Summation of Divisors

Uploaded by

Copyright:

Available Formats

Finding Divisors, Number of Divisors and Summation of Divisors

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Finding Divisors, Number of Divisors and Summation of Divisors

Uploaded by

Copyright:

Available Formats

Finding Divisors,

36 is divisible by 1, 2, 3, 4, 6, 9, 12, 18 and 36. It is clear that if a is divisible by b, then a is also

So, for 36, we will evaluate our idea.

or, b >= sqrt(a)

so, bminimum = sqrt(a)

For example, 18 has 6 divisors. If we prime factorize 18, we find that

We can say that any divisor of 36 should be in the form

2x * 3y where 0 <= x <= 1 and 0 <= y <= 2

So, the divisors are,

So, if a number is factorized as

Then the number of divisors is (x+1) * (y+1). Again, the reason is

Now, let's find the total number of divisors of 60.

So, similarly the divisors are

So, total number of divisors is 12. Let's check it in another way.

(20, 21, 22) and (30, 31) and (50, 51)

Now, the general formula is

If the prime factorization of an integer is

p1x1 * p2x2 * p3x3 * ... * pnxn

(x1 + 1) * (x2 + 1) * (x3 + 1) * ... * (xn + 1)

It can be written as,

(20 + 21 + 22) * (30 * 50 + 30 * 51 + 31 * 50 + 31 * 51)

(20 + 21 + 22) * (30 * (50 + 51) + 31 * (50 + 51))

(20 + 21 + 22) * (30 + 31) * (50 + 51)

Now, we know that the summation of series

You might also like