The automaticity of the set of primes
| Autor: | Dubbe, Thomas |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The automaticity $A(x)$ of a set $\mathcal{X}$ is the size of the smallest automaton that recognizes $\mathcal{X}$ on all words of length $\leq x$. We show that the automaticity of the set of primes is at least $x\exp\left(-c(\log\log x)^2\log\log\log x\right)$, which is fairly close to the maximal automaticity. |
| Databáze: | arXiv |
| Externí odkaz: |
|