# Calculates the multiplicative persistence of a given number // Returns the smallest number with a given level of MP (Numberphile Challenge)

I was watching this Numberphile video: https://youtu.be/Wim9WJeDTHQ on multiplicative persistence (multiplying digits of a number over and over until one digit remains). I decided to take up the challenge, first of creating a program that calculates the multiplicative persistence of a given number, then reversing the process to return the smallest number with a given level of multiplicative persistence. This is the first half:

# Calculating the multiplicative persistence of a given number
def per():

number = input("Enter an integer: ")
steps = 0

if len(number) == 1:
print(number)
print(f"Number of steps: {steps}")

else:

while len(number) > 1:
digits = [int(digit) for digit in number]
new_number = 1

for digit_multiply in digits:
new_number *= digit_multiply
print(new_number)
steps += 1
number = str(new_number)

print(f"Number of steps: {steps}")

per()


The other half of returning the smallest number with a given MP level is below, but warning: I couldn't figure out how to put a limit on the process and I noticed that my computer took a long time returning the number after a persistence of 8. I don't know what the problem but I'm afraid it may have something to do with memory; hopefully you can enlighten me:

# Calculating the multiplicative persistence of a given number
def persistence(number):

steps = 0

while len(str(number)) > 1:
digits = [int(digit) for digit in str(number)]
new_number = 1

for digit_multiply in digits:
new_number *= digit_multiply

steps += 1
number = str(new_number)

return steps

# Finding the smallest number of a given persistence level
def numb_finder(level):

number = 0

while persistence(number) < level:
number += 1

return number

desired_level = int(input("Multiplicative Persistence Level: "))
print(f"Smallest number: {numb_finder(desired_level)}")


Thanks as always!

## 2 Answers

In my testing, it was faster to use divmod() to extract and multiply the digits that to convert back and forth between strings and ints. That is this code took about half the time to multiply the digits as your code:

def digital_product(number):

m = 1
while number > 1:
number,r = divmod(number, 10)
m *= r

return m


One thing to realize is that persistence function can be calculated recursively:

persistence(n) = 0  if n < 10

persistence(n) = persistence(digit_product(n)) + 1 if n >= 10


So you can basically use earlier results to reduce the time needed to calculate later results. This code finds all the minimums below the LIMIT. It can calculate the persistence function for n up to 20M in about 23 seconds.

LIMIT = 20_000_000

mins = {0:0}

pers = [0]*LIMIT

for i in range(10, LIMIT):
pers[i] = pers[digital_product(i)] + 1
if pers[i] not in mins:
print(f"min {pers[i]} is {i}")
mins[pers[i]] = i


Output:

min 1 is 10
min 2 is 25
min 3 is 39
min 4 is 77
min 5 is 679
min 6 is 6788
min 7 is 68889
min 8 is 2677889


The persistence function is taking a few micro-seconds per call which seems OK but is called many times. This could be reduced by not starting the checking at 1 but at eg. 11111111 (for level 8) using: number = int('1'*level)

• That implies some sort of relation between the length of the number and its persistence. I'm not sure such a relation exists. For example, 89 has persistence 3, but you would miss that and start checking at 111. Jul 20, 2022 at 14:34