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. 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 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. 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 and
(2) neither k−1 nor k+1 is divisible by 5.
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 the base is not
without nontrivial PPDIs. 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
By Theorem 13, then, 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
By Theorem 14, there exists a nontrivial
PPDI in base-b.
Every other case is covered by Corollary 1.
Q.E.D.
Corollary 2 tells us a bit more than
does Corollary 1, though it still leaves some bases without proven
PPDIs. Some clarification will be helpful, particularly as Corollary 2
is somewhat oddly stated.
First, we can say that all bases other than
those that are multiples of 18 contain non-trivial PPDIs. Only bases
that are multiples of 18 need be considered further.
If a base can be written as 18k2 or
36k2, it too, contains at least one non-trivial PPDI.
Unfortunately, as k increases, successive instances of such bases
become arbitrarily far apart, a fact that is little help in showing that
all bases contain non-trivial PPDIs.
Corollary 2 retains gaps in bases with
proven nontrivial PPDIs. Most bases seem to have order-2 or order-3
PPDIs that offer some potential for closing some of those gaps with
theorems. On the other hand, the smallest base-90 PPDI is of order 8 and
that of base-270 is also of order 8. Larger, untested bases may contain
similarly long PPDIs or perhaps even none at all. In any case, Winter
has shown that no base between 2 and 1000 lacks nontrivial PPDIs. In the
hope that it can eventually be proved, I formally state my previously
mentioned 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
15. 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. |
