Almost Beatty partitions

MaRDI QIDQ5226858zbMATH OpenFDO

Authors Xiao-Min Li, Junxian Li, Yun Xie, Adolf Hildebrand

Publication date 2 August 2019

Full work available at URL https://arxiv.org/abs/1809.08690, https://cs.uwaterloo.ca/journals/JIS/VOL22/Hildebrand/hilde2.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Beatty sequencecomplementary sequencepartition of the integers

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Special sequences and polynomials (11B83) Elementary theory of partitions (11P81)

Abstract: Given $0<alpha<1$, the Beatty sequence of density $alpha$ is the sequence $B_{alpha}=(lfloorn/alphafloor{)}_{ninmathbbN}$. Beatty's theorem states that if $$ are irrational numbers with $$, then the Beatty sequences $B_{alpha}$ and $$ partition the positive integers, that is, each positive integer belongs to exactly one of these two sequences. On the other hand, Uspensky showed that this result breaks down completely for partitions into three (or more) sequences: There does not exist a single triple $$ such that the Beatty sequences $$ partition the positive integers. In this paper we consider the question of how close we can come to a three-part Beatty partition by considering "almost" Beatty sequences, that is, sequences that represent small perturbations of an "exact" Beatty sequence. We first characterize all cases in which there exists a partition into two exact Beatty sequences and one almost Beatty sequence with given densities, and we determine the approximation error involved. We then give two general constructions that yield partitions into one exact Beatty sequence and two almost Beatty sequences with prescribed densities, and we determine the approximation error in these constructions. Finally, we show that in many situations these constructions are best-possible in the sense that they yield the closest approximation to a three-part Beatty partition.

Recommendations

• Partitions into Beatty sequences
• Interpolating classical partitions of the set of positive integers
• Partitioning the positive integers to seven Beatty sequences
• A generalization of Beatty's theorem
• Gap problems for integer part and fractional part sequences

Cites work

• scientific article; zbMATH DE number 3821627 (Why is no real title available?)
• scientific article; zbMATH DE number 1990000 (Why is no real title available?)
• scientific article; zbMATH DE number 1522554 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 1820654 (Why is no real title available?)
• scientific article; zbMATH DE number 5270037 (Why is no real title available?)
• A Model for Pairs of Beatty Sequences
• A generalization of Beatty's theorem
• A generating function technique for Beatty sequences and other step sequences
• Beatty Sequences, Continued Fractions, and Certain Shift Operators
• Complementary Systems of Integers
• Complementary equations and Wythoff sequences
• Complementary iterated floor words and the Flora game
• Generalized Beatty sequences and complementary triples
• Iterated Floor Function, Algebraic Numbers, Discrete Chaos, Beatty Subsequences, Semigroups
• On A Theorem of Uspensky
• On certain distributions of integers in pairs with given differences
• On functions expressible as words on a pair of Beatty sequences
• On the sequence $[n \alpha]$, $n = 1,2,\dots$. Supplementary note to the preceding paper by Th. Skolem
• Slow Beatty Sequences, Devious Convergence, and Partitional Divergence
• The Bracket Function and Complementary Sets of Integers
• The Chairman assignment problem
• The Fifty-Eighth William Lowell Putnam Mathematical Competition
• The on-line encyclopedia of integer sequences
• The optimality of the online greedy algorithm in carpool and chairman assignment problems

Cited in

(8)

• Partitions into Beatty sequences
• scientific article; zbMATH DE number 2124084 (Why is no real title available?)
• Partitioning the positive integers to seven Beatty sequences
• Webster sequences, apportionment problems, and just-in-time sequencing
• A generalization of Beatty's theorem
• A discrete Fourier kernel and Fraenkel's tiling conjecture
• Gap problems for integer part and fractional part sequences
• Interpolating classical partitions of the set of positive integers

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Almost Beatty partitions

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