1
\$\begingroup\$

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!

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Teepeemm
    Jul 20 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.