TAOCP 7.2.2 Exercise 22
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$.
Exercise 22. [M26] [M26] Explore "loose Langford pairs": Replace '$j + k + 1$' in (7) by '$j + \lfloor 3k/2 \rfloor$'.
Verified: no
Solve time: 4m55s
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}}$