## Multiplicative Persistance

### March 26, 2019

Over at NumberPhile, Matt and Brady are talking about multiplicative persistance:

Take a number. Multiply all its digits together. Repeat with the new number until it reaches a single digit. For instance, starting from 327, the product of the digits 3, 2 and 7 is 42, then recurring with 42 the product of the digits 4 and 2 is 8, which is the final answer; we say the sequence 327 → 42 → 8 finishes in 2 steps. What number leads to a sequence with the maximal number of steps?

The video includes some live-coding in Python by Matt.

Your task is to implement a function to compute the multiplicative persistance sequence starting from a given number, then “play with it” as Matt suggests. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Python. As suggested in the video only certain patterns of numbers is searched. The results come in a few seconds. After that no more numbers are found up to 50 digits.

Strange. My comment ended up in page 2.??

I also went for a Python solution, this one just enumerates multisets of 2..9 (in appropriate order) and uses the number with those digits in ascending order. A few seconds to get up to 277777788888899 (after looking at 435968 multisets), then nothing. https://oeis.org/A003001 has more details.

I noticed an interesting pattern when I calculated the frequency of the final step in the range 1…10^n

1 occurs n times

3 and 7 occur n(n+1)/2 times

9 occurs n(n+1)(n+2)/6 times

I noticed an interesting pattern when I calculated the frequency of the final step in the range 1…10^n

1 occurs n times

3 and 7 occur n(n+1)/2 times

9 occurs n(n+1)(n+2)/6 times

@Ernie: nice observation, looks like the only numbers going to 1 are 100.., going to 3 are 311.. & permutations, going to 7 are 711.. & permutations and going to 9 are 3311… and 911…, with permutations which gives the result you see. For other numbers to end up here, we would need eg. 311111 to have only 2,3,5 and 7 as prime factors which is (presumably) unlikely, though I don’t see why it should be ruled out.

Investigating further, there seems to only a finite number of fundamentally different numbers that end up at something other than 0. The product of digits can only have 2,3,5 and 7 as prime factors so generating multisets of 0..3 gives us all numbers of that form. We quickly get up to 2

39 * 33 * 7**2, but after that everything seems to end up at 0:Here’s a solution in C.

Example Usage: