Возьмем к примеру число 1020. Его можно упростить, таким образом 10^2+20.
Но это короткое число. Так что возьмем для примера число чуть побольше: 10 000 002 985 984 (14 символов)
Его можно упростить так: 10^13 + 12^6 (10 символов).
Но это всё ещё маленькое число. В самой задаче присутствует число из 30↑30 символов в 36'чной системе счисления. Есть ли какой-нибудь алгоритм, который позволит упростить любое такое большое число, до простых математических операции, хотя бы из 10↑10 символов?
В условии математических операциях можно использовать любые простые операции, не требующего больших ресурсов для вычисления или из класса NP. К примеру, можно использовать: плюс, минус, деление, возведение в степень, стрелочные нотации Кнута, и др.
И ещё можно использовать любую систему счисления, вплоть до 36'чной.
Можно также разделить число на несколько частей, чтобы упростить их. И при вычислении этих чисел, они обратно встают друг за другом.
Сам алгоритм упрощения тоже должен быть простым и не быть из класса NP.
Так вот, существует ли такой алгоритм, которым можно упростить любое большое число до простых мат. операции с самым минимальным количеством символов?
Ответа не знаю, но давайте порассуждаем вместе.
1) Снижать число символов могут унарные функции, которые растут быстрее линейных по отношению к аргументу (например, факториал).
2) Функция двух и более аргументов должна рости быстрее, чем умножение: любая запись умножения длиннее, чем результат (степени, стрелки Кнута, функция Аккермана, ...).
При этом, как вы сами показали, ни от сложений, ни от умножений отказаться нельзя. Вряд ли для числа 2^65536+6 можно придумать запись, короче чем A(4,2)+9 или 2↑↑5+6 .
Таким образом, есть функции, "ухудшающие" запись, есть "улучшающие". Результат - это композиция этих функций. Дальше исключтельно рассуждения, не подтверждённые доказательствами :) Если отказаться от применения ухудщающих операций мы не можем, то пространство поиска у нас не выпуклое (иногда лучше декомпозировать число как сумму, чтобы потому получить что-то типа 2↑↑↑↑5+8^13). Кажется, поэтому ни динамика, ни DnC, ни жадный алгоритм нам не помогут. Скорее всего решение будет вполне себе экспоненциальным. Например, обход по дереву операций с отсечениями. Кажется, что задав изначальный набор унарных и бинарных операций, такой метод написать совсем несложно, но увы, это будет экспонента.