CODEWITHSUNDEEP
arraysalgorithm
Dario Colombotto
Dario Colombotto

Reputation: 319

find a list of integers for a checksum

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

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

Upvotes: 3

Views: 260

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186793

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

Upvotes: 6

Related Questions