TAOCP 7.2.1.1 Exercise 80

Section 7.2.1.1: Generating All n-Tuples

Exercise 80. [M20] [M20] Explain how to run through all divisors of a number, given its prime fac- torization pe1 1 . . . pet t , repeatedly multiplying or dividing by a single prime at each step.

Verified: yes
Solve time: 1m46s

---

Solution

Let the given factorization be

$$ N = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}. $$

Every divisor of $N$ has the unique form

$$ d = p_1^{a_1} p_2^{a_2} \cdots p_t^{a_t}, \qquad 0 \le a_j \le e_j. $$

Thus the task is equivalent to visiting all integer vectors

$$ (a_1,\ldots,a_t) \in \prod_{j=1}^t [0,e_j] \cap \mathbb{Z}^t $$

in such an order that successive vectors differ in exactly one coordinate by $\pm 1$, since multiplying or dividing by a single prime $p_j$ changes only $a_j$ by $+1$ or $-1$.

The structure is the grid graph on this Cartesian product, and the requirement is a Hamiltonian path in which each step moves along one coordinate axis by one unit.

The construction proceeds by induction on $t$.

For $t=1$, the divisors are

$$ 1, p_1, p_1^2, \ldots, p_1^{e_1}, $$

and consecutive terms differ by multiplication or division by $p_1$. This gives the required ordering.

Assume now that a valid ordering is available for all $(t-1)$-tuples. Write

$$ A = (a_1,\ldots,a_{t-1}). $$

Let $G_{t-1}$ denote an ordering of all such $A$ where consecutive tuples differ in exactly one coordinate by $\pm 1$, and suppose $G_{t-1}$ starts at $(0,\ldots,0)$ and ends at $(e_1,\ldots,e_{t-1})$. This endpoint property follows from the same construction applied inductively.

Now define the $t$-dimensional ordering as follows. For each value $a_t = 0,1,\ldots,e_t$, traverse the entire set of $(t-1)$-tuples in alternating directions:

if $a_t$ is even, use $G_{t-1}$ in forward order, and if $a_t$ is odd, use $G_{t-1}$ in reverse order. Between consecutive blocks, only $a_t$ changes by $+1$ or $-1$, while all other coordinates remain fixed at the terminal point of one block and the initial point of the next block, which match by construction of the reversal symmetry.

This produces a full sequence of all $t$-tuples with the required adjacency property.

To translate this into divisors, maintain a current value

$$ d = \prod_{j=1}^t p_j^{a_j}. $$

Whenever a coordinate $a_j$ increases by $1$, update $d \leftarrow d \cdot p_j$. Whenever $a_j$ decreases by $1$, update $d \leftarrow d / p_j$. Since each step of the constructed sequence changes exactly one coordinate by $\pm 1$, each transition modifies $d$ by multiplying or dividing by exactly one prime.

The sequence begins at $a_j=0$ for all $j$, hence at divisor $d=1$, and ends at $(e_1,\ldots,e_t)$, hence at $d=N$.

Every divisor appears exactly once because every exponent vector appears exactly once in the inductive traversal, and each corresponds uniquely to a divisor.

This completes the proof. ∎