The persistence P(x) of an integer x is the number of times its digits can be multiplied, recursively.
arithmetic/digits/persistence New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
The persistence P(x) of an integer x is the number of times its digits can be multiplied, recursively. P(0..9) = 0 since you cannot multiply one digit; P(10) = 1 because 10 -> 1*0 = 0; P(467) = 4 because 467 -> 4*6*7 = 168 -> 1*6*8 = 48 -> 4*8 = 32 -> 3*2 = 6. 1. For every N, find the smallest x such that P(x) = N. 2. Is there a largest value of N? What about in different bases? For example, for base 2, max N = 1. What about base 3? 3. Given X, what percent of positive integers y <= 10^X are ordered such that each digit is greater than or equal to the digit immediately to the left? -- Gaku Sato <gaku.sato@leland.stanford.edu>
Show solution
This topic is discussed in section F25 of "Unsolved Problems in Number Theory", 2nd ed, by Richard K. Guy. The only reference is to the article "The persistence of a number", N.J.A. Sloane, J Recreational Math, 6(1973). 1. For N = 1..11, the least values are 10, 25, 39, 77, 679, 6788, 68889, 2677889, 26888999, 3778888999, 277777788888899, according to Guy. If there is a number with persistence 12 or greater, it has more than fifty digits. 2. Sloane conjectures that there is [Editor: a largest value]. After one step, any base 3 number becomes zero or a power of two. All powers of two from 2^16 to 2^500 are known to contain a zero in base 3; if, as is conjectured, all larger powers of two do as well, the maximum persistence in base 3 is 3. Sloane further conjectures that there is a maximum persistence for any given base. 3. This works out a little neater if we include zero and omit 10^X; then the question is equivalent to How many non-decreasing sequences of X digits are there (leading zeroes being allowed)? There's a standard combinatorial trick for this. Imagine you have a row of X+9 bins containing 9 objects, with no two objects in the same bin. As you walk by the bins, keep a count of the objects. Each time you encounter an empty bin, write down the current count. Since there are X empty bins, you'll be writing down X non-decreasing digits. I hope it's clear that each arrangement of objects in the bins corresponds to one such sequence of digits, and vice versa. But the number of ways to put 9 objects in X+9 bins is simply (X + 9)!/(X! * 9!). Now you can use Stirling's formula to approximate the percentage. -- Fred W. Helenius <fredh@ix.netcom.com>