Frobenius numbers and automatic sequences

zbMATH Open1490.11036arXiv2103.10904MaRDI QIDQ3390106FDOQ3390106

Authors: Jeffrey Shallit 

Publication date: 24 March 2022

Abstract: The Frobenius number $g(S)$ of a set $S$ of non-negative integers with $gcd1$ is the largest integer not expressible as a linear combination of elements of $S$. Given a sequence $$, we can define the associated sequence $$. In this paper we compute $$ 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.

Full work available at URL: https://arxiv.org/abs/2103.10904

Recommendations

• Computing the Frobenius number
• The Frobenius problem for classes of polynomial solvability.
• The Frobenius number of geometric sequences
• The Frobenius number associated with the number of representations for sequences of repunits
• scientific article; zbMATH DE number 5041220

zbMATH Keywords

automatic sequencesregular sequencesFrobenius numberBeatty sequenceWalnutevil numberoddious number

Mathematics Subject Classification ID

Automata sequences (11B85) The Frobenius problem (11D07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automatic Sequences
• Numerical semigroups.
• Beyond odious and evil
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of the Frobenius problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• On synchronized sequences and their separators
• On the Frobenius problem for Beatty sequences
• The critical exponent is computable for automatic sequences
• Enumeration and decidable properties of automatic sequences
• On a linear diophantine problem of Frobenius
• Conductors for sets of large integer squares
• On integers which are representable as sums of large squares
• Additive number theory via automata theory
• Sumsets associated with Wythoff sequences and Fibonacci numbers
• Title not available (Why is that?)
• Synchronized sequences

Cited In (5)

• A Birman exact sequence for \(\Aut(F_n)\).
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiplicative functions and \(k\)-automatic sequences
• On certain recurrent and automatic sequences in finite fields

Uses Software

• OEIS
• Walnut

This page was built for publication: Frobenius numbers and automatic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3390106)