Limited persistence

There’s a numberphile video about the number 277,777,788,888,899:

But in written words, here it is: Take a number and multiply its digits (in base 10 unless otherwise noted) together. Then the product of the digits of that number. Then the product of the digits of that number. Keep going. Eventually you will reach a single digit number (the digit product for a multi-digit number is always less than that number, so it decreases at each step until a single digit is reached), and of course the digit product of a single digit number is itself, the end.

For instance: Starting from 28, we have 2×8 = 16, then 1×6 = 6 and you get to a single digit number in two steps. We say the multiplicative persistence of 28 is 2. From 88 it goes: 88, 64, 24, 8. Persistence is 3.

You might guess there’s no upper limit on persistence, that there can be numbers with persistence of 100 or 1000 or 1,000,000 or whatever; but actually the conjecture is that no number has persistence higher than 11. The smallest number with persistence 11 is 277,777,788,888,899:

277777788888899, 4996238671872, 438939648, 4478976, 338688, 27648, 2688, 768, 336, 54, 20, 0

Obviously the persistence doesn’t depend on the order in which the digits occur, so for instance 998,888,887,777,772 also has persistence 11. So does 27,777,772,228,888,899, where an 8 has been replaced by three 2s. Or by replacing all the 8s, and all the 9s by two 3s, you get numbers like 22,222,222,222,222,222,223,333,777,777, again with persistence 11. And of course adding a 1 digit doesn’t change anything, so 111,122,222,222,222,222,222,223,333,777,777 has persistence 11 too.

But no one has ever found a number with greater persistence. Why not?

Well, there’s a zero trap. Any number > 9 with a 0 digit in it has persistence 1. Any number that has no zero in it but does have a 5 and an even digit has persistence 2, because the product of its digits ends in 0. And even if a number has no zero and either no 5 or no 2, the same must be true of the product of its digits, and of the product of the digits of that product, and so on, for eleven steps in order for there to be a twelfth step. And when you’re dealing with numbers up around 277,777,788,888,899, the likelihood of that gets vanishingly small.

But how would you check if it’s really vanishing? The naive thing to do is to check all numbers up through, say, 1040, but that would take, ah, a while. (What’s your computer’s clock speed? The age of the Universe is 4.3 × 1026 nanoseconds…). Checking all the n-digit numbers would take around ten times longer than the n–1-digit ones, and that gets intractable pretty fast.

But as we just noticed, there’s no point in checking numbers containing a zero. And up around 277,777,788,888,899, a lot of numbers do. You can also skip any number containing a 5 and an even digit. Numbers containing a 1 are equivalent to a smaller number without a 1, so no point in bothering with them either. And of course, there’s no point in checking a number whose digits are a permutation of a number you’ve already checked.

In fact, suppose you don’t worry about the 5-and-even check. Then you can just look at numbers containing only digits > 1 in nondecreasing order. Like this:

2, 3, 4, 5, 6, 7, 8, 9, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35… , 77, 78, 79, 88, 89, 99, 222, 223, 224…

There are 8 valid single digit numbers. For 2-digit numbers there are 8 valid first digits, but the second digit must not be less than the first, so there are 8 numbers starting with 2, 7 starting with 3, 6 starting with 4, and so on: 8+7+6+5+4+3+2+1 = 36. That’s the 8th triangular number. For three digits, the number of valid numbers is similarly the 8th tetrahedral number, and generally for n digits, the 8th n-simplex number:

N(n) = \frac{(7+n)!}{7!n!}

That increases pretty slowly with n. You have to check 8 out of 10 1-digit numbers, but only 36 out of 90 2-digit numbers and 120 out of 900 3-digit numbers, and by the time you’re up to 40-digit numbers, you only have to check 62,891,499 of them! If you do skip over numbers with a 5 and an even digit, that drops even further to only 9,378,299 numbers. For 41 digits the number is 10,749,914, so instead of ten times as many numbers to check in that decade, there’s only about 15% more. A Python script can blow pretty easily through 50 or more digits in a fairly short time.

What you find is this: For valid (nondecreasing, all digits > 1) 15 digit numbers only one, 277,777,788,888,899, has persistence 11. For 16 digits, there’s only 2,247,777,778,888,899. For 17 digits there are two: 22,227,777,778,888,899 and 27,777,789,999,999,999. The first of these is a trivial modification of the 15-digit number, with the same digit product; the second has a different digit product, but the digit product of its digit product is the same as for the 15-digit number; it goes 27777789999999999, 937638166841712, 438939648, 4478976, 338688, 27648, 2688, 768, 336, 54, 20, 0.

Up to 29 digits there are only two valid numbers per decade with persistence 11, based on those two 17 digit numbers. The longest valid variant of 277,777,788,888,899 is 22,222,222,222,222,222,223,333,777,777 as noted above, and the other also has variants up to 29 digits. From 30 digits on up the maximum persistence is 10, with variants of a single number that peter out at 36 digits. For 37 through 42 digits maximum persistence is 8; for 43 through 44, 6: for 45 through 58, 5, and that’s all I’ve got so far.

The sequence of the persistences of the counting numbers is A031346 in OEIS, and the smallest number with persistence n is A003001. Per comments there, Martin Gardner wrote about the subject (of course), and there are results implying there are no numbers with persistence greater than 11 through 1020585.

That’s in base 10. In binary, every number > 1 has persistence 1. I’ll leave the other bases to you.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s