Закодируйте последовательность чисел как одно число - используйте китайскую теорему об остатках

Question

Мне нужно закодировать последовательность S произвольного числа элементов (но конечных) с целым числом Kи сможет декодировать K чтобы получить обратно начальную последовательность.

Мне нужно сделать так, чтобы компьютер был в состоянии справиться с числом K,

Я сделал это так (в lisp):

• предположим, что последовательность S имеет n элементов e1, ... en

• генерировать первые n простых чисел p1 ... pn

• написать K = p1^e1 + p2 ^ e2 + ... + pn ^ en

Я попробовал этот метод. Тем не менее, я получаю огромное количество.

Я знаю, что можно использовать chinese remainder theorem чтобы решить проблему, и K получается не так уж и много.

Кто-нибудь может помочь мне использовать эту теорему так, чтобы я кодировал последовательность?

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

Я хочу увидеть алгоритм кодирования с использованием ch r th используя конкретный простой пример. Я не могу понять теоретические идеи из Википедии и других веб-ресурсов.

Answer 1

Вы ищете нумерацию последовательностей Гёделя. Это способ кодирования (конечной) последовательности чисел в виде единого числа. Китайская теорема об остатках дает рекурсивный метод построения.