Учитывая целое число, найдите наименьшую функцию, которая дала ему

Question

У меня очень большое положительное целое число (миллион цифр).Мне нужно представить его с наименьшей возможной функцией, это число является переменной, это означает, что мне нужен алгоритм, который генерирует наименьшую возможную функцию для получения заданного числа.

Пример: Для числа 295126654306527521487534802261977363143592725170438328860638846328860638846376769470330000000000000000000000000000000000000000000000000000000000"9 ^ 99".Он должен уметь анализировать числа и всегда возвращать математическую функцию, которая представляет число.Пример: номер 21847450052839212624230656502990235142567050104912751880812823948662932355202 должен возвращать «9 ^ 5 ^ 16 + 1».

Answer 1

Слышал о Колмогоровской сложности ?

Чтобы ответить на ваш вопрос: если вы не ограничите себя каким-то конкретным набором функций, это невозможно.

РЕДАКТИРОВАТЬ: Даже в вашем примере, откуда вы знаете, что кратчайшее представление 21 847 450 052 839 212 624 230 656 502 990 235 142 567 050 104 912751 880 812 823 948 662 932 355 202 на самом деле 9 ^ 5 ^ 16 + 1?Разве не сложно доказать даже в этом конкретном случае ?

Если вы ограничиваете себя каким-то набором функций, то вы можете использовать следующий алгоритм:

For i = 1 to n
  enumerate all strings s of length i
    if s represents a valid expression according to rules chosen a priori, 
      and evaluates to the number in the input,
        return s

Гарантируется остановка, потому что на последней итерации внешнего цикла (i = n) вы в конечном итоге получите строку, содержащую входной дословно.

Конечно, этоне очень эффективно.В частности, O (b ⁿ ), где n - длина ввода, а b - размер алфавита.

Answer 2

Расширяя краткий ответ @ybungalobill, ваша функция эквивалентна функции, которая вычисляет колмогоровскую сложность произвольной строки.(Эквивалентность очевидна, если вы рассматриваете каждую цифру ваших очень больших чисел как символы, а числа как последовательности символов.)

Согласно странице Википедии о сложности Колмогорова, функция K(s), которая даетсложность строки s равна , не является вычислимой функцией .(На странице есть подтверждение.)

Другими словами, требуемый алгоритм просто не существует.

Answer 3

Если вы не ищете оптимальности, просто достаточно хорошей работы, то есть куча эвристик, которые вы можете использовать.Например, попробуйте разложить n, используя все следующие

n = a^k + b

для k = 2, 3, ..., log n, и выберите тот, который имеет наименьшее значение, скажем, a + b.Вы можете вычислить a и b, используя a = floor(n^(1/k)) и b = n-a^k.Затем наберите a и b.

Конечно, для поиска хорошего сжатия используется только возведение в степень и сложение.Если вы также разрешите вычитание, используйте a=round(n^(1/k)) вместо этого, и пусть b будет отрицательным.

Также допустимое умножение делает его немного сложнее, потому что вам, вероятно, нужно будет учитывать n.

Answer 4

@ BlueRaja - Дэнни Пфлюгофт: да, это так.Я пытаюсь создать сжатие, которое использует этот алгоритм, но, кстати, это невозможно.

Это потому, что технически невозможно сжать произвольные данные по той же причине, но это не такпомешать нам сделать это:)

Однако есть гораздо лучшие способы сжатия данных.Взгляните, например, на LZ .Это настолько повсеместно, что вы почти наверняка можете найти библиотеку, которая будет выполнять сжатие для вас, независимо от того, на каком языке вы пишете. DEFLATE - еще один популярный язык.!