a(27) in A059097: A new lower higher bound

[David Wilson]

The n such that 9 does not divide c(2n, n) form a regular language in base 3 
which can
be generated quickly.  If we were to check only these n for inclusion in 
A059097, we
could get much farther than by checking every integer.


Indeed, let S be a set of nonnegative integers whose base-b representation are
accepted by an extant finite automaton F.  There is then an algorithm which, 
given
k >= 0, finds the smallest element of S > k in time O(log(k)). This algorithm 
can be
called repeatedly to quickly generate all elements of S in order.

Furthermore, given two such sets S and T, even with different bases, it is 
possible
to use the above algorithm to generate the elements of S intersect T (or any set
function of S and T) in O(log(k)) time per element k.

This method could be used to quickly generate the intersection of the sets of n
with C(2n, n) divisible by neither 9 nor 25, which is a very sparse subset of 
the
integers.  This would allow us to greatly extend the test range of A059097.

----- Original Message ----- 
From: "David Wilson" <davidwwilson at comcast.net>
To: "Richard Guy" <rkg at cpsc.ucalgary.ca>; "Alonso Del Arte" 
<alonso.delarte at gmail.com>
Cc: <seqfan at ext.jussieu.fr>
Sent: Wednesday, November 23, 2005 9:42 AM
Subject: Re: a(27) in A059097: A new lower higher bound


>0 is a proper domain value for A059097 and should be included in the sequence.