# Thread: Sum Distinct Algorithm

1. ## Sum Distinct Algorithm

Dear

I know basic sum distinct set is Z =(1 2 4 8 16 32 64 and so on) which follows the equation like : Nth element = (n-1)th element + (n-2) element + 1. But since I would like to implement this sum distinct property in wireless sensor network in binary format. To represent 64 in binary I need (1000000) 7 bits.

Are there any other sum distinct set can be possible so that I need less number of bits?

Let say, we have sensor node: X1,X2,X3,X4,X5,X6, X7 total 7 nodes. Our coding scheme is as follows : X1=1,X2=2,X3=4,X4=8,X5=16=,X6=32, X7=64. So when any node has any sensing event it will transmit the preassign code. Ans we allow simultaneous transmission. So if all the nodes are transmitting over the air they will sum up which is the summation of Z i.e 127. If any one of the node are not transmitting let say X5, we will get 127-16 = 111 at the receiver side. Since receiver does not have any other information except summation and pre-coding scheme, how can we now which one is the node not transmitting? This is very easy for this sum distinct set by subtracting the total sum to receive sum i.e. 127-111 = 16 so node X5 is not transmitting. What is the problem so that I am not interesting with this solution? This is because it needs lot of bits and which leads a bandwidth problem for wireless sensor networks (WSNs).

I would like you to help me how can I design another sum distinct set which has same property that I said earlier with minimum number of binary bit.

Are their any relation with this problem with lattice sphere packing or coverage problem?

Please suggest me some Engineering mathematical literature to formalize the problem and design the algorithm.

Thanks

2. I know basic sum distinct set is Z =(1 2 4 8 16 32 64 and so on) which follows the equation like : Nth element = (n-1)th element + (n-2) element + 1.
The equation is: nth element = 2 * (n - 1)th element.

You probably googled for "distinct subset sums." I found these two articles (PDF). Apparently, there is Erdős conjecture that for some constant c, the maximum of an n-element set with distinct subset sums is at least c * 2^n. As you noted, there are n-element sets where the maximum is 0.5 * 2^n. The second article above proves that there are sets where the maximum is < 0.22002 * 2^n for sufficiently large n.