6
$\begingroup$

For example, I have the number $420$. This can be broken down into its prime factorization of $$2^2 \times3^1\times5^1\times7^1 = 420 $$

Using $$\prod_{i=1}^r (a_r + 1)$$ where $a$ is the magnitude of the power a prime factor is raised by and $r$ is the number of prime factors. I get $24$ possible factors.

Is there an easy way to iterate through all those $4$ factors to obtain all $24$? I know this can be easily done using a table with numbers with only $2$ factors. But, as this one has $4$ I obviously can't implement the table method. So any general solution to do this? Thanks!

$\endgroup$
  • 3
    $\begingroup$ Does $2^3$ really divide $420$? $\endgroup$ – Lord Shark the Unknown May 15 '18 at 18:21
  • $\begingroup$ Whoops, that's supposed to be a $2^2$ thanks for pointing that out. $\endgroup$ – Alex May 15 '18 at 18:22
  • $\begingroup$ Don't you mean $\displaystyle \prod_{i=1}^r (a_r+1)$ ? I also got 32 possible factors by $4(2)(2)(2)$. it's 30 if you get rid of the trivial ones $\endgroup$ – N8tron May 15 '18 at 18:23
  • $\begingroup$ It's not 32, I just put the wrong power for 2, it's definitely 24. Sorry! $\endgroup$ – Alex May 15 '18 at 18:25
7
$\begingroup$

By way of example of a table of factors, just to check we're talking about the same thing:

The factors of $8=2^3$ are of course just $2^0, 2^1, 2^2, 2^3$ or calculated out $1,2,4,8$.

The factors of $9=3^2$ are $3^0, 3^1, 3^2$ aka $1,3,9$.

Now the factors of $72$ can be made up by combining two numbers chosen, one from each of these two sets:

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 8 \\\hline 1 & 1 & 2 & 4 & 8 \\ 3 & 3 & 6 & 12 & 24 \\ 9 & 9 & 18 & 36 & 72 \\ \end{array}

This is no doubt the kind of table you are thinking of.

For $420$ we could apply this process repeatedly, just feeding the contents of each table into one axis of the next table:

\begin{array}{c|ccc} \times & 1 & 2 & 4 \\\hline 1 & 1 & 2 & 4 \\ 3 & 3 & 6 & 12 \\ \end{array}

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 \\ 5 & 5 & 10 & 20 & 15 & 30 & 60 \\ \end{array}

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 & 5 & 10 & 20 & 15 & 30 & 60 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 & 5 & 10 & 20 & 15 & 30 & 60\\ 7 & 7 & 14 & 28 & 21 & 42 & 84 & 35 & 70 & 140 & 105 & 210 & 420\\ \end{array}

or for a slightly more attractive final table we could split the factors into more equal subsets, here the factors of $2^23^1 =12$ across the top and the factors of $5^17^1=35$ down the side.

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 \\ 5 & 5 & 10 & 20 & 15 & 30 & 60\\ 7 & 7 & 14 & 28 & 21 & 42 & 84 \\ 35 & 35 & 70 & 140 & 105 & 210 & 420\\ \end{array}

$\endgroup$
  • $\begingroup$ Wow! This was exactly what I was looking for, that's so cool! $\endgroup$ – Alex May 15 '18 at 20:12
  • 4
    $\begingroup$ Or we can put the table in n-dimensional space, where n is the number of distinct prime factors. $\endgroup$ – Acccumulation May 15 '18 at 22:18
  • 6
    $\begingroup$ @Acccumulation I couldn't get the 4-dimensional formatting to work :-) $\endgroup$ – Joffan May 15 '18 at 22:46
  • 3
    $\begingroup$ @Joffan You can simulate the 4D formatting by using a 2D table of 2D tables, like \begin{array}{ccccc|ccc} & & & 1 & & & 5\\ & & & & \\ 1 & & 1 & 2 & 4 & 5 & 10 & 20\\ & & 3 & 6 & 12 & 15 & 30 & 60\\ \hline 7 & & 7 & 14 & 28 & 35 & 70 & 140\\ & & 21 & 42 & 84 & 105 & 210 & 420 \end{array} $\endgroup$ – Mark S. May 16 '18 at 2:06
  • 2
    $\begingroup$ hmmm... I personally prefer the "odometer" reading. Factor is $n = 2^a3^b5^c7^d$ so just list out all the $(d,c,b,a)$ as they roll out on an odometer. $(0,0,0,0)$ $(0,0,0,1)$, $(0,0,0,2)$, $(0,0,1,0)$, $(0,0,1,1)$,$(0,0,1,2)$, $(0,1,0,0)$, etc.... so $(1,0,1, 2)$ for instance would be $7^1*5^0*3^1*2^2 = 7*3*4 = 84$. That way I wouldn't need my 4-dimensional table formating. $\endgroup$ – fleablood May 16 '18 at 15:22
13
$\begingroup$

Expand the following expression: $$(2^0+2^1+2^2)(3^0+3^1)(5^0+5^1)(7^0+7^1)$$ Each combination of four choices (e.g. $2^2, 3^1, 5^0, 7^1$, whose product is $2^23^15^07^1=84$) gives a distinct factor of $420$.

$\endgroup$
  • $\begingroup$ So out of those 84 only 24 of them are unqiue? Is this really the simplest way of finding all the factors? That's so much distributing and elinimating duplicates. $\endgroup$ – Alex May 15 '18 at 18:28
  • 2
    $\begingroup$ $84$ is one of the $24$ divisors. All $24$ divisors are unique. $\endgroup$ – vadim123 May 15 '18 at 18:29
  • $\begingroup$ Oh I get it! That's really cool :) $\endgroup$ – Alex May 15 '18 at 18:30
5
$\begingroup$

Well... yeah. They are all the numbers that are in the form $2^a3^b5^c7^d$ where $0 \le a \le 2; 0 \le b\le 1; 0 \le c\le 1;0 \le d\le 1;$

Just list them all:

$2^03^05^07^0 = 1$

$2^13^05^07^0 = 2$

$2^23^05^07^0 = 4$

$2^03^15^07^0 =3$

$2^13^15^07^0 =6$

....etc...

Less typing: they are $1,2,4,3,6,12,5,10,20,15,30,60,7,14,28,21,42,84,35,70,140,105,210,420$

In general if $N=\prod p_i^{k_i}$ just list every possible $\prod p_i^{m_i}$ where for each $m_i$ $0\le m_i \le k_i$.

$\endgroup$
  • 1
    $\begingroup$ Notice that the exponents form a mixed radix number that is repeatedly incremented (by $1$) with radices (left-to-right) 3, 2, 2, 2. It's a little weird to increment on the left and carry to the right, but that could be fixed in several ways. $\endgroup$ – Eric Towers May 16 '18 at 3:19
  • $\begingroup$ In an earlier edit I first listed from right to left (first the 7, then the 5, and the twos last). But I think going from left to right seemed more natural as we are doing the generally smaller terms first. Also I prefer "rolling " through the terms with the highest powers first. But frankly I really don't think it matters. Does it? $\endgroup$ – fleablood May 16 '18 at 4:32
  • $\begingroup$ The increment is easier to pick out of the visual noise (all the non-superscripts) if it is $0000, 0001, 0002, 0010, \dots$. It's not necessary, but it may well be clearer. $\endgroup$ – Eric Towers May 16 '18 at 6:16
  • $\begingroup$ I was hoping that would be clear. But without the "visual noise" I don't know if someone would see or understand that 0000=1,0001=2,0002=4,0010=3 etc. $\endgroup$ – fleablood May 16 '18 at 15:14
4
$\begingroup$

If $n = \prod_{i=1}^r p_i^{a_i} $ is the prime factorization on $n$, there are $\prod_{i=1}^r (a_i + 1) $ prime factors.

Look at this as counting a $r$-digit number in a variable base, with the base of the $i$-th digit being $a_i+1$, so that digit goes from $0$ to $a_i$. If $b_i$ is the $i$-th digit, then the value corresponding to that digit is $p_i^{b_i}$.

Here is my take on a moderately efficient algorithm to compute all the possible factors. The divisor starts at $1$. When a digit is incremented, the value of the divisor is multiplied by $p_i$. If the $i$-th digit exceeds $a_i$, it is set to zero, the divisor divided by $p_i^{a_i}$, and the next digit is examined.

Initialize $d = 1$ (the divisor) and $b_i = 0$ and $c_i = p_i^{a_i}$ for $i=1$ to $r$ (the exponents and max powers of $p_i$).

$\text{do forever}\\ \quad\text{output } d\\ \quad\text{for }i=1\text{ to }r\\ \qquad \text{if } b_i<a_i\text{ then } b_i=b_i+1; d=d\cdot p_i; \text{ exit for loop} \quad\text{(digit did not overflow)}\\ \qquad\text{else } b_i=0; d=d/c_i \quad\text{(digit overflowed - reset and look at next digit)}\\ \quad\text{end for}\\ \quad\text{if }d=1\text{ then exit do loop} \quad\text{(all digits overflowed - done)}\\ \text{end do}\\ $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.