Back to Search
Start Over
Frobenius Numbers and Automatic Sequences
- Publication Year :
- 2021
- Publisher :
- arXiv, 2021.
-
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 ${\bf s} = (s_i)_{i \geq 0}$, we can define the associated sequence $G_{\bf s} (i) = g(\{ s_i,s_{i+1},\ldots \})$. In this paper we compute $G_{\bf 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.
- Subjects :
- FOS: Computer and information sciences
Mathematics - Number Theory
Discrete Mathematics (cs.DM)
Formal Languages and Automata Theory (cs.FL)
Primary 11D07, Secondary 11B85, 11B83
FOS: Mathematics
Mathematics - Combinatorics
Computer Science - Formal Languages and Automata Theory
Number Theory (math.NT)
Combinatorics (math.CO)
Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....204535973b0a52c1c04e5f5b7a9b3a7a
- Full Text :
- https://doi.org/10.48550/arxiv.2103.10904