Логика программирования: Нахождение наименьшего уравнения для большого числа

Question

Я мало что знаю о математике, поэтому я не знаю, как начать гуглить то, что я ищу, поэтому я полагаюсь на опыт экспертов, которые помогут мне понять, что я ищу ...

Я пытаюсь найти наименьшую строку уравнений для конкретного большого числа. Например дано число

"39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306816"

Наименьшее уравнение - 64 ^ 64 (что я знаю). Содержит только 5 байтов.

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

Это уже было создано? Если так, где я могу найти это? Я собираюсь взять чрезвычайно ОГРОМНЫЕ числа (10 ^ 10000000) и разбить их на, мы надеемся, выражения, которые будут как 100 символов в длину. Это вообще возможно? Разве современные процессоры / графические процессоры не способны выполнять такие большие вычисления?

---

Редактировать:

Ok. Таким образом, нахождение наименьшего уравнения занимает слишком много времени, судя по ответам. Есть ли какой-нибудь способ подловить это и найти самое маленькое из найденных до сих пор?

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

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

Answer 1

Просто чтобы добавить другое ключевое слово в свой бункер Google, см. Сложность по Колмогорову . Колмогоровская сложность строки - это размер самой маленькой машины Тьюринга, которая выводит строку при пустом вводе. Это один из способов формализовать то, что вы, кажется, после. Однако вычисление колмогоровской сложности данной строки, как известно, является неразрешимой проблемой:)

Надеюсь, это поможет,

TJ

Answer 2

Здесь есть хорошая программа для этого: http://mrob.com/pub/ries/index.html

Answer 3

Я задал вопрос «в чем смысл делать это», поскольку я не знаю, смотрите ли вы на этот вопрос с точки зрения математики или с точки зрения факторизации большого числа.

Поскольку в других ответах учитывается факторинговая точка зрения, я посмотрю на математику. В частности, проблема, которую вы описываете, является проблемой сжимаемости . Здесь у вас есть номер, и вы хотите описать его в наименьшем алгоритме. Сильно случайные числа имеют очень плохую сжимаемость, так как для их описания необходимо либо выписать все цифры, либо описать детерминированный алгоритм, который лишь немного меньше самого числа.

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

Как вы сказали, вы не знаете много математики, возможно, это бесполезный ответ для вас ...

Answer 4

Вы выполняете форму сжатия без потерь, а сжатие без потерь не работает со случайными данными.Предположим, наоборот, что у вас был способ сжатия N-битных чисел в N-1-битные числа.В этом случае у вас будет 2 ^ N значений для сжатия в 2 ^ N-1 обозначений, что в среднем составляет 2 значения для обозначения, поэтому ваше среднее обозначение не может быть распаковано.Сжатие без потерь хорошо работает с относительно структурированными данными, где данные, которые мы, вероятно, получим, сжимаются небольшими размерами, а данные, которые мы не собираемся получать, на самом деле увеличиваются.Сжатие частично, позволяя больше информации на символ.(Существует больше N-символьных последовательностей, включающих цифры и операторы, чем только цифры.) Тем не менее, вы не получите сжатие без потерь, которое в среднем лучше, чем просто запись целых чисел в двоичном виде.*

Answer 5

Это действительно проблема математики, а не проблемы программирования или информатики. Вы должны спросить это на https://math.stackexchange.com/

Answer 6

Похоже, что вы в основном хотите использовать факторинг для сколь угодно большого числа. Это настолько сложная проблема, что она фактически является краеугольным камнем современной криптографии.

Answer 7

Хотя ваш вопрос остается неясным, возможно, поиск целочисленных отношений - это то, что вам нужно.

РЕДАКТИРОВАТЬ:

Существуют некоторые предположения, что поиск "короткой" формыкак-то связано с проблемой факторинга.Я не верю, что это правда, если ваше определение не требует продукта в качестве ответа.Рассмотрим следующий псевдоалгоритм, который является просто наброском и для которого не предпринимаются попытки оптимизации.

Если «кратчайший» является четко определенной концепцией, то в общем случае вы получаете «короткие» выражения, используя маленькие целые числа для большихполномочия.Если N - мое целое число, то я могу найти рядом целое число, которое равно 0 mod 4. Насколько близко?В пределах +/- 2. Я могу найти целое число в +/- 4, которое равно 0 mod 8. И так далее.Теперь это только степени 2. Я могу выполнить то же упражнение с 3, 5, 7 и т. Д. Мы можем, например, легко найти ближайшее целое число, которое одновременно является произведением степеней 2, 3, 5, 7,11, 13 и 17, назовите это N_1.Теперь вычислите N-N_1, назовите его d_1.Может быть, d_1 "короткий".Если это так, то ответ N_1 (выраженный как степень простого числа) + d_1.Если нет, повторите поиск, чтобы найти «короткое» выражение для d_1.

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

Answer 8

Существование бесконечного числа простых чисел означает, что всегда найдутся числа, которые нельзя упростить с помощью факторинга. То, о чем ты просишь, невозможно, извини.