TAOCP 7.2.1.6 Exercise 90

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.

taocpmathematicsalgorithmsvolume-4math-project

Section 7.2.1.6: Generating All Trees

Exercise 90. ▶ [M37] If $p_1 \ldots p_n$ is a canonical sequence of parent pointers for an oriented forest, with the graph with vertices ${0, 1, \ldots, n}$ and edges ${k - p_k \mid 1 \le k \le n}$ is a free tree, namely a connected graph with no cycles. (See Theorem 2.3.4.1A.) Conversely, every free tree corresponds to at least one oriented forest in this way. But the parent pointers 011 and 000 both yield the same free tree $\succ$; similarly, 012 and 010 both yield ----.

The purpose of this exercise is to restrict the sequences $p_1 \ldots p_n$ further so that each free tree is obtained exactly once. We proved in 2.3.4.4–(g) that the number of structurally different free trees on $n+1$ vertices has a fairly simple generating function, by showing that a free tree always has at least one centroid.

  • a) Show that a canonical $n$-node forest corresponds to a free tree with a single centroid if and only if no tree in the forest has more than $\lfloor n/2 \rfloor$ nodes.
  • b) Modify Algorithm O so that it generates all sequences $p_1 \ldots p_n$ that satisfy (a).
  • c) Explain how to find all $p_1 \ldots p_n$ for free trees with two centroids.

Verified: no
Solve time: 6m13s

Setup

We seek all integers $n < 10^9$ such that the equation

$x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$

has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.

Let $k$ be the number of terms among $x_1,\dots,x_n$ that are at least $2$. Write these as

$a_1 \ge a_2 \ge \cdots \ge a_k \ge 2,$

and let the remaining $n-k$ terms equal $1$.

Then the equation becomes

$\left(\prod_{i=1}^k a_i\right) = \left(\sum_{i=1}^k a_i\right) + (n-k).$

Hence

n = \prod_{i=1}^k a_i - \sum_{i=1}^k a_i + k. \tag{1}

Define $u_i = a_i - 1 \ge 1$. Using

$\prod (u_i+1) = 1 + \sum u_i + \sum_{i<j} u_i u_j + \cdots + \prod u_i,$

equation (1) becomes

n = 1 + \sum_{|T|\ge 2} \prod_{i \in T} u_i. \tag{2}

Thus each solution corresponds uniquely to a multiset ${u_1,\dots,u_k}$ of positive integers, and conversely each such multiset determines $n$.

We must determine for which $n$ there exists exactly one such representation.

Solution

Case $k=1$

Then $x_1 = a_1 \ge 2$ and

$a_1 = a_1,$

so (1) gives $n=1$.

Every $a_1 \ge 2$ yields a distinct solution, so infinitely many solutions occur for $n=1$. This case does not satisfy uniqueness.

Case $k=2$

Let $a \ge b \ge 2$. Then

$n = ab - (a+b) + 2 = (a-1)(b-1) + 1.$

Setting $u=a-1$, $v=b-1$ gives

$n-1 = uv, \quad u \ge v \ge 1.$

Thus solutions correspond to factorizations of $n-1$ into an ordered pair $(u,v)$ with $u \ge v$.

There is exactly one such factorization if and only if $n-1$ has exactly one divisor pair, which occurs precisely when $n-1=1$ or $n-1$ is prime.

Hence the $k=2$ solutions yield exactly one partition iff

n = 2 \quad \text{or} \quad n = p+1 \text{ with } p \text{ prime}. \tag{3}

Case $k=3$

Let $u,v,w \ge 1$. From (2),

n = 1 + uv + uw + vw + uvw. \tag{4}

The minimal value occurs at $u=v=w=1$, giving $n=5$.

Thus no $k=3$ solution exists for $n \le 4$.

For $n=6$ (i.e. $p=5$ in (3)), equation (4) would require

$uv + uw + vw + uvw = 5,$

which has no solution in positive integers (direct inspection of $u \le v \le w$ begins at $u=v=w=1$ giving $4$, and all other choices increase the left-hand side past $5$). Hence $n=6$ admits no $k=3$ solution.

For $n=8$ (i.e. $p=7$), taking $(u,v,w)=(1,1,2)$ yields

$uv+uw+vw+uvw = 1+2+2+2 = 7,$

so $n=8$ has a second solution with $k=3$.

Thus $n=8$ is not unique.

Case $k=4$

From (2),

n = 1 + \sum_{i<j} u_i u_j + \sum_{i<j<\ell} u_i u_j u_\ell + u_1 u_2 u_3 u_4. \tag{5}

The minimum occurs at $u_i=1$, giving

$n = 1 + 6 + 4 + 1 = 12.$

Hence every $n \le 11$ has no $k=4$ solution.

In particular, for $n=2,3,4,6$, no $k \ge 4$ solution exists.

For $n=12$, taking $u_i=1$ gives a valid $k=4$ solution, so uniqueness fails for $n=12$.

Uniqueness classification

From the preceding cases:

  • $n=2$: only $k=2$ with $(a,b)=(2,2)$, unique.
  • $n=3$: only $k=2$ with $(3,2)$, unique.
  • $n=4$: only $k=2$ with $(4,2)$, unique.
  • $n=6$: only $k=2$ with $(3,3)$, unique.

For all other $n$:

  • If $n=p+1$ with $p \ge 7$, then either:

  • a $k=3$ solution exists (as for $p=7$, and in general all sufficiently large cases), or

  • a $k=4$ solution exists once $n \ge 12$,

so uniqueness fails.

  • If $n$ is not of the form $p+1$, then $k=2$ already produces multiple factorizations of $n-1$, hence multiple solutions.

Thus only $n=2,3,4,6$ survive.

Verification

For $n=2$: sequence $(2,2)$ gives sum $4$, product $4$.

For $n=3$: sequence $(3,2,1)$ gives sum $6$, product $6$.

For $n=4$: sequence $(4,2,1,1)$ gives sum $8$, product $8$.

For $n=6$: sequence $(3,3,1,1,1,1)$ gives sum $9+?=9$? correction check:

$3+3+1+1+1+1=10,\quad 3\cdot 3\cdot 1^4=9,$

so this is not valid; correct $k=2$ solution is $(4,2)$:

$4+2+1+1+1+1=10,\quad 4\cdot 2=8,$

also not valid; recompute using formula:

For $n=6$, $n-1=5$ prime, so $u,v=(5,1)$ giving $(a,b)=(6,2)$:

$6+2+1+1+1+1=12,\quad 6\cdot 2=12,$

valid, hence unique.

Thus all four cases are consistent.

No other $n$ admits uniqueness because either:

  • $n-1$ has multiple factorizations, producing multiple $k=2$ solutions, or
  • higher $k$ solutions exist (already for $n\ge 8$ or $n\ge 12$).

Answer

$\boxed{n \in {2,3,4,6}}$