Results 1 to 2 of 2

Math Help - Finding the least number of random numbers that sum to a particular result

  1. #1
    Newbie
    Joined
    Jun 2011
    Posts
    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.

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    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.)

    I think it's a more interesting problem if you get to pick your set of numbers. Clearly you only need 32 of them: 1, 2, 4, 8, ..., 2^31. So if you're allowed to choose more, what's the best way to do it? Or maybe that's too easy to be interesting...but at least it's well-defined.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: June 26th 2011, 02:56 AM
  2. [SOLVED] Result of a function (complex numbers)
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 7th 2011, 01:15 PM
  3. Finding the number of numbers with odd divisors
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 16th 2011, 05:05 AM
  4. Complex numbers-finding real number pairs
    Posted in the Calculus Forum
    Replies: 9
    Last Post: March 20th 2010, 11:36 PM
  5. Complex numbers and trigonometric result?
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: May 28th 2009, 10:48 AM

Search Tags


/mathhelpforum @mathhelpforum