CODEWITHSUNDEEP
mathnumbers
Chad
Chad

Reputation: 2455

Getting Unique Number Combinations

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.

Upvotes: 1

Views: 763

Answers (4)

Residuum
Residuum

Reputation: 12064

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.

Upvotes: 3

joel.neely
joel.neely

Reputation: 30943

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.

Upvotes: 1

Artelius
Artelius

Reputation: 49089

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.

Upvotes: 1

Kaivosukeltaja
Kaivosukeltaja

Reputation: 15735

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.

Upvotes: 1

Related Questions