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
| arrays   | algorithm   2016-12-22 10:12 1 Answers

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

  1. 2016-12-22 11:12

    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
    

Leave a reply to - find a list of integers for a checksum

◀ Go back