Proof of Finiteness

One of the most important statements about PPDIs is a proof by B. L. Schwartz that for base 10, the largest order for a possible PPDI is 60. This is significant because it makes it possible to definitively search for and find every PPDI in base 10. Furthermore, the proof can be generalized to show that a similar limit exists for numbers in any base. Therefore, to find all PPDIs in base 10, you only need to check all numbers from 1 to $10^{61} - 1$. Obviously that is still an extremely large task, but another observation given later will show how to reduce it so that a computer search is feasible. Schwartz's proof follows (see reference [2] for the complete article; there is a typographical error in the second step of the induction in the original however! Also, he uses the term PDI to refer to PPDIs as defined above):

Lemma 1: If $m > 9$, then $(10/9)m > m + 1$

$$\begin{eqnarray*} \emph{Proof}: m & > & 9, 10m & > & 9m + 9 = 9(m + 1), (10/9)m & > & m + 1 \end{eqnarray*}$$

Lemma 2: If $m \geq 61$, then $10^{m - 1} > m9^{m}$

Proof: By induction. Base case $m = 61$:

$$\begin{eqnarray*} \log(m9^{m}) & = & \log(61\times9^{61}) & = & \log61 + 61... ...0.9543) \\ & = & 59.9977 < 60 = \log(10^{60}) = \log(10^{m-1}) \end{eqnarray*}$$

Inductive step: assume $10^{m-1} > m9^m$

$$\begin{eqnarray*} (10/9)^{m} & > & 10m (10/9)^{m+1} & > & 10 \times 9^{m-1}... ...m+1} & > & 10\times9^{m+1}(m+1) 10^{m} & > & (m+1)(9^{m+1}) \end{eqnarray*}$$

Theorem If $N$ is a PPDI, then $N < 10^{60}$.

Proof: Let $M$ be an integer whose decimal representation $d_{1}d_{2} \ldots d_{m}$ has $m$ digits, $m \geq 61, d_{1} \neq 0$. Let

$$S =\sum_{i = 1}^{m}d^{m}_{i}.$$

Now

$$S = \sum_{i = 1}^{m} d_{i}^{m} \leq \sum_{i = 1}^{m} 9^{m} = m9^{m} < 10^{m-1}, \mathrm{ by Lemma 2.}$$

But since $d \geq 1$, we have

$$M = \sum_{i = 1}^{m}d_{i}(10)^{m-i} \geq d_{i}(10)^{m-1} \geq 1(10)^{m-1} = 10^{m-1}.$$

Since $M > S$, $M$ cannot be a PPDI. Therefore, a base 10 PPDI can have no more than 60 digits.

As stated above, it is possible to generalize this theorem for any base. That is, for any base $B \geq 2$, there exists a number $L$ such that for $N$ to be a PPDI, $N < B^{L}$. This is done generally by replacing all occurences of '10' (the base in the above example) with $B$, and all 9's (which is the largest single digit in base 10) with B-1's (which is the largest single digit in base $B$) in the formulas above. This proceeds as follows:

Lemma 3: If $m > B - 1$, then $(\frac{B}{B-1})m > m + 1$

Proof:

$$\begin{eqnarray*} m & > & B - 1, Bm & > & (B-1)m + B - 1 = (B-1)(m + 1), (\frac{B}{B-1})m & > & m + 1 \end{eqnarray*}$$

Lemma 4: For any base $B \geq 2$, there exists a number $L$ such that if $m \geq L$, then $B^{m-1} > m(B-1)^{m}$.

Proof:

$$\begin{eqnarray*} \mathrm{assume } B^{m-1} & \geq & m(B-1)^{M} \\ \log_{B}(B... ...m) + 1 m & \geq & \frac{\log_{B}(m) + 1}{1 - \log_{B}(B-1)} \end{eqnarray*}$$

Now, $0 \leq \log_{B}(B-1) < 1$, so $1 - \log_{B}(B-1) < 1$. Let $D = \frac{1}{1 - \log_{B}(B-1)} > 1$.

$$\begin{eqnarray*} m & \geq & D\log_{B}m + D \frac{m - D}{\log_{B}m} & \geq & D \end{eqnarray*}$$

Convert to natural logarithms:

$$\begin{eqnarray*} \frac{m - D}{\frac{\ln m}{\ln B}} & \geq & D \frac{(\ln B)(m - D)}{\ln m} & \geq & D \end{eqnarray*}$$

L'Hôpital's Rule verifies that

$$\lim_{m \rightarrow \infty} \frac{(\ln B)(m -D)}{\ln m} = \infty .$$

Therefore, some number $L$ exists such that

$$\frac{(\ln B)(m - D)}{\ln m} \geq D .$$

Since this number exists, our assumption in the first step therefore holds for any value of $m$ that makes the above equation true, and thus $L$ can equal any such value of $m$.

Theorem: If $N$ is a PPDI, then $N < B^{L-1}$.

Proof: Let $M$ be an integer whose base-$B$ decimal representation $d_{1}d_{2} \ldots d_{m}$ has $m$ digits, $m \geq L$, $d_{1} \neq 0$. Let

$$S = \sum_{i = 1}^{m}d_{i}^{m}.$$

Now

$$S = \sum_{i = 1}^{m}d_{i}^{m} \leq \sum_{i = 1}^{m}(B-1)^{m} = m(B-1)^{m} < B^{m-1}, \mathrm{ by Lemma 4}.$$

But since $d_{i} \geq 1$, we have

$$M = \sum_{i=1}^{m}d_{i}(B)^{m-i} \geq d_{i}(B)^{m-1} \geq 1(B)^{m-1} = B^{m-1}.$$

Since $M > S$, M cannot be a PPDI. Therefore, a PPDI in base $B$ can have no more than $L-1$ digits.

In his paper, Schwartz also demonstrates how to prove that there are no base-10 PPDIs which have 60 digits. This proof is quite tedious, and adds little overall value to easing the search for PPDIs; therefore it will not be shown in its entirety. However, the first two steps of his proof will be given because they introduce a concept which was used in my Meta-program that searches for PPDIs, namely restricting the search based on the number of 9s (more generally, $B-1$ digits) that must and/or can appear in a number for it to be a PPDI.

Let $M$ be an integer of 60 digits with decimal representation $d_{1}d_{2} \ldots d_{60}, d_{1} \neq 0$. Let

$$S = \sum_{i = 1}^{60}d_{i}^{60}.$$

Let $k$ be the number of the $d_{i}$ which are 9's.

Part 1: If $k \leq 55$, then $M$ is not a PPDI.

Proof: $S \leq 55(9^{60}) + 5(8^{60}) < 9.881 \times 10^{58} < 10^{59} \leq M$.

Part 2: If $M \geq 1.08 \times 10^{59}$, then $M$ is not a PPDI.

Proof: $S \leq 60(9^{60}) < 1.08 \times 10^{59} \leq M$.

He continues the proof by further refining the statements about the number of nines in the potential PPDI until he reduces it to one single possibility, which he then demonstrates is not in fact a PPDI.