DEAN MORROW
WASHINGTON & JEFFERSON COLLEGE
dmorrow@washjeff.edu
The main results of this paper (Propositions 1 and 2) will appear
in The Journal of Recreational Mathematics, so the proof of
Proposition 1 will be omitted here.
Let n be a positive integer with base-10 representation:
where the di's are the digits of n.
For each positive integer k, define a function gk on n as the sum
of the di powers of k:
The gk's are the family of digit functions referred to in the
title. Other families of digit functions have been studied and
will be mentioned briefly later. The primary question of our
investigation will be: What happens when we iterate gk on n?
For example let k = 2 and n = 467. Then
g2(467) = 24 + 26 + 27 = 208
g2(208) = 22 + 20 + 28 = 261
g2(261) = 22 + 26 + 21 = 70
g2(70) = 27 + 20 = 129
g2(129) = 21 + 22 + 29 = 518
g2(518) = 25 + 21 + 28 = 290
g2(290) = 22 + 29 + 20 = 517
g2(517) = 25 + 21 + 27 = 162
g2(162) = 21 + 26 + 22 = 70.
So, after 3 iterations of g2, the integer n = 467 enters the
6-cycle (70,129,518,290,517,162).
If k = 3 and n = 278, then
g3(278) = 32 + 37 + 38 = 8757
g3(8757) = 38 + 37 + 35 + 37 = 11178
g3(11178) = 31 + 31 + 31 + 37 + 38 = 8757.
So, after 1 iteration of g3, the integer n = 278 enters the 2-cycle (8757,11178).
Of particular interest are the 1-cycles (or fixed points) of the
gk's. For example, with k = 3 and n = 221,
g3(221) = 32 + 32 + 31 = 21
g3(21) = 32 + 31 = 12
g3(12) = 31 + 32 = 12.
So, after 2 iterations of g3, the integer n = 221 reaches the
1-cycle (12).
It turns out that for any integer n, with a sufficient number of
digits, gk(n) < n. This implies that, under repeated iteration
of gk, every integer n must eventually enter a cycle.
PROPOSITION 1. Let m be the number of base-10 digits of n. If
m > B, then gk(n) < n, where
B = [(1 + 9logk)/(1 - c)] (*)
with the brackets representing the greatest integer function and
c = (loge)/e.
We are interested in the eventual cycle destination of the
sequence gk(n), gk2(n), gk3(n), ... . Proposition 1 shows that
eventually this sequence will reach a point where gki(n) will
have no more than B digits, where B is defined in (*).
Consequently, we will only need to know the effect of repeated
iteration of gk on integers with no more than B digits.
COROLLARY 1. To find the cycles of the digit functions gk, it is only necessary to find the cycle destinations of integers n with no more than B digits, where B is defined at (*). In particular, we have:
k 1 2 3 4 5 6 7 8 9 10
-----------------------------------------------------
B 1 4 6 7 8 9 10 10 11 11
THE COMPUTER PROGRAM
Since the order of the digits of n does not affect the value of
the digit function gk, one only needs to consider unordered sets
of digits with repetitions allowed. In an 11 digit search, this
reduces the number of cases from 100,000,000,000 to 352,715 -- a
critical savings.
The function is iterated on a starting set of digits, extracting
a new set of digits at each step and checking to see if one of
the known cycle destinations has been reached. After 200
iterations, if no known cycle destination is reached, the current
value is printed out for further investigation. If necessary,
new cycle destinations are added to the program.
PROPOSITION 2. If 1 <= k <= 10, the ultimate destination of any
base-10 integer n under repeated iteration of the function gk is
one of the cycles represented below. The complete cycle can be
obtained by iterating gk on the given cycle representative (rep).
Cycle Cycle Cycle Cycle
k Length Rep k Length Rep
-------------------------- ---------------------------
1 1 1 7 1 13,177,388
-------------------------- 7 4 6,002,858
2 2 148 7 44 19,260
2 5 98 ---------------------------
2 6 70 8 1 1,033
2 15 5 8 2 41,498
-------------------------- 8 3 19,402,896
3 1 12 8 4 299,593
3 2 8,757 8 9 41,561
3 13 54 8 18 66,250
3 13 118 8 22 4,747
3 14 32 8 88 5,696
-------------------------- --------------------------- 4 1 4,624 9 1 10
4 1 595,968 9 4 96,788,601
4 4 5,268 9 10 6,669
4 15 36,929 9 13 43,119,713
-------------------------- 9 23 185,897
5 1 3,909,511 9 24 597,080
5 2 1,959,655 9 61 605,161
5 3 81,886 9 91 60,185
5 3 1,954,031 ----------------------------
5 6 17,031 10 2 21
5 20 81,902 10 6 22
-------------------------- ----------------------------
6 2 49,473
6 2 1,967,408
6 14 55,800
6 50 9,338
--------------------------
FREQUENCY OF CYCLE OCCURRENCE
During the execution of the computer program, one can keep track
of the "frequency of occurrence" of each cycle destination in the
following sense. The program is executed on unordered sets of up
to B digits (with repeated digits permitted), so it can keep
track of how many of these sets reach each cycle destination
under repeated iteration of gk.
Some examples:
Cycle Cycle
k B Length Rep Frequency
-----------------------------------------------------------
4 7 1 4,624 12
1 595,968 2
4 5,268 7,610
15 36,929 11,824 19,448
-----------------------------------------------------------
5 8 1 3,909,511 11
2 1,959,655 704
3 81,886 118
3 1,954,031 23,898
6 17,031 366
20 81,902 18,661 43,758
-----------------------------------------------------------
8 10 1 1,033 1
2 41,498 29
3 19,402,896 54
4 299,593 1,612
9 41,561 186
18 66,250 2,304
22 4,747 1,002
88 5,696 179,568 184,756
-----------------------------------------------------------
OTHER DIGIT FUNCTIONS WHOSE CYCLES HAVE BEEN INVESTIGATED
p(n) = the product of the digits of n
e.g. p(432) = 4x3x2 = 24
fk(n) = the sum of the kth powers of the digits of n
e.g. f3(432) = 43 + 33 + 23 = 99
f(n) = the sum of the factorials of the digits of n
e.g. f(432) = 4! + 3! + 2! = 32
g(n) = the sum of the digit-to-digit powers of n
e.g. g(432) = 44 + 33 + 22 = 287
Note: These investigations can be (and some have been) done in
other bases using base-b digits of the integer in the various
functions and extracting the base-b digits of the result.
References:
These papers contain other related references:
D.C. Morrow, Variations on Perfect Digital Invariants, J.
Recreational Mathematics, 27:1, pp. 9-12, 1995.
D.C. Morrow, Recurring Digit-to-Digit Invariants, J. Recreational
Mathematics, 27:2, pp. 154-156, 1995.