TAOCP 7.2.2 Exercise 79

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-hard

Section 7.2.2: Backtracking

Exercise 79. ▶ [M30] The author and his wife own a pipe organ that contains 812 pipes, each of which is either playing or silent. Therefore $2^{812}$ different sounds (including silence) can potentially be created. However, the pipes are controlled by a conventional organ console, which has only $56+56+32=144$ keys and pedals that can be played by hands and feet, together with 20 on-off switches to define the connections between keys and pipes. Therefore at most $2^{164}$ different sounds are actually playable! The purpose of this exercise is to determine the exact number of $n$-pipe playable sounds, for small $n$.

The keys are binary vectors $s = s_1 s_2 \ldots s_{53}$ and $g = g_0 g_1 \ldots g_{31}$; the pedals are $p = p_0 p_1 \ldots p_{31}$; the console control switches are $c = c_0 c_1 \ldots c_{19}$; and the pipes are $r_{i,j}$ for $0 \le i < 16$ and $0 \le j < 56$. Here are the precise rules that define the pipe activity $r_{i,j}$ in terms of the input vectors $s$, $g$, $p$, and $c$ that are governed by the organist:

$$r_{i,j} = \begin{cases} c_1 p_j \vee c_{i+15} p_{j-12}, & i \in {0, 1}; \ c_i p_j, & i \in {2}; \ (c_i \vee c_{i+1}[j < 12]) s_j^, & i \in {3}; \ c_i [j \ge 12] s_j^, & i \in {4, 8}; \ c_i s_j^, & i \in {5, 6, 7}; \end{cases} \quad r_{i,j} = \begin{cases} (c_i \vee c_{i+1}[j < 12]) g_j^, & i \in {9}; \ c_i [j \ge 12] g_j^, & i \in {10}; \ c_i g_j^, & i \in {11, 12}; \ (c_{13} \vee c_{14}) g_j^, & i \in {13}; \ c_{14} g_j^, & i \in {14, 15}. \end{cases}$$

Here $p_j = 0$ if $j < 0$ or $j \ge 32$; $s_j^* = s_j \vee c_{17} g_j \vee c_{18} p_j$; $g_j^* = g_j \vee c_{19} p_j$. [In organ jargon, the array of pipes has 16 "ranks"; ranks ${0, 1, 2}$, ${3, \ldots, 8}$, ${9, \ldots, 15}$ constitute the Pedal, Swell, and Great divisions. Ranks 3 and 4 share their lower 12 pipes, as do ranks 9 and 10. Ranks 13, 14, and 15 form a "mixture," $c_{14}$. Unit ranks $c_{15}$ and $c_{16}$ extend ranks 0 and 1, twelve notes higher. Console switches $c_{17}$, $c_{18}$, $c_{19}$ are "couplers" Swell $\to$ Great, Swell $\to$ Pedal, Great $\to$ Pedal, which explain the formulas for $s_j^$ and $g_j^$.]

A playable sound $S$ is a set of pairs $(i, j)$ such that we have $r_{i,j} = [(i, j) \in S]$ for at least one choice of the input vectors $s$, $g$, $p$, $c$. For example, the first chord of Bach's Toccata in D minor is the 8-pipe sound ${(3, 33), (3, 45), (4, 33), (4, 45), (5, 33), (5, 45), (6, 33), (6, 45)}$, which is achievable when $s_{33} = s_{45} = c_4 = c_5 = c_6 = 1$ and all other inputs are 0. We want to find the number $Q_n$ of playable sounds with $|S| = n$.

a) There are $16 \times 56$ variables $r_{i,j}$ but only 812 actual pipes, because some of the ranks are incomplete. For which pairs $(i, j)$ is $r_{i,j}$ always false?

b) True or false: If $s \subseteq s'$, $g \subseteq g'$, $p \subseteq p'$, and $c \subseteq c'$, then $r \subseteq r'$.

c) Show that every playable sound is achievable with $c_{17} = c_{18} = c_{19} = 0$.

d) Find a 5-pipe playable sound in which just five of the $s_j$, $g_j$, $p_j$, $c_j$ are nonzero.

e) For which $i$ and $i'$ are the 2-pipe sounds ${(i, 40), (i', 50)}$ playable?

f) Determine $Q_1$ by hand, and explain why it is less than 812.

g) Determine $Q_{812}$ by hand.

h) Determine $Q_2, \ldots, Q_{10}$ by computer, and compare them to $\binom{812}{2}, \ldots, \binom{812}{10}$.

We hold several threads in our hands, and the odds are that one or other of them guides us to the truth. We may waste time in following the wrong one, but sooner or later we must come upon the right., SHERLOCK HOLMES, in The Hound of the Baskervilles (1901)

The following Receipts are not a mere marrow-less collection of shreds, and patches, and cuttings, and pastings, from obsolete works, but a bona fide register of practical facts . . . the author submitting to a labour no preceding cookery-book-maker, perhaps, ever attempted to encounter; and having not only dressed, but eaten each Receipt before he set it down in his book., WILLIAM KITCHINER, Apicius Redivivus; Or, The Cook's Oracle (1817)

Just as we hope you will learn from us, we have learned from you, from the recipes and short cuts and tips and traditions you have been kind enough to tell us about. Without your help, truly, this book could not have been written., McCall's Cook Book (1963)

Verified: no
Solve time: 5m03s

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}}$