Order - 2 PPDIs

Even without the aid of computers, several interesting facts have been proven about PPDIs. For instance, it can be shown that in base 10, no number is equal to the sum of its digits squared, and that in fact there can only exist an order-2 PPDI for bases that meet certain criteria. The first step in this is to show that for any arbitrary base $B$, a number that is equal to the sum of its digits squared must contain no more than 2 digits. This was posed as part of a problem in a 1964 issue of American Mathematical Monthly ([8,10]), and the solution given is as follows (with missing steps added for clarity):

Consider the problem for an arbitrary base $b \geq 2$. Let $N = a_{0} + a_{1}b + a_{2}b^{2} + \cdots + a_{n}b^{n}$, with $0 \leq a_{i} <b, 0 <a_{n}$. If $n \geq 2$ (that is, the number has 3 or more digits), then $N$ cannot equal the sum of its digits squared. This is shown by contradiction below, assuming that $n \geq 2$, and that the number is equal to the sum of its digits squared:

$$\begin{eqnarray*} (b-1)b + 1 = b^{2} - b + 1 & \leq & a_{n}(b^{n} - a_{n}) N ... ...\\ b^{2} - b + 1 & \leq & b^{2} - 3b + 2 1 & \leq & -2(b - 1) \end{eqnarray*}$$

Since this is false for all $b \geq 2$, no number of three or more digits can be equal to the sum of its digits squared in any base.

Obviously, except for 1, no other single digit can equal itself squared. Therefore, a number in any base that is equal to the sum of its digits squared must have exactly two digits, and by definition be a PPDI. Using the definitions given above, if $n = 1$ and the number is a PPDI, then:

$$\begin{eqnarray*} a_{1}b + a_{0} & = & a_{1}^{2} + a_{0}^{2} a_{1}b - a_{1}^{... ... - b^{2} b^{2} + 1 & = & (2a_{1} - b)^{2} + (2a_{0} - 1)^{2} \end{eqnarray*}$$

Subramanian ([9]) uses this equation to derive an equation for calculating the number of order-2 PPDIs in a given base. First of all, the number of representations of $b^{2} + 1$ as the sum of two squares is known to be

$$4\sum_{t}(-1)^{(t-1)/2}$$

where $t =$ each positive odd divisor of $b^{2} + 1$.¹ If you assume that the base $b$ is odd, then $D_{o}(b)$, the number of order 2 PPDIs in base $b$ can be written using this formula as

$$D_{o}(B) = 2\left(\sum_{t}1\right) - 2.$$

Since $t = 1$ is an odd divisor of $B^{2} + 1$, if you restrict $t$ such that $1 < t < b^{2} + 1$, then you can rewrite the above formula as

$$D_{o}(B) = 2\sum_{t}1, 1 < t < B^{2} + 1.$$

Similarly, $D_{e}(B)$, the number of order-2 PPDIs in an even base, is:

$$D_{e}(B) = \sum_{t}1$$

This leads to the following theorem:

Theorem: In any given base $B$, the number $D(B)$ of order 2 PPDIs is given by $D(B) = \sum_{t}1$, where $t$ = all divisors of $B^{2} + 1$ such that $1 < t < B^{2} + 1$.

Proof: If $B$ is even, then $B^{2} + 1$ is odd, so all proper divisors of $B^{2} + 1$ will be odd, thus $D(B) = D_{e}(B)\sum_{t}1$ where $t$ = all proper odd divisors of $B^{2} + 1$. If $B$ is odd, then $B^{2} + 1 = 2p$, where $p$ is odd. If $A_{o} = \{p, t_{1}, \cdots,t_{n}\}$ is the set of proper odd divisors of $B^{2} + 1$, then $A_{e} = \{2, 2t_{1},\cdots,2t_{n}\}$ is the set of even divisors of $B^{2} + 1$. Since $A_{o}$ and $A_{e}$ have the same number of elements, the theorem follows from the equation given above for $D_{o}(b)$.