6
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ The Wiki article says that numbers with large persistence (like, persistence 10) can be calculated in "a fraction of a second" with a clever algorithm. Hmm. I'm interested. $\endgroup$ – Lopsy Dec 30 '14 at 17:45
  • $\begingroup$ I'm confused by your question. Correct me if I'm wrong, but are you saying if you have 3, you get 1 3, or 13? Then do you do the same process (13 ==> 1 1 and 1 3 ==> 1113)? Also, I'm glad you were inspired by my question! :) $\endgroup$ – James Lynch Dec 30 '14 at 18:07
  • $\begingroup$ 3 could be 13 or 31 going backwards @JamesLynch $\endgroup$ – Chrismas007 Dec 30 '14 at 18:08
  • $\begingroup$ Then that means you will never get to a single digit: 3, 13 & 31, 1113 & 3111 or 1311 & 1131, so on, so on, forever. $\endgroup$ – James Lynch Dec 30 '14 at 18:09
  • $\begingroup$ Well the O.P. is talking about multiplicative persistence here... so yes, going backwards from 3 we see that you can only go persistence 1. But look at 2 -> 12/21 -> 34/43/37/73 etc. $\endgroup$ – Chrismas007 Dec 30 '14 at 18:11
5
$\begingroup$

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

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.

$\endgroup$
  • 1
    $\begingroup$ How can you guarantee that by adding 1s you'll eventually get a number that'll factorise into single digits? $\endgroup$ – Sp3000 Dec 30 '14 at 20:03
  • $\begingroup$ @Sp3000 I can't, and if the wiki article is correct (persistence $\leq 11 $ for all numbers less than $10^{50}$) this seems unlikely to work well. $\endgroup$ – frodoskywalker Dec 30 '14 at 21:01
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The op is (or appears to be) asking for a method to find a number of a given persistence, starting from the single digit number it reduces to. $\endgroup$ – frodoskywalker Dec 30 '14 at 21:07
0
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ This is not the meaning of the OP's question. They are looking for the reverse persistence of $n$. Otherwise, prove this false. $\endgroup$ – James Lynch Dec 30 '14 at 19:24
  • $\begingroup$ @JamesLynch: If so, "How can you determine a number with n persistence by calculating backwards?" needs an edit. $\endgroup$ – Briguy37 Dec 30 '14 at 20:27

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.