TAOCP 7.2.1.2 Exercise 33

Section 7.2.1.2: Generating All Permutations

Exercise 33. [25] [25] Continuing the previous exercise, find all positive integers less than 150 that (a) cannot be represented in such a fashion; (b) have a unique representation.

Verified: no
Solve time: 1m33s

Solution

Let the digits ${1,2,\dots,9}$ be arranged in some permutation, and let two cuts and a division sign be inserted to form an expression of the form

$A + \frac{B}{C},$

where $A,B,C$ are positive integers formed by concatenating disjoint subsets of the digits, each digit used exactly once. The exercise from the previous part requires determining all integers $N < 150$ that can be written in this form, and identifying those $N$ with a unique representation.

The key structural restriction is that the value of the expression must be an integer. Since $A$ is an integer, this forces $\frac{B}{C}$ to be an integer as well, hence $C \mid B$ in the sense of integer divisibility after concatenation. Writing $B = kC$ with $k \in \mathbb{Z}_{>0}$, the expression simplifies to

$A + k.$

Thus every admissible representation corresponds to a partition of the digits into three disjoint blocks $(A,B,C)$ such that $B = kC$ as integers, and the resulting value is $N = A + k$.

This reduces the problem to a finite search over all permutations of ${1,\dots,9}$ together with all placements of the two separators. For each configuration, one forms the integers $A,B,C$, checks the divisibility condition $C \mid B$, and records $N = A + B/C$.

Algorithmically, this is most directly handled using Algorithm P (plain changes) to generate all $9!$ permutations, and for each permutation testing all $\binom{8}{2}$ ways to place the two separators. This produces a finite set of valid triples $(A,B,C)$, from which the multiset of val