Получение уникальных комбинаций номеров

Question

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

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

Но мне интересно, возможно ли это без возведения в степень.

Answer 1

Нет, вы можете использовать только возведение в степень, потому что сумма младших значений должна быть меньше, чем новое число, чтобы быть уникальным: 1 + 2 = 3 <4, 1 + 2 + 4 = 7 <8. </p>

[EDIT:] Это объяснение непрофессионала, конечно, есть и другие возможности, но не такие эффективные, как использование экспонент 2.

Answer 2

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

{} : all possible sums = {0}, smallest possible next = 1
{1} : all possible sums = {0, 1}, smallest possible next = 2
{1, 2} : all possible sums = {0, 1, 2, 3}, smallest possible next = 4
{1, 2, 4} : a.p.s. = {0, 1, 2, 3, 4, 5, 6, 7}, s.p.n. = 8
{1, 2, 4, 8} ...

И, конечно, мы наращиваем бинарные способности. Вы можете начать с чего-то другого, кроме {1, 2}, но посмотрите, что произойдет, используя правило «наименьшее возможное следующее»:

{1, 3} : a.p.s. = {0, 1, 3, 4}, s.p.n. = 6 (because 2 could be added to 1 giving 3, which is already there)
{1, 3, 6} : a.p.s. = {0, 1, 3, 4, 6, 7, 9, 10}, s.p.n = 11
{1, 3, 6, 11} ...

Эта последовательность растет быстрее, чем двоичные степени, термин за термином.

Если вам нужна хорошая задача программирования в стиле Project-Euler , вы можете написать подпрограмму, которая принимает набор положительных целых чисел и определяет «наименьшее возможное следующее» положительное целое число под «сумма быть уникальным "ограничение.

Answer 3

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

С числами с плавающей точкой вы можете добавлять уникальные неприводимые корни простых чисел (sqrt(2), sqrt(3), sqrt(5), ...), и вы всегда будете получать что-то уникальное, пока не достигнете пределов точность с плавающей точкой. Не уверен, сколько уникальных чисел вы могли бы выжать из него - возможно, вам стоит попробовать.

Answer 4

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