Biquanimous numbers

[Brendan McKay]

* 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.