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