# Thread: Finding the least number of random numbers that sum to a particular result

1. ## Finding the least number of random numbers that sum to a particular result

I have a list of let's say 256 random 32 bit numbers. I need to come up with some sum of a number of them that mod 2^32 sums to a particular number. This sum should involve the fewest terms. Hopefully 4 or so would suffice.

If this were xoring instead of summing you could do this with Gaussian elimination and the sum would involve about 32 terms and you wouldn't need many more than 32 random numbers.

Hopefully with more random numbers the number of terms can be reduced.

The 32 bit example above is a "toy" version. The solution has to scale to large numbers.

I imagine this is a well solved, common problem if only I knew how it was referred to in the literature.

2. If they're random, then you have no guarantee you can do it at all, e.g. say there's a number p such that p divides every number in your list. Then every possible sum must also be a multiple of p. Now, the probability of getting all even numbers is $2^{-256}$, and it gets much less likely as the divisors get larger, but it's a nit that has to be picked. (Nitpick to the nitpick: that's only guaranteed to be a problem if p is a power of 2, else modding by 2^32 will change the remainder mod p.)