Biquams, forwarded message from Bill Thurston

[N. J. A. Sloane]

>>From rcs at CS.Arizona.EDU  Thu Nov  1 16:23:21 2001
>>Delivered-To: njas at research.att.com
>>Date: Thu, 1 Nov 2001 13:01:53 -0800
>>From: Bill Thurston <wpt at math.ucdavis.edu>
>>To: "David W. Wilson" <wilson at aprisma.com>, math-fun at CS.Arizona.EDU
>>Subject: Biquanimous Generating Function
>>Content-Disposition: inline
>>User-Agent: Mutt/1.2.5i
>>
>>A follow-up to previous postings on David Wilson's notion of biquanimous numbers,
>>i.e. strings of digits in base b such that the digits can be divided into two equal
>>piles with equal sums. Here's the "answer".  I went ahead and constructed
>>finite state automata using mathematica that recognize biquanimous numbers in
>>bases 2 through 10.  This becomes feasible by using the concept of m-full digit
>>strings to mean that for any further digits, only the values modulo 2m makes any
>>difference to biquanimity. I.e. 1-full means it only matters whether the digit sum
>>is even or odd.  It's straightforward (along lines I've previously discussed)
>>to show that after a bounded number of non-0 digits
>>every string is m-full for some m less than the base.  In base 10, the last
>>holdouts are the 13-digit number 8888888999999 and permutations; base 10 numbers with
>>14 non-0 digits are always m-full for some m.
>>
>>  The minimal finite state automata that recogize biquanimity in these bases
>>respectively 2, 4, 10, 21, 51, 89, 203, 370, 688 states.
>>However, most of the states are never visited after a bounded number of
>>non-0 digits.  In the case of base 10, there are 144 states that recur.
>>They're easy to count, given the FSA; the sequence of counts of n-digit biquanimous
>>numbers in base 10, (allowing leading 0's)
>>is 9, 90, 864, 7944, 70754, 623046, 5628919, 52870112, 512063556, 
>> 5047914960, 50183831091, 500694867724, 5002634946760, 50010181701330, 
>> 500040556819036, 5000167530626608, 50000717821597760, 500003177577591980, 
>> 5000014445637684811, 50000067035341062444, ... 
>>
>>These automata always have a simple form, where the longest cycles have
>>length 2 (obtained by m-full heaps of digits by adding m's), so all the
>>roots of the characteristic polynomial of the associated matrix are integers.
>>
>>It is convenient to count biquanimous numbers by looking only at
>>digit strings that exclude 0's (it's easy to sprinkle in 0's, they make
>>no difference in biquanimity), and for each length digit-string, look
>>at the difference, diff[k]=(non-biquanimous - biquanimous) --- this sequence for base
>>10 grows as 4^length rather than 10^length, so it is more manageable:
>>9, 63, 513, 3423, 18589, 71955, 224639, 617215, 1622001, 4300263, 
>> 12128763, 37076783, 122411649, 427600575, 1550703157, 5759666431, 
>> 21738733961, 82999762711, 319722139579, 1240393764207, ...
>>For base 10, the denominator of the generating function for the diff[k] is
>>(-1 + t)^8*(1 + t)^7*(-1 + 2*t)^3*(-1 + 3*t)^2*(-1 + 4*t), and the numerator is
>>this irreducible polynomial:
>>-1 + 26*t - 204*t^2 + 816*t^3 - 1476*t^4 - 2516*t^5 - 392*t^6 + 107114*t^7 - 
>> 159540*t^8 - 717344*t^9 + 1057416*t^10 + 3298914*t^11 - 4555798*t^12 - 
>> 7196788*t^13 + 9183048*t^14 + 7822144*t^15 - 10469545*t^16 - 2803302*t^17 + 
>> 10668436*t^18 + 1775790*t^19 - 14400494*t^20 - 11011208*t^21 + 
>> 13787184*t^22 + 26467498*t^23 + 3420146*t^24 - 34077124*t^25 - 
>> 26877128*t^26 + 26192684*t^27 + 33303780*t^28 - 11886288*t^29 - 
>> 20931912*t^30 + 2873424*t^31 + 6983328*t^32 - 272448*t^33 - 988416*t^34
>>
>>	Bill Thurston
>>
>>