This next theorem is of a somewhat different character. Theorem
9. Let p = { a }{ c } be a base-b PPDI. Then {
b-a }{ c } is also a base-b PPDI. Proof.
Since p is a PPDI, we know that ab +
c = a2 + c2 Adding to both
sides of this equality gives ab +
c + (b2 −2ab) = a2 +
c2 + (b2 −2ab)
Rearranging terms yields (b2
−ab) + c = (b2
−2ab+a2) + c2
(b−a) b + c = (b−a)2
+ c2, which implies that {
b−a }{ c } is a base-b PPDI. For example,
123 and 223 are base‑3 PPDIs.
Q.E.D.
Theorem 9 has two obvious deficiencies.
First, it does not identify order-2 PPDIs in any particular base. From
the tables shown earlier, we know that there are
bases with and bases without order-2 PPDIs. (There are two-digit base-3
PPDIs but no two-digit base-10 PPDIs.) Second, Theorem 9 does not assure us that
the pairs of two-digit PPDIs whose existence is asserted are, in fact,
distinct. Notice that, if { b/2 }{ c } is a base-b PPDI, then the
theorem merely says that { b/2 }{ c } is a PPDI, in
which case, there would not exist a pair of distinct PPDIs. We
now show that this case does not occur and therefore that the paired
PPDIs of Theorem 9 are distinct. Theorem
10. { b/2 }{ c } is not a PPDI in any base b.
Proof.
Assume the contrary, namely, that { b/2 }{ c } is a PPDI
in some base b. Then we must have (b2/2)
+ c = (b2/4) + c2
b2/4 = c2−c
b/2 = (c2−c)1/2
b/2 = ( c (c−1) )1/2 Because b/2
and c are both base-b digits, they must be integers. This means that the right side of the above equation must be
an integer as well. The square
root of c (c−1) is clearly less than c. By the
same token, the square root must be greater than c−1. But there
are no integers between c and c−1. Therefore, our
assumption that { b/2 }{ c } is a base-b PPDI must
be incorrect. Q.E.D.
Theorem
11. The number p = dn-1dn-2 … d11 is an
order-n PPDI in base b if and only if p´ = dn-1dn-2
… d10 is also an order-n PPDI in base b.
Proof. By the
definitions given earlier, p is a base-b PPDI when
Pb(p) = Sn(p)
If the low-order digit of p is 1, its contribution to the sum Pb(p)
is 1. Its contribution to the sum Sn(p) is 1n,
which is also 1. Similarly, if we substitute 0 for the low-order digit
(i.e., if we consider p´), the final digit again contributes the
same (0) to both sums. Thus, any PPDI ending in 1 or 0 implies the
existence of another PPDI that is identical except for ending in 0 or 1.
For example, both 370 and 371 are base-10 PPDIs.
Q.E.D.
We now collect what we know about the distribution of PPDIs so far in the
following corollary.
Corollary
1. There is at least one nontrivial PPDI in every base b >
2, except possibly where b = 18k and k is not a perfect
square.
Proof. By Theorem 1, every odd base
contains an order-2 PPDI. This leaves only the even bases, beginning
with 4, to be considered.
Let i be a non-negative integer and consider even numbers in base
b. These can always be represented as 18i +
n, where n > 2 is even.Our proof proceeds by cases.
Case 1. b = 18i + 4.
We can write b as 3 (6i + 1) + 1 = 3k + 1, where
k = 6i + 1. By Theorem 2, therefore, base-b contains a
non-trivial PPDI.
Case 2. b = 18i + 6.
It follows directly from Theorem 4 that base b contains a
non-trivial PPDI, where i = k.
Case 3. b = 18i + 8.
We can write b as 3 (6i + 2) + 2 = 3k + 2, where
k = 6i + 2. By Theorem 3, therefore, base-b contains a
non-trivial PPDI.
Case 4.: b = 18i + 10.
We can write b as 3 (6i + 3) + 1 = 3k + 1, where
k = 6i + 3. Like Case 1, this case is covered by Theorem 2.
Case 5. b = 18i + 12.
It follows directly from Theorem 5 that base b contains a
non-trivial PPDI, where i = k.
Case 6. b = 18i + 14.
We can write b as 3 (6i + 4) + 2 = 3k + 2, where
k = 6i + 4. Like Case 3, this case is covered by Theorem 3.
Case 7. b = 18i + 16.
We can write b as 3 (6i + 5) + 1 = 3k + 1, where
k = 6i + 5. As in Case 1, this case is covered by Theorem 2.
Case 8. b = 18i + 18 = 18 (i + 1).
This may look a bit odd, but we are interested only in positive
multiples of 18, i.e., bases 18, 36, etc. By Theorem 6, we know
that base b has a non-trivial PPDI if (i + 1) is a
perfect square. We have proved nothing about other bases that are
multiples of 18. (See more on this below.)
Case 9. b = 18i + 20.
We can write b as 3 (6i + 6) + 2 = 3k + 2, where
k = 6i + 6. As in Case 3, this case is covered by Theorem 3.
Case 10. b = 18i + j, where j ≥ 22
and j is even.
We can write j as 18l + m, where l ≥ 1 and
0 ≤ m ≤ 20. Thus, b = 18 (i + l)+ m,
which reduces to one of the cases above.
Q.E.D.
Corollary 1 seems
really odd. Is there something special about bases that are multiples of
18? The exceptions in Corollary 1 have bothered me for years. I conjecture that all bases above 2 contain nontrivial PPDIs. Even if my
conjecture is correct, however, proving it may be difficult. The theorems on
which the corollary is based
rely on two- and three-digit PPDIs A different approach is likely needed to
prove that all bases contain significant PPDIs. For example, Dik Winter of
Centrum voor Wiskunde en Informatica in Amsterdam discovered that the
smallest non-trivial PPDI in base-90 (i.e., base-18k, where k = 5)
is {73}{62}{15}{62}{83}{18}{39}{47}. (Dik Winter has
provided a brief discussion of
“Armstrong numbers,” a.k.a. PPDIs, and two interesting tables of such
numbers. These can be found here.)
Of course, there might be an existence proof for the conjecture that does not
actually identify the numbers that make the conjecture true, but it is not at
all clear what such a proof might look like. Alternatively, there may
actually be bases without multi-digit PPDIs, but it is equally unclear
how to approach proof of this conjecture.
Mike
Keith and I have eliminated some of the restrictions of Corollary 1.
What follows has resulted from our collaboration: Theorem
12. There is at least one nontrivial PPDI in every base b =
36k2, where k = 1, 2, … .
Proof. { 12k2−4k }{ 24k2−2k }{ 1 }
is a PPDI in base b = 36k2. Thus, {8}{22}{1} is a
base-36 PPDI, {40}{92}(1} is a base-144 PPDI, etc. (Admittedly, varifying proofs
such as this is tedious!)
Q.E.D. Theorem
13. There is at least one nontrivial PPDI in every base b =
90k+18, where k = 0, 1, … . Proof. { 18k+4 }{ 36k+8 }
is a PPDI in base b = 90k+18. Thus, {4}{8} is a base-18 PPDI,
{22}{44} is a base-108 PPDI, etc. Q.E.D. Theorem
14. There is at least one nontrivial PPDI in every base b =
90k+72, where k = 0, 1, … . Proof. { 18k+14 }{ 36k+29 }
is a PPDI in base b = 90k+72. Thus, {14}{29} is a base-72
PPDI, {32}{65} is a base-162 PPDI, etc. Q.E.D. Theorem
15. There is at least one nontrivial PPDI in every base b = 18k,
where k = 13 + 17m, for
m = 0, 1, … .
Proof. { 14 + 18m } { 56 +
72m } is a PPDI in base-18 (13 +17m). Thus, we have
order-234 PPDI {14 }{ 56 }, order-4824 PPDI { 284 }{ 1136 }, etc. Q.E.D. Now we are ready to improve
upon Corollary 1. Originally, I wrote that we could “easily prove” Corollary 2
from earlier theorems. Perhaps a proof is not so obvious, so I have
added one. Corollary 2. There is at least one nontrivial PPDI in every
base b > 2,
except possibly where b = 18k and all the following are
true: (1) k is neither a perfect square nor twice a perfect square,
(2)neither k−1 nor k+1 is divisible by 5, and k ≠
13 + 17m, for m ≥ 0.
Proof. In base b = 18k,
where k is a perfect square, Theorem 6 assures us that there is a
nontrivial PPDI in that base. In base b = 18k, if
k is twice a perfect square, say 2j2, we can write b as
18(2j2 ) = 36j2. Then Theorem 12 asserts that
there is at least one nontrivial base-b PPDI. In base b = 18k, assume that
k−1 = 5m for some integer m, i.e., k−1 is
divisible by 5. Then
18k = 18( 5m+1 )
= 90m
+ 18
Then, Theorem 13 asserts that there is at
least one nontrivial base-b PPDI.
In base b = 18k, assume that
k+1 = 5m for some integer m, i.e., k+1 is
divisible by 5. Then
18k = 18( 5m−1 )
= 90m − 18
= 90( m−1 ) + 90 − 18
= 90( m−1 ) + 72
Then, Theorem 14, there exists a nontrivial PPDI in base-b.
In base b = 18k, if k = 13 + 17m
for some m, then by Theorem 15, there is at least one nontrivial
base-b PPDI.
Every other case is covered by Corollary 1.
Q.E.D.
Corollary 2 improves somewhat over
Corollary 1, but many bases remain without analytically proven PPDIs. It
is curious that all the bases in which the existence of PPDIs is
unproven are multiples of 18. Why 18? It is equally curious that
Winter’s list of PPDIs consists almost exclusively of order-2 and
order-3 numbers, but bases 90 and 270 contain only remarkably longer
PPDIs. He found PPDIs in all bases up to 1000, which suggests the
following conjecture:
Conjecture. Every base b > 2 contains
nontrivial PPDIs (i.e., PPDIs two or more digits long). Finally,
Mike was able to prove another theorem that does little to close the existence
gap, but which is interesting for its own sake: Theorem
16. Let t be the nth triangular number, n >
1. (The triangular numbers are those representing the number of objects needed
to form a triangle like that formed by bowling pins. The first triangular number
is 1, the second—reflecting a row of 1 object and a row of 2 objects—is 3,
etc. In the case of bowling, i.e., tenpins, there are four rows of 1, 2, 3, and
4 pins. The 4th triangular number is 10.) If t is a square
triangular number, let its square root be r. Then number {r}{r}{0}
is a PPDI in base n. Proof. {r}{r}{0}
represents the value rn2 + rn = r (n2
+ n). Since the formula for the nth triangular number t
is (n2 + n)/2, however, and since, by
assumption t = r2, we may write this as 2r3.
But, of course, the sum of the cubes of the digits of {r}{r}{0} is
also 2r3, so {r}{r}{0} is, by definition, a PPDI.
Q.E.D.
Square triangular numbers are rather sparse. The first two PPDIs whose existence
is asserted by the theorem are 6608 and {35}{35}{0}49. |