Block-counting sequences are not purely morphic

Abstract: Let

m

be a positive integer larger than

1

, let

w

be a finite word over

l e f t 0, 1, ..., m - 1 i g h t

and let

a_{m; w} (n)

be the number of occurrences of the word

w

in the

m

-expansion of

n

mod

p

for any non-negative integer

n

. In this article, we first give a fast algorithm to generate all sequences of the form

(a_{m; w} (n))_{n i n m a t h b f N}

; then, under the hypothesis that

m

is a prime, we prove that all these sequences are

m

-uniformly but not purely morphic, except for

w = 1, 2, ..., m - 1

; finally, under the same assumption of

m

as before, we prove that the power series

s u m_{i = 0}^{i n f t y} a_{m; w} (n) t^{n}

is algebraic of degree

m

over

m a t h b b F_{m} (t)

.

Cites Work

This page was built for publication: Block-counting sequences are not purely morphic