Minimal automaton for multiplying and translating the Thue-Morse set

The Thue-Morse set T is the set of those non-negative integers whose binary expansions have an even number of 1. The name of this set comes from the fact that its characteristic sequence is given by the famous Thue-Morse word abbabaabbaababba..., which is the fixed point starting with a of the word morphism a -> ab; b -> ba. The numbers in T are commonly called the evil numbers. We obtain an exact formula for the state complexity of the set mT + r (i.e. the number of states of its minimal automaton) with respect to any base b which is a power of 2. Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all 2^p-expansions of the set of integers mT +r for any positive integers p and m and any remainder r between 0 and m-1. The proposed method is general for any b-recognizable set of integers. As an application, we obtain a decision procedure running in quadratic time for the problem of deciding whether a given 2^p-recognizable set is equal to a set of the form mT + r.