Frobenius numbers and automatic sequences

MaRDI QIDQ3390106zbMATHFDO

Authors Jeffrey Shallit

Publication date 24 March 2022

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

zbMATH Keywords

automatic sequencesregular sequencesFrobenius numberBeatty sequenceWalnutevil numberoddious number

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 7233012 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 1740032 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3397597 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• scientific article; zbMATH DE number 3076700 (Why is no real title available?)
• Additive number theory via automata theory
• Automatic Sequences
• Beyond odious and evil
• Complexity of the Frobenius problem
• Conductors for sets of large integer squares
• Enumeration and decidable properties of automatic sequences
• Numerical semigroups.
• On a linear diophantine problem of Frobenius
• On integers which are representable as sums of large squares
• On synchronized sequences and their separators
• On the Frobenius problem for Beatty sequences
• Sumsets associated with Wythoff sequences and Fibonacci numbers
• Synchronized sequences

Cited in

(7)

• The Frobenius problem for homomorphic embeddings of languages into the integers
• A Birman exact sequence for \(\Aut(F_n)\).
• Multiplicative functions and \(k\)-automatic sequences
• scientific article; zbMATH DE number 6984442 (Why is no real title available?)
• \(k\)-Fibonacci numbers and \(k\)-Lucas numbers in Beatty sequences generated by powers of metallic means
• Automated conjecturing of Frobenius numbers via grammatical evolution
• On certain recurrent and automatic sequences in finite fields

Describes a project that uses

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)