Biquanimous numbers
Brendan McKay
bdm at cs.anu.edu.au
Tue Oct 9 03:58:19 CEST 2001
* Don Reble <djr at nk.ca> [011009 11:41]:
> > So, let's call a number biquanimous if its digits can be split into
> > two sets with the same sum.
> > ...
> > ... the base-2 and base-3 biquanimous
> > numbers are, respectively, 2-regular and 3-regular sets. My gut
> > feeling is that this generalizes to all finite bases...
>
> My gut feeling is that it doesn't. Determining biquanimosity
> is a special case of the subset-sum problem, and that problem
> is NP-complete. Maybe this problem is, too.
>
> Do tell us, if you find a clever way to solve it for really
> large bases.
The subset-sum problem can be solved in polynomial time if there is
a constant bound on the value of the numbers. Using the same method
(dynamic programming) gives a polynomial-time algorithm for testing
biquanimosity in any fixed base. I think that O(k n^2) is easy to
achieve, where k is the base and n is the number of digits. Can it
be done faster than that?
Note that the expression "k n^2" is exponential in the length (number
of bits) of the number k, so this is not polynomial if k is part of
the input. For fixed k it is polynomial, though.
Brendan.
More information about the SeqFan
mailing list