Как свернуть 3 числа в одно

[Руст]

Так обычно нумеруют все конечные подмножества N, сопоставляя конечному подмножеству $x_1,x_2,...,x_k$ (k не ограничено) число $2^{x_1}3^{x_2}...p_k^{x_k}.$

[bot]

bot писал(а):

Не бейте сильно, если это совсем тривиально, я ведь глубоко не задумывался.

Вчера перед сном осознал, что мой вопрос был глупый, что и подозревал.
Не осмелился высказать вчера, что экономия битов растёт с ростом N, а ведь это всё-таки верно.

Похоже знаю оптимальную компактизацию (в крайнем случае близкую к ней) услових произвольного числа k слагаемых с суммой, меньшей N.

[bot]

Как добрался до бумаги, так и вспомнил про овраги ...

bot писал(а):

... экономия битов растёт с ростом N, а ведь это всё-таки верно.

Лажа получилось - всё наоборот. При фиксированном числе слагаемых экономия убывает с ростом N и при больших N её просто нет. Конечно, это для избранного способа кодировки.
Однако для k, сравнимых с N (оптимум когда $\frac{N}{k} \approx 2,84 $ ), экономия есть.
Так, для кодировки решений уравнения

$$x_1 + x_2 = 1000$$

я не могу сэкономить ни одного бита, но для

$$x_1 + x_2 + ... + x_{100} = 1000$$

уже лучше - любое решение можно закодировать числом, содержащим не более 634 цифры в двоичной записи.
Для сравнения: при фиксированном диапазоне $ x_i \in [0,1000]$ для кодировки любого решения требуется 1000 цифр.
Ещё лучше для оптимального k~350:

$$x_1 + x_2 + ... + x_{350} = 1000$$

Здесь уже ~1500 против 3500.

[bot]

Частично прихожу к тому же самому:

bot писал(а):

... осознал, что мой вопрос был глупый ...

Постановка должна быть другой.
Предположим мы хотим закодировать n-ки (прежде употребляемую букву k в этом констексте отвергаю как неблагозвучную) некоторого множества M. Здесь принципиально два различных варианта:
1) M - конечно.
2) M - бесконечно.

Примером первого варианта может служить исходная задача или ещё проще - все $x_i$ равномерно ограничены: $0\le x_i \le a$
Здесь можно поступить просто - все n-ки кодируем бинарным кодом одной и той же длины.
Но можно сэкономить - ведь глупо кодировать n-ку малых чисел тем же количеством битов, что и n-ку больших чисел.
Способ 1. Поэтому берём из $x_i$ самое большое, смотрим сколько битов надо для записи этого максимального и этим же количеством битов кодируем все остальные члены n-ки. Эти коды пишем подряд. Этот способ пригоден уже и для бесконечного M, но на некоторых n-ках он неэкономен - например, если все числа в n-ке маленькие, за исключением одного большого.
Способ 2. Каждое из $x_i$ записываем в системе с основанием 3, пишем их подряд, отделяя друг от друга свободной цифрой 3, которая будет играть роль "перегородки". Число 0 при этом требует 0 бит для записи - если такое встретилось, ставим перегородку. Полученную запись рассматриваем как число в системе с основанием 4. В двоичном коде длина увеличится вдвое. Исходя из этого рассмотрения я и оценивал сверху нужное количество битов - неудобные для этого способа те n-ки члены которых близки друг другу по порядку величины. Формулки я не пишу - их легко напишет каждый.

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

Способ 3. (комбинированный). Для каждой n-ки без труда вычисляется необходимое число битов для кодировки по каждому из способов и определяется какой из них выгоднее. Остаётся выбрать более выгодный и указать способ распознавания выбора. При первом способе число битов всегда кратно n - это и будет отличительным признаком первого выбора. Однако случайно может оказаться, что и по второму выбору длина кратна n. Если это произошло, а этот выбор выгоднее, мы просто удлиним эту последовательность цифрой 0 спереди и сделаем этот выбор. Заметим для этого, что при втором способе цифра 0 никогда на первом месте не стоит - если $x_0 =1$, то эта цифра кодируется сама собой, а все $x_i = 0$ вообще не кодируются - ставится перегородка. Таким образом, если число битов кратно n, то кодировка первая, в противном случае - вторая, стоит впереди 0 или не стоит.

ЗЫ. Возможно это или что-нибудь подобное давно известно, так что надеюсь на снисходительность к дилетанту в теории кодирования.