## Multiplicative Persistance

### March 26, 2019

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.

Pages: 1 2

### 9 Responses to “Multiplicative Persistance”

1. Paul said

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.

```from functools import reduce
from operator import mul
from itertools import combinations_with_replacement

def mult(n):
pr = [n]
while n > 9:
n =  reduce(mul, (int(c) for c in str(n)))
pr.append(n)
return pr

def search():
rest of the numbers are 6, 7 ,8 ,9
"""
first = "23 "
rest = "6789"
ms = 0
for N in range(2, 50):
for f in first:
for m in combinations_with_replacement(rest, N + (1 if f == " " else 0)):
n = int(f + "".join(m))
steps = mult(n)
if len(steps) > ms:
ms = len(steps)
print("-".join(str(s) for s in steps))

search()
```
2. Paul said

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

3. matthew said

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.

```from operator import mul
from functools import reduce

# The smallest number with a given number of steps must have digits
# in ascending order and not contain 0 or 1.

# Represent candidate numbers by multisets of 0..7:

# Convert a multiset to an integer, nth multiset element is number of times
# digit n+2 occurs, so eg. [1,2,0,2,0,0,0,1] => 233559

def mset2int(s): return int(''.join([str(i+2)*d for (i,d) in enumerate(s)]) or '0')

# Find the next multiset - when converted to integers as above, the
# sequence of integers is in ascending order.
def nextmultiset(s):
# [..,n,0,..,0,m] -> [..,n-1,m+1,..,0,0]
# [0,0,..,n] => [n+1,0,..,0]
n = s[-1]; s[-1] = 0
for i in range(len(s)-1,0,-1):
if s[i-1] > 0:
s[i-1] -= 1
s[i] = n+1
return
s = n+1

# Count the number of reduction steps for an integer
def countsteps(n):
count = 0
while n >= 10:
n = reduce(mul,(int(d) for d in str(n)))
count += 1
return count

s = *8
max = -1
while True:
n = mset2int(s)
steps = countsteps(n)
if steps > max:
print(n,steps)
max = steps
nextmultiset(s)
```
4. Ernie said

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

5. Ernie said

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

6. matthew said

@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.

7. matthew said

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 239 * 33 * 7**2, but after that everything seems to end up at 0:

```from operator import mul
from functools import reduce

def nextmultiset(s):
n = s[-1]; s[-1] = 0
for i in range(len(s)-1,0,-1):
if s[i-1] > 0:
s[i-1] -= 1
s[i] = n+1
return
s = n+1

def seq(n):
s = [n]
while n >= 10:
n = reduce(mul,(int(d) for d in str(n)))
s += [n]
return s

def test():
s = *4
while True:
n = 2**s * 3**s * 5**s * 7**s
a = seq(n)
if a[-1] != 0: print(n,s,a)
nextmultiset(s)

test()

"""
(1, [0, 0, 0, 0], )
(2, [1, 0, 0, 0], )
(3, [0, 1, 0, 0], )
(5, [0, 0, 1, 0], )
(7, [0, 0, 0, 1], )
(4, [2, 0, 0, 0], )
(6, [1, 1, 0, 0], )
(14, [1, 0, 0, 1], [14, 4])
(9, [0, 2, 0, 0], )
(15, [0, 1, 1, 0], [15, 5])
...
(3416267673274176, [6, 27, 0, 1], [3416267673274176, 1792336896, 2939328, 23328, 288, 128, 16, 6])
(913217421312, [29, 5, 0, 1], [913217421312, 18144, 128, 16, 6])
(1438916737499136, [24, 6, 0, 6], [1438916737499136, 4444263936, 1492992, 11664, 144, 16, 6])
(112717121716224, [34, 8, 0, 0], [112717121716224, 131712, 42, 8])
(727326941773824, [39, 3, 0, 2], [727326941773824, 1194891264, 124416, 192, 18, 8])
"""
```
8. Daniel said

Here’s a solution in C.

```#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
if (argc != 2) return EXIT_FAILURE;
if (*argv == '-') ++argv;
intmax_t x = strtoimax(argv, NULL, 10);
for (int i = 0;; ++i) {
printf("%d %jd\n", i, x);
if (x < 9) break;
intmax_t y = 1;
while (x) {
y *= x % 10;
x /= 10;
}
x = y;
}
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./a.out 277777788888899
0 277777788888899
1 4996238671872
2 438939648
3 4478976
4 338688
5 27648
6 2688
7 768
8 336
9 54
10 20
11 0
```
9. ```
Mumps version

EN ; ENTER
N I,J,N,NS,OLDNS,QTY,VAL
K TMP
W !,"PER(327) = ",\$\$PER(327)
F I=0:1:9 S TMP(2,I)=0
S OLDNS=-1
F I=1:1:1000001 D
. S L=\$\$PER(I)
. S N=\$P(L," "),NS=\$L(L," ")-1
. S TMP(2,N)=TMP(2,N)+1
. S TMP(3,NS)=\$G(TMP(3,NS))+1
. I NS>OLDNS D
. . S TMP(4,NS)=L
. . S OLDNS=NS
F I=2,3 S J=I+.5,N="" F  S N=\$O(TMP(I,N)) Q:N=""  D
. S QTY=TMP(I,N)
. S TMP(J,-QTY)=\$S('\$D(TMP(J,-QTY)):N,1:TMP(J,-QTY)_" "_N)
F I=2.5,3.5 D
. W !!,\$P("Common ending #;Common # of steps",";",I-1.5)
. S N="" F  S N=\$O(TMP(I,N)) Q:N=""  W !,TMP(I,N),": ",-N
W !!,"Longer sequences:"
S NS="" F  S NS=\$O(TMP(4,NS)) Q:NS=""  S J=NS W !,\$J(NS,2),": ",TMP(4,NS)
F I=1000002:1 Q:NS=11  D
. S L=\$\$PER(I),NS=\$L(L," ")-1
. I NS>J D
. . W:\$I(J) !,\$J(NS,2),": ",L," (\$H = ",\$H,")"
Q
;
PER(N) ; Multiplicative Persistence
N I,L,S
S L=N
F  Q:N<10  D
. S S=1
. F I=1:1:\$L(N) S S=S*\$E(N,I)
. S N=S,L=N_" "_L
Q L
;

---

YDB>d ^multpers

PER(327) = 8 42 327

Common ending #
0: 902610
6: 43538
8: 32658
2: 16673
4: 2345
5: 2073
9: 56
3 7: 21
1: 6

Common # of steps
1: 402541
2: 375227
3: 123860
4: 66772
5: 24654
6: 4488
7: 2450
0: 9

Longer sequences:
0: 1
1: 0 10
2: 0 10 25
3: 4 14 27 39
4: 8 18 36 49 77
5: 6 32 48 168 378 679
6: 0 20 54 336 768 2688 6788
7: 0 20 54 336 768 2688 27648 68889
8: 0 20 54 336 768 2688 27648 338688 2677889 (\$H = 65102,31491)
9: 0 20 54 336 768 2688 27648 338688 4478976 26888999 (\$H = 65102,31564)
10: 0 20 54 336 768 2688 27648 338688 4478976 438939648 3778888999 (\$H = 65102,43213)^C
%YDB-I-CTRLC, CTRL_C encountered

YDB>h

sdfsdf

```