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

Question

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!

Answer 1

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

Answer 2

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)