1

Is it possible without using exponentiation to have a set of numbers that when added together, always give unique sum?

I know it can be done with exponentiation (see first answer): The right way to manage user privileges (user hierarchy)

But I'm wondering if it's possible without exponentiation.

Community
  • 1
  • 1
Chad
  • 2,365
  • 6
  • 26
  • 37

4 Answers4

3

No, you can only use exponentiation, because the sum of lower values have to be less than the new number to be unique: 1+2=3 < 4, 1+2+4=7 < 8.

[EDIT:] This is a laymen's explanation, of course there are other possibilities, but none as efficient as using exponentials of 2.

Residuum
  • 11,878
  • 7
  • 40
  • 70
  • The problem with exponentiation is that when working in PHP I run out of digits very quickly (after about 2^1023). I there a trick to overcome this? – Chad Oct 29 '09 at 10:20
  • 3
    Maybe having 1000s of bits is not a good solution in the first place. When asking a question, explain your *problem*, not the trouble you're having with a particular *solution*. – Artelius Oct 29 '09 at 10:23
  • Not using PHP? :). Just joking. See http://stackoverflow.com/questions/211345/working-with-large-numbers-in-php BTW 2^1023 is a VERY big number. – Tamás Szelei Oct 29 '09 at 10:23
  • 2
    @Chad: It sounds like you're going down the wrong path. No matter how you interpret binary data, you can't fit more than `2^n` different values in `n` bits. If you really need to represent that many unique values, you'll just have to use a bit vector or bigint library (see http://www.php.net/manual/en/ref.gmp.php). – outis Oct 29 '09 at 11:02
1

There's a chance it can be done without exponentation (I'm no math expert), but not in any way that's more efficient than exponentation. This is because it only takes one bit of storage space per possible value, and as an added plus you can use boolean operators to do useful stuff with the values.

Kaivosukeltaja
  • 15,541
  • 4
  • 40
  • 70
1

If you restrict yourself to integers, the numbers have to grow at least as fast as an exponential function. If you find a function that grows faster (like, oh, maybe the Ackermann function) then the numbers produced by that will probably work too.

With floating-point numbers, you can keep adding unique irreducible roots of primes (sqrt(2), sqrt(3), sqrt(5), ...) and you will always get something unique, up until you hit the limits of floating-point precision. Not sure how many unique numbers you could squeeze out of it - maybe you should try it.

Artelius
  • 48,337
  • 13
  • 89
  • 105
  • Could you please give me an example of this? – Chad Oct 29 '09 at 10:38
  • 2
    Another fun one: fibonacci coding (http://en.wikipedia.org/wiki/Fibonacci_coding). Note that none of these will likely be of much use to OP, as it sounds like he's running up against a pigeonhole problem. – outis Oct 29 '09 at 11:10
  • Nice ideas from a theoretical point of view, but not as efficient as using exponentials of 2. – Residuum Nov 02 '09 at 10:56
  • @Residuum: I thought the question was asked from a theoretical point of view. Turns out there was (as usual) a hidden problem behind the question that the questioner didn't want to reveal. – Artelius Nov 02 '09 at 22:08
1

No. To see this directly, think about building up the set of basis values by considering at each step the smallest possible positive integer that could be included as the next value. The next number to add must be different from all possible sums of the numbers already in the set (including the empty sum, which is 0), and can't combine with any combination of numbers already present to produce a duplicate. So...

{} : all possible sums = {0}, smallest possible next = 1
{1} : all possible sums = {0, 1}, smallest possible next = 2
{1, 2} : all possible sums = {0, 1, 2, 3}, smallest possible next = 4
{1, 2, 4} : a.p.s. = {0, 1, 2, 3, 4, 5, 6, 7}, s.p.n. = 8
{1, 2, 4, 8} ...

And, of course, we're building up the binary powers. You could start with something other than {1, 2}, but look what happens, using the "smallest possible next" rule:

{1, 3} : a.p.s. = {0, 1, 3, 4}, s.p.n. = 6 (because 2 could be added to 1 giving 3, which is already there)
{1, 3, 6} : a.p.s. = {0, 1, 3, 4, 6, 7, 9, 10}, s.p.n = 11
{1, 3, 6, 11} ...

This sequence is growing faster than the binary powers, term by term.

If you want a nice Project-Euler-style programming challenge, you could write a routine that takes a set of positive integers and determines the "smallest possible next" positive integer, under the "sums must be unique" constraint.

joel.neely
  • 30,725
  • 9
  • 56
  • 64