[seqfan] Re: Sirag numbers.

allouche at math.jussieu.fr allouche at math.jussieu.fr
Sat Oct 1 17:09:20 CEST 2011


A set of integers is said b-automatic if the set
of base b-representations of these integers is rational.
This is equivalent to saying that its characteristic function
is b-automatic (a finitely valued sequence (u(n))_{n \geq 0}
is said to be b-automatic if the set of subsequences
(u(b^k n + j))_{n \geq 0} when k runs through 0, 1, 2,... and
j through 0, 1, 2, ..., b^k - 1  is a finite set.

Remark:
Also note that a sequence with values in Z (say) such that
the corresponding set of subsequences as above generates
a module of finite type is said to be b-regular.
The notions should not be confused. For example the set
of integers without the digit 1 in base 3, is 3-automatic.

Now if you look at the sequence of these integers
(v(n))_{n \geq 0} = 0 2 6 8 18 20 24... as a sequence
of integers, it is 2-regular since
v(2n) = 3 u(n)
v(2n+1) = 3 u(n) + 2

Example:
The set of odious numbers is a 2-automatic set.

Refs:

The papers of Cobham (1972 and 1969) in the journal
Math. Syst. Theory (now Theory of Computing Systems)
plus a lot of papers that you might find in the references
of the book I already mentioned by Jeff Shallit and myself.

best wishes
jean-paul


David Wilson <davidwwilson at comcast.net> a écrit :

> On 9/30/2011 1:08 AM, allouche at math.jussieu.fr wrote:
>
> So then, what would be the name for a set of integers (= increasing
> sequence), whose base-b representations form a regular language?
> (for example, A00069, the odious numbers, whose binary representations
> form the language 10*(10*10*)*  ?
>
> I only ask because there are many sequences of this type in the OEIS,
> and they have some interesting arithmetic properties as established
> by Cobham circa 1964.
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/



----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.




More information about the SeqFan mailing list