Wednesday, October 23, 2019

A Simple Method to Count an Integer's Factors from its Prime Factorization

Suppose we have we have an integer x whose prime factorization is a^n * b^m * c^l * d^h, where all variables here are also integers.

Then a, a^2, a^3,...a^n each must be factors of x as they clearly divide x's prime factorization (PF), yielding n distinct factors.

Similarly this is true for b, b^2, b^3,...b^m, yielding m factors.
And so and so forth for prime factors c and d; they each yield a number of factors equal to their respective exponents (l and h).
Thus far we have n + m + l + h factors.

We also have each combination of two primes from the PF; here is one for a and b:
  a*b,     a*b^2,      a*b^3...     a*b^m
a^2*b, a^2*b^2, a^2*b^3....a^2*b^m
a^3*b, a^3*b^2, a^3*b^3....a^3*b^m
.
.
.
a^n*b, a^n*b^2, a^n*b^3....a^n*b^m

Each element in this table divides the PF of x (and therefore x). This is an mxn table and so contains mn elements to add to our total number of factors.
Similar tables can be constructed for each other pair of prime factors, and each table would have a number of elements equivalent to the product of the exponents of that pair.

Here is the table for b and c:
  b*c,     b*c^2,      b*c^3...     b*c^l
b^2*c, b^2*c^2, b^2*c^3....b^2*c^l
b^3*c, b^3*c^2, b^3*c^3....b^3*c^l
.
.
.
b^m*c, b^m*c^2, b^m*c^3....b^m*c^l
Which yields ml elements.


In the end we will take all possible pairs of products of exponents! Yielding nm + nl + nh + ml + mh + lh.

For three factors, instead of a two dimensional table as shown above, you will get a three dimensional cube, with dimensions equal to the product of the exponents of the prime factors! And we will iterate for each possible cube, i.e. each possible triplet of prime factors, as shown in the uploaded picture. Thus we take each triplet product: nml + mlh + nmh +nlh.

We repeat this process but for three factors, and then four, then five... etc.
Reiterate for four factors: this will give a four dimensional hypercube, and we count the elements in each possible 4D hypercube. In this case we only have one such possible hypercube with cardinality nmlh. 

With each new prime factor in the PF we would keep repeating this process.

Thus in total we have 
n + m + l + h  +
nm + nl + nh + ml + mh + lh +
nml + mlh + nmh +nlh +
nmlh
factors in x.

I am not quite sure how to write that out as a mathematical statement. This is the process in English: note the exponent for each prime factor of x. Add each possible singleton, pair product, triplet product, quadruplet product, and so on for how many exponents there are. This sum is the number of factors in x. Quite a handy shortcut for doing GRE factorization problems!








No comments:

Post a Comment