The automaticity of the set of primes (Q6930229)

The main result of the paper is the following: the size of a finite automaton recognizing the set of \(b\)-ary representations of primes from \(1\) to \(x\) is at least\N\[\Nx \exp(-c(\log\log x)^2 \log \log\log x).\N\]\NTwo other results of the paper is a simpler bound for the set of squares (the size of the automaton grows as \(x^{1/2}\)) and a lower bound for the set of primes (the size \(x/(\log x \log\log\log x)\) of the automaton is sufficient).