найти список целых чисел для контрольной суммы

Question

Я бы нужен список п положительных целых чисел L, что имеет следующие свойства:

• для каждого возможного подмножества S из L, если я суммировать все элементы S, эта сумма не L
• для каждого возможного подмножества S из л, если суммировать все элементы S, эта сумма является уникальным (каждое подмножество может быть идентифицирован по его сумме)

Рабочий пример 1:

n = 4 
L = [1, 5, 7, 9] 

check: 
1+5 = 6 ok 
5+7 = 12 ok 
7+9 = 16 ok 
9+1 = 10 ok 
1+7 = 8 ok 
5+9 = 14 ok 

1+5+7 = 13 ok 
5+7+9 = 21 ok 
1+5+9 = 15 ok 
1+7+9 = 17 ok 

1+5+7+9 = 22 ok 

All sums are unique -> L is OK for n = 4 

Answer 1

Как легко построить последовательности, я предлагаю использовать степенные серии, например

1, 2, 4, 8, ..., 2**k, ... 
1, 3, 9, 27, ..., 3**k, ... 
1, 4, 16, 64, ..., 4**k, ... 
... 
1, n, n**2, n**3,..., n**k, ... where n >= 2 

Возьмем, к примеру, 2: ни сила 2 является суммой других 2 полномочий; учитывая sum (число), вы можете легко найти подмножество путем преобразования sum в двоичном представлении:

23 = 10111 (binary) = 2**0 + 2**1 + 2**2 + 2**4 = 1 + 2 + 4 + 16 

В общем случае, простой жадный алгоритм будет делать: учитывая sum вычитать наибольший элемент меньше или равно к sum; продолжить вычитание до нуля:

n = 3 
sum = 273 

273 - 243 (3**5) = 30 
    30 - 27 (3**3) = 3 
    3 - 3 (3**1) = 0 

273 = 3**5 + 3**3 + 3**1 = 243 + 27 + 3