TAOCP 7.2.2 Exercise 37

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

Section 7.2.2: Backtracking

Exercise 37. ▶ [**] [M30] (W. L. Eastman, 1965.) The following elegant construction yields a commafree code of maximum size for any odd block length $n$, over any alphabet. Given a sequence $x = x_0 x_1 \ldots x_{n-1}$ of $n$ nonnegative integers, where $x$ differs from each of its other cyclic shifts $x_k \ldots x_{n-1} x_0 \ldots x_{k-1}$ for $0 < k < n$, the procedure outputs a cyclic shift $\sigma x$ with the property that the set of all such $\sigma x$ is commafree.

We regard $x$ as an infinite periodic sequence $(x_t)$ with $x_t = x_{t \bmod n}$ for all $t \ge 0$. Each cyclic shift then has the form $x_k x_{k+1} \ldots x_{k+n-1}$. The simplest nontrivial example occurs when $n = 3$, where $x = x_0 x_1 x_2 x_0 x_1 x_2 x_0 \ldots$ and we don't have $x_0 = x_1 = x_2$. In this case the algorithm outputs $x_{s} x_{s+1} x_{s+2}$, where $x_s \ge x_{s+1} < x_{s+2}$; and the set of all such triples clearly satisfies the commafree condition.

One key idea is to think of $x$ as partitioned into $t$ substrings by boundary markers $b_j$, where $0 \le b_0 < b_1 < \cdots < b_{t-1} < n$ and $b_j = b_{j-t} + n$ for $j \ge t$. Then substring $y_j$ is $x_{b_j} x_{b_j+1} \ldots x_{b_{j+1}-1}$; the number $l$ of substrings is always odd. Initially $t = n$ and $b_j = j$ for all $j$; ultimately $t = 1$, and $\sigma x = y_0$ is the desired output.

Eastman's algorithm is based on comparison of adjacent substrings $y_{j-1}$ and $y_j$. If those substrings have the same length, we use lexicographic comparison; otherwise we declare that the longer substring is bigger.

The second key idea is the notion of "dips," which are substrings of the form $z = z_1 \ldots z_k$ where $k \ge 2$ and $z_1 \ge \cdots \ge z_{k-1} < z_k$. It's easy to see that any string $y = y_0 y_1 \ldots$ in which we have $y_j < y_{j+1}$ for infinitely many $j$ can be factored into a sequence of dips, $y = z^{(0)} z^{(1)} z^{(2)} \ldots$, and this factorization is unique. For example,

$$31415926535897923836264383\ldots = 314\ 15\ 926\ 535\ 89\ 79\ 23\ 8\ 40\ 26\ 4383\ 8\ \ldots$$

Furthermore, if $y$ is a periodic sequence, its factorization into dips is also ultimately periodic, although the number of actual factors may not be what you expect. For example,

$$12344355012344355012344355\ldots = 12\ 34\ 4\ 35\ 5\ 01\ 23\ 4\ 4355\ 01\ 23\ 4435\ldots$$

Given a periodic, nonconstant sequence $y$ described by boundary markers as above, where the period length $l$ is odd, its periodic factorization will contain an odd number of odd-length dips. Each round of Eastman's algorithm simply retains the boundary points at the left of those odd-length dips. Then $t$ is reset to the number of retained boundary points, and the next round begins if $t > 1$.

a) Play through the algorithm by hand when $n = 19$ and $x = 3141592653589793238$.

b) Show that the number of rounds is at most $\lfloor \log_2 n \rfloor$.

c) Exhibit a binary $x$ that achieves this worst-case bound when $n = 3^k$.

d) Implement the algorithm with full details. (It's surprisingly short!)

e) Explain why the algorithm yields a commafree code.

Verified: no
Solve time: 5m10s

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