Frobenius Numbers and Automatic Sequences

Abstract

The Frobenius number $g(S)$ of a set $S$ of non-negative integers with $\gcd 1$ is the largest integer not expressible as a linear combination of elements of $S$. Given a sequence $\mathbf{s}=(s_i{)}_{i\ge 0}$, we can define the associated sequence $G_{\mathbf{s}}(i)=g(\{s_i,s_{i+1},\dots \})$. In this paper we compute $G_{\mathbf{s}}(i)$ for some classical automatic sequences: the evil numbers, the odious numbers, and the lower and upper Wythoff sequences. In contrast with the usual methods, our proofs are based largely on automata theory and logic.