Existence of Integer $C$

B.M Stewart published a series of proofs in a 1960 article ([3]) which are of significant theoretical value, but have little practical impact in searching for PDIs. However, they are quite useful in search for Recurring Digital Invariants, which are similar to Perfect Digital Invariants, except that the exponentiation/summation process may be repeated on a number several times. His proofs require the following definitions:

• Let $B \geq 2$ be the base of enumeration
• Let
  
  $$A = a_{k}'B^{k} + \sum_{0}^{k-1}a_{i}B^{i},$$
  
  
  where $a_{i}$ is restricted to the subset $0,1, 2, \ldots, B-1$, and $a_{i}'$ is restricted to the subset $1,2,\ldots,B-1$ (ie the first digit of the number can't be 0)
• Let $P(a)$ be any function which is defined for all values $0,1, 2, \ldots, B-1$ and whose range is the integers.
• Let
  
  $$F(a) = P(a), F(A) = P(a_{k}') + \sum_{0}^{k-1}P(a_{i})$$
  
  

The first thing he shows is that for any function $P(a)$, there exists an integer $C$ such that $F(C) \geq C$ and $F(A) < A$ for every $A > C$. Thus, when checking for PDIs of a particular order (as opposed to a number of digits), you only need to check numbers up to $C$. His proof proceeds as follows:

Theorem: To any real $\epsilon > 0$ there corresponds an integer $C = C(\epsilon)$ such that $\vert F(C)\vert \geq \epsilon C$ and such that $\vert F(A)\vert < \epsilon A$ for every $A > C$.

Proof: Let $P$ be the maximum value of $\vert P(a)\vert$. This value is guaranteed to exist, because there are only a finite number of values that $a$ can be. Since $B^{k}/(k+1)$ is increasing and unbounded for $k = 0,1,2,\ldots,$ there exists $K = K(\epsilon,P)$ such that $B^{k}/(k+1) > P/\epsilon$ when $k > K$. Therefore, $\epsilon B^{k} > P(k+1)$. If $B^{k} \leq A < B^{k+1}$, then $\vert F(A)\vert \leq (k+1)P$ (number of digits times the maximum of $P$). But, $(k+1)P < \epsilon B^{k} \leq \epsilon A$ for all $k > K$. Since $\vert F(0)\vert \geq 0$, $C$ exists, and $0 \leq C < B^{k+1}$.

He then proceeds to give an algorithm for finding $C$, and several proofs about the growth of $F(A)$. Since his algorithm for $C$ isn't directly useful in searching for PDIs, it will only be described informally:

• Calculate the maximum number of digits that can be in a number before $F(A) < A$
• Starting with the most significant digit and working your way to the right, calculate the maximum value that each digit can be such that $F(A) < A$ until all digits have been maximized.

His proofs about $F(A)$ require the use of many auxillary definitions and restating them all here would mean virtually copying his paper verbatim. However, he does conclude with two theorems, which will be presented with minimal explanation here, but are proven thoroughly in his article.

Theorem: If $P(A) = a^{t}, t > 1, B > 2$, then $C < (t-1)B^{t}$. If $B > T = (1 - (1 - t^{-1})^{1/t})^{-1}$ (which includes all $B \geq t^{2}$) then $C = (t-1)B^{t} - 1$.

He proves this by contradiction, using earlier an earlier theorem to show that if $C > (t-1)B^{t}$, then $F(C) < C$, which contradicts one of the defining properties of $C$.

Theorem: For $P(a) = a^{t}, t > 1, B > 2, C$ has the property that $c_{i} = B - 1$ for $i < J$; and either $c_{i} = B - 1$ or $c_{i} \leq t -2$ for $J \leq i \leq S$.

In this theorem, $S$ and $J$ are auxillary constants that are calculated during the execution of his algorithm for finding $C$. $S$ is the number of digits in $C$, and $J$ is defined by $B^{j - 1} \leq R \leq B^{j}$, where $R$ is the maximum value of $(P(a') - P(0)) / a'$. So, once you have calculated $S$ and $J$, this theorem provides a direct way to calculate $C$ without any of the conditions of the previous theorem.