An Interesting Family of Iterated Sequences

Before you read this:

For a better writeup, read An Introduction to Digit Product Sequences, to appear in the Journal of Recreational Mathematics in 2004 (its in .ps format).

I. History

In the fall of 1989, I was a sophomore at Wabash College. During an uninspiring lecture, I found myself trying to come up with an integer sequence with interesting - whatever that may mean - properties. I eventually found one that interested me, so I spent hours filling up page after notebook page with this sequence. At some point, I noticed a mistake pages earlier. When I redid the calculations, I found it really didn't matter - I eventually ended up with the same sequence. Since then, I spent some of an REU working on it and came back to it from time to time during graduate school and now as an assistant professor. I am not a number theorist by training, so I have not yet done any serious number theory with it.

II. The Iterated Function

Let n be a positive integer, written in base 10. Then define

f(n) = n + (the product of the nonzero digits of n).

Then, beginning with any positive integer, by iterating f we create an increasing sequence of integers. For example, with n=1, we have

1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, 162, 174, 202, 206, 218, 234, 258, 338, 410, 414, 430, 442, 474, 586, 826, 922, 958, 1318, 1342, 1366, ...

For example, at 26 we add (2)(6)=12 to obtain 38; at 102 we ignore the 0 and add (1)(2).

III. Sequences That Join

Life becomes more interesting when we look at sequences beginning with other integers. Beginning with 3, we have

3, 6, 12, 14, 18, 26, 38, 62, 74, 102, ...

Note that once we hit 26, we are in the sequence given in section II. Here are some more sequences, each shown only until they join a previously displayed sequence:

5, 10, 11, 12, ...
7, 14, ...
9, 18, ...
13, 16, ...
15, 20, 22, ...
17, 24, 32, 38, ...
19, 28, 44, 60, 66, 102, ...
21, 23, 29, 47, 75, 110, 111, 112, 114, 118, 126, ...

In 1989 I conjectured that for all positive integers n, the sequence beginning with n eventually joins the sequence beginning with 1. In 1991 I wrote a simple C program and checked that for all n up to 1,000,000, this is true. The first "stubborn" sequence is 63, 81, 89, 171, ... which takes 321 iterations to join the main sequence. In other words,

f^³²²(63)=f^²⁶¹(1)=150,056.

IV. Other Bases and p(n)

A similar phenomenon occurs in other bases. In base 2 the above conjecture is trivial:
1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, ...

But in base 3,
(written in base 3 notation:)
1, 2, 11, 12, 21, 100, 101, 102, 111, 112, 121, 200, 202, 220, 1001, 1002, 1011, 1012, 1021, 1100, 1101, 1102, 1111, ...
10, 11, ...
20, 22, 110, 111, ...
120, 122, 210, 212, 1000, 1001, ...
201, 210, ...
211, 220, ...
221, 1002, ...
222, 1021, ...
1010, 1011, ...
1020, 1022, 1110, 1111, ...

in base 10 notation this is
1, 2, 4, 5, 7, 9, 10, 11, 13, 14, 16, 18, 20, 24, 28, 29, 31, 32, 34, 36, 37, 38, 40, ...
3, 4, ...
6, 8, 12, 13, ...
15, 17, 21, 23, 27, 28, ...
19, 21, ...
22, 24, ...
25, 29, ...
26, 34, ...
30, 31, ...
33, 35, 39, 40, ...

Note that in base 3, all sequences beginning at less than 40 eventually "pass through" 40. With this in mind, for a fixed base b, define
p(n) = the number of positive integers less than or equal n whose sequences pass through n.
In base 2, p(n)=n for all n. In base 3, p(n)=n for n=1, 4, 5, 13, 14, 40, 41, 121, 122, 364, 365,... One can show by induction that p(n)=n for any number consisting of all ones in base 3; that is, a number of the form 1 + 3 + 3^² + 3^³ + ... + 3^{^k-1}, or (3^{^k}-1)/2.
It is then natural to ask: Given a base b, what is limsup p(n)/n as n goes to infinity?

V. Unattainables

Note that the numbers that begin all the above sequences are numbers that do not occur in any other sequence; that is, n for which f(m)=n has no solution m. We label these numbers unattainables, and ask How many unattainables are there?

We define u(n)= number of unattainables less than or equal n.
In base 2, of course, u(n)=1 for any n. In all bases greater than 2, if the conjecture that all sequences join is true, then there must be infinitely many unattainables. As the base increases (and sequences tend to move more quickly), the proportion of unattainables increases. In any base, the proportion seems to converge to some limit. In base 10, for example:

n	u(n)/n
10	.50000
50	.42000
100	.44000
500	.42600
1K	.42900
5K	.41800
10K	.40890
50K	.41336
100K	.39544
500K	.39851
1M	.39712

VI. More

There are many more interesting questions than those raised here. I'm working on LaTex-ing this and on adding more information here. If you are interested in hearing more, email me at ploomis@bloomu.edu.

visitors since 8.8.2001.
Back to PL's main page.