Persistence Reverse Calculation!

Question

This question was inspired by a recent question about number persistence.

If a number's persistence is defined by how many times you have to multiply all of its digits together before you get a single digit (e.g. *47 -> 28 -> 16 -> 6 (4 steps)) how can you determine a number with n persistence by calculating backwards? Or is it impossible?

By calculating backwards I mean taking a number (such as 2) and work from it; 2 -> 12 (or 21) -> etc. etc.

Prove your claim!

Answer 1

Rather than giving heuristics that might work, I thought I'd try putting my money where my mouth is.

Here's some code in Python 3:

from collections import defaultdict

PERSISTENCE = 9
START_DIGIT = 0
ONES = 1

def single_digit_factorise(n):   
    divisors = []

    for p in [2, 3, 5, 7]:
        while n % p == 0:
            n //= p
            divisors.append(p)

    return (n == 1) and sorted(divisors)

# Uses http://www.nayuki.io/page/next-lexicographical-permutation-algorithm
def next_number(digits):
    # Treat 0 differently
    if digits[-1] == 0:
        n = int("".join(map(str,digits[:-1])))
        return list(map(int,list(str(n+1)))) + [0]

    pivot = len(digits) - 1
    last = digits[-1]

    while pivot >= 0 and digits[pivot] >= last:
        last = digits[pivot]
        pivot -= 1

    # Exhausted search, add a 1
    if pivot == -1:
        return [1] + sorted(digits)

    pivot_num = digits[pivot]
    successor = len(digits) - 1

    while digits[successor] <= pivot_num:
        successor -= 1

    digits[pivot], digits[successor] = digits[successor], digits[pivot]
    digits[pivot+1:] = digits[pivot+1:][::-1]

    return digits

def to_num(digits):
    total = 0

    for i in range(len(digits)):
        total += digits[~i] * 10**i

    return total

def possibilities(digits):
    def _possibilities(digits, results):
        results.add(tuple(sorted(digits)))

        if digits.count(2) + digits.count(3) <= 1:
            return results

        # It's late night and I can't be bothered making this part neater
        if digits.count(2) >= 3:
            digits.remove(2)
            digits.remove(2)
            digits.remove(2)
            digits.append(8)
            _possibilities(digits, results)
            digits.remove(8)
            digits.extend([2, 2, 2])

        if digits.count(2) >= 2:
            digits.remove(2)
            digits.remove(2)
            digits.append(4)
            _possibilities(digits, results)
            digits.remove(4)
            digits.extend([2, 2])

        if digits.count(3) >= 2:
            digits.remove(3)
            digits.remove(3)
            digits.append(9)
            _possibilities(digits, results)
            digits.remove(9)
            digits.extend([3, 3])

        if digits.count(2) >= 1 and digits.count(3) >= 1:
            digits.remove(2)
            digits.remove(3)
            digits.append(6)
            _possibilities(digits, results)
            digits.remove(6)
            digits.extend([2, 3])

        return results

    results = _possibilities(digits, set())
    return list(map(list, results))

def persistence_str(n):
    output = [str(n)]

    while n >= 10:
        product = 1

        for digit in str(n):
            product *= int(digit)

        output.append(str(product))
        n = product

    return " -> ".join(output)

def find_persistence(n, start, ones=1):
    assert 0 <= start < 10

    queues = defaultdict(list)

    if start > 0:
        queues[0] = [[start]]
        base = step = 0

    else:
        queues[1] = [[1, 0]]
        base = step = 1

    while base <= step < n:
        if not queues[step]:
            step -= 1
            continue

        num = queues[step].pop(0)            
        fact = single_digit_factorise(to_num(num))

        next_num = next_number(num[:])

        if len(num) > 1 and next_num.count(1) <= ones:
            queues[step].append(next_num)

        if len(num) == 1:
            step += 1
            queues[step].append(next_num)
            queues[step].extend([x for x in possibilities(fact) if len(x)>1])

        elif fact and fact != num:
            step += 1
            queues[step].extend([x for x in possibilities(fact) if len(x)>1])

    return to_num(queues[step][0])

number = find_persistence(PERSISTENCE, START_DIGIT, ONES)
print(persistence_str(number))

Edit: Updated to be easier to use

Enter the persistence and starting digit at the top. ONES is an additional parameter which specifies how many ones the program is allowed to add.

Currently the program throws an error if a solution was not found (you can try upping the number of ones allowed to see if that helps).

Here are some chains it has found:

2222222223333333778 -> 438939648 -> 4478976 -> 338688 -> 27648 -> 2688 -> 768 -> 336 -> 54 -> 20 -> 0
11 -> 1
222222244468 -> 393216 -> 972 -> 126 -> 12 -> 2
13 -> 3
2377 -> 294 -> 72 -> 14 -> 4
33557 -> 1575 -> 175 -> 35 -> 15 -> 5
233366777 -> 666792 -> 27216 -> 168 -> 48 -> 32 -> 6
17 -> 7
2222344444446679 -> 1783627776 -> 4148928 -> 18432 -> 192 -> 18 -> 8
19 -> 9

It's not surprising that the chains found are so short for the digits 1379. After all, the last digit means that the number can't be divisible by 2 or 5, leaving only 3 and 7 as possible prime factors. If it's possible for the chain to be any longer for these digits then it's going to need a lot of 1s.

---

Explanation

We keep a list of queues for different persistences, e.g. queue #3 is filled with numbers of persistence 3. Each queue is essentially a list of numbers to be searched. We initialise queue #0 to contain the digit in question (or queue #1 to contain 10 if the digit was 0, to make calculating easier). We also initialise a step variable to 0.

While step is less than our target, we:

• Check if queue #step is empty. If it is, we decrement step by 1 and backtrack.
• Otherwise, get the next number from queue #step.
• Factorise it into primes, and push the "next number" back onto queue #step
• If the prime factorisation had only single digits and isn't the original number (in the case of one-digit numbers) then:
  • Increment step by 1 (i.e. we just found a number with a higher persistence)
  • Look at all possibilities of factorising the number into single digits (not necessarily prime) and push each of them into the queue for the new incremented step number.

For most numbers, "next number" means lexicographically, so 123 -> 132 -> 213 -> 231 -> 312 -> 321. When we reach the end, we go back to the beginning but add a 1 to the front, i.e. 321 -> 1123 -> 1132 -> ....

For multiples of 10, however, we use the next multiple of 10 (since these are all numbers with a product of 0).

However, this has the problem that we might be searching indefinitely, always adding 1s. To remedy this we stop searching down a path if we've added more than some number of 1s - this probably isn't the best method, but it's the first quick heuristic I could think of.

All this was a mouthful, so let's look at what happens if the number we're searching is 24.

• We push 42 as the next number to search back on the current queue for later
• We factorise 24 into primes, becoming [2, 2, 2, 3]
• Then we look at all ways of turning that factorisation into single digits whose product is 24, giving 38, 234, 46, 2223, 226.
• Finally we increment step by 1 as we have found numbers with a persistence one higher than that of 24, and push all of these numbers into the corresponding queue and continue searching from there

Answer 2

This is less simple than I thought. The chosen factors must all be less than 10.

Choose an end number (4)
Choose a set of factors (1,4).
Use the factors to form a new number (14).
Repeat until you have a number of the desired persistence (2,7)->72, (8,9)->98 (2,7,7)->277. This has no set of factors all less than 10. We may add 1s as we wish until we have a number which factorises as desired.

Answer 3

Using this process, you can never calculate a number's persistence. I will explain why.

Let's say you start with $13$:

$13$
$1113$ & $3111$
$(3113$ & $3113)$ or $(1331$ & $1331)$
$((2321$ & $1232)$ or $(2321$ & $1232))$ & $((2123$ & $3212)$ or $(2123$ & $3212))$

As you can see, the resulting numbers will never reach a single digit, and the sequence becomes extremely complicated. I would continue on, but as you can see, it gets very complicated and redundant.

Answer 4

You could brute force it by checking the persistence of each number until you find one that matches. You could get smart with different rules for building this data, such as any number with a 0 in it will have a persistence < 2, any number with an even digit and a 5 will have a persistence of < 3, etc.

However, from Wikipedia's persistence article it's thought that multiplicative persistence for base 10 is <= 11 for all numbers. If that's true you could just take the appropriate value from that known sequence based on your desired n from the following values:

[0, 10, 25, 39, 77, 679, 6788, 68889, 2677889, 26888999, 3778888999, 277777788888899]