85 шагов для "калькулятора" (x→x+1, x→2x, x→3x)

Понятно что число с максимальным количеством операций будет максимально удалено от степеней 3-х и 2-х. В таком случае нам нужно лишь просмотреть числа 2**a * 3**b - 1, что сокращает количество чисел до ~64 * 40. Вот решение, что я написал:

import collections
import tqdm


def problem85(n):
    graph = {}
    queue = collections.deque()
    queue.append((n, 0))
    while queue:
        a, b = queue.popleft()
        if a not in graph:
            graph[a] = b
            if a == 1:
                break
            q, r = divmod(a, 3)
            if r == 0:
                queue.append((q, a))
            q, r = divmod(a, 2)
            if r == 0:
                queue.append((q, a))
            queue.append((a - 1, a))

    m = 1
    path = [m]
    while m != n:
        m = graph[m]
        path.append(m)
    return len(path) - 1

results = []

for pow2 in tqdm.tqdm(range(64)):
    for pow3 in range(40):
        if ((pow2 == 0 and pow3 == 0) or (2 ** pow2 * 3 ** pow3) > 2 ** 64): break
        result = problem85(2**pow2 * 3 ** pow3 - 1)
        if result > 60:
            results.append([result, pow2, pow3])

for result in sorted(results, key = lambda x:x[0]):
    print(result)

Где problem85 - функция решения оригинальной задачи.

Вот топ лист:

[87, 40, 15]
[88, 28, 21]
[88, 29, 20]
[88, 31, 18]
[88, 36, 17]
[89, 27, 23]
[89, 28, 22]
[89, 30, 19]
[89, 32, 18]
[89, 35, 17]
[89, 37, 17]
[90, 29, 21]
[90, 30, 20]
[90, 33, 18]
[90, 34, 18]
[91, 29, 22]
[91, 31, 19]
[92, 30, 21]
[92, 31, 20]
[92, 32, 19]
[92, 35, 18]
[93, 33, 19]
[94, 32, 20]

Я воспользовался великолепной идеей из ответа gord1402. У меня уже была таблица рекордов (она есть на OEIS: https://oeis.org/A056817), полученная полным перебором. Для каждого числа операций я отыскал минимальное n требующее это количество операций. Например 143 строится за 10 операций, а все числа меньше требуют меньше операций.

Я попробовал к рекордам добавлять небольшие числа так, чтобы сумма делилась на много двоек и троек: 143 + 1 = 2⁴·3².

Иногда деление не полное, остаётся небольшой множитель. Рекорд для 20 разлагается так:
12959 + 1 = 2⁵·3⁴·5.

Получилась таблица ниже. Она составлена неформально: сперва подбиралось небольшое t, потом проверялось что сумма "хорошо" разлагается. Но это всегда срабатывало: t принимает значения 0, 1, 2 и 5, а оставшийся после исключения двоек и троек множитель f – 1, 5 и 7.

Дальше я повторил поиск gord1402 меняя параметры a, b, f, t. f менялся в диапазоне [1, 30] (брались только значения взаимно простые с 2 и 3), t – в диапазоне [0, 20]. Для 2^a·3^b·f - t рассчитывалось количество операций. Рекорды для 85, 94, 95:

85: n = 136496581762351103 = 2²⁴·3¹⁹·7 - 1

94: n = 9827753886889279487 = 2²⁷·3²¹·7 - 1

95: n = 13103671849185705983 = 2²⁹·3²⁰·7 - 1

Доказательства у меня нет, но я думаю что все рекорды имеют структуру замеченную gord1402. Если так, то 95 – самое большое число операций для n < 2⁶⁴.