## find a list of integers for a checksum

Question

I would need a list of n positive integers L that has this properties:

• for each possible subset S of L, if I sum all items of S, this sum is not in L
• for each possible subset S of L, if I sum all items of S, this sum is unique (each subset can be identified by his sum)

Working example 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

Show source

## Answers to find a list of integers for a checksum ( 1 )

1. As an easy to construct sequence, I suggest using power series, e.g.

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

Take, for instance, 2: neither power of 2 is a sum of other 2 powers; given a sum (number) you can easily find out the subset by converting sum into binary representation:

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

In general case, a simple greedy algorithm will do: given a sum subtract the largest item less or equal to the sum; continue subtracting up to zero:

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