ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

Beatty Sequences: Mathematical Curiosities with Irrational Numbers and Integers

Updated on April 02, 2015
calculus-geometry profile image

TR Smith is a product designer and former teacher who uses math in her work every day.

A partition of a set of numbers is when you divide it into two or more non-overlapping subsets where every element of the original set is contained in one subset. Both finite and infinite sets can be partitioned. For example, the set of integers greater than 1 can be partitioned into primes and composites. The set of all integers can be partitioned into even numbers and odd numbers. Real numbers can be partitioned into rational and irrational numbers.

There are infinitely many ways to partition an infinite set, and sometimes these subsets can be expressed as sequences with definite patterns, which is more interesting from a mathematician's point of view.

One pattern-based partitioning is with Beatty sequences, which use a pair of irrational numbers to generate a pair of disjoint integer sequences that partition the positive integers into two sets. Beatty sequences are easy enough for most high school students to understand and can be used to teach students about properties of irrational numbers, set theory, and proofs by contradiction.


How to Construct A Pair of Beatty Sequences

The foundation of the Beatty sequences is a pair iof positive irrational numbers r and s such that their reciprocals add up to 1, that is, 1/r + 1/s = 1. To construct the first Beatty sequence, take all all the positive integer multiples of r and round them down to the nearest whole number. This gives you,

Br = { ⌊1r⌋, ⌊2r⌋, ⌊3r⌋, ⌊4r⌋, ... },

where ⌊x⌋ means x rounded down. To construct the second Beatty sequence, take all the integer multiples of s and round them down to the nearest whole number. This gives you

Bs = { ⌊1s⌋, ⌊2s⌋, ⌊3s⌋, ⌊4s⌋, ... }

The remarkable fact is that the union of the sequences Br and Bs is the entire set of positive integers, and that no integer appears in both sequences. In other words, whatever number is missed by the Br sequence is caught by the Bs sequence, and vice versa. An equivalent interpretation is that for any consecutive positive integers N and N+1, the interval from N to N+1 contains exactly one irrational number of the form k*r or k*s for some integer k.

Examples of Beatty Sequences

Example 1: Let's take r = π and s = π/(π-1). This is a valid pair since 1/r + 1/s = 1. The first Beatty sequence is

Br = { ⌊r⌋, ⌊2r⌋, ⌊3r⌋, ⌊4r⌋, ... }
= { ⌊π⌋, ⌊2π⌋, ⌊3π⌋, ⌊4π⌋, ... }
= { 3, 6, 9, 12, 15, 18, 21, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, ...}.

The second Beatty sequence is

Bs = { ⌊s⌋, ⌊2s⌋, ⌊3s⌋, ⌊4s⌋, ... }
= { ⌊π/(π-1)⌋, ⌊2π/(π-1)⌋, ⌊3π/(π-1)⌋, ⌊4π/(π-1)⌋, ... }
= { 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, 27, ... }.

As you can see, the second Beatty sequence fills in the holes of the first so that every positive integer lies in either Br or Bs.


Example 2: If you select r = sqrt(3) and s = (3+sqrt(3))/2 you get the sequences

Br = {1, 3, 5, 6, 8, 10, 12, 13, 15, 17, 19, 20, 22, 24, 25, 27, ... }
Bs = { 2, 4, 7, 9, 11, 14, 16, 18, 21, 23, 26, 28, ... }.


Example 3: If you let r equal the golden mean (1+sqrt(5))/2 and s = (3+sqrt(5))/2, you get the sequences

Br = { 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, ... }
Bs = { 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, ... }

Br and Bs are called the upper and lower Wythoff sequences, respectively. Br contains every other Fibonacci number 1, 3, 8, 21, 55,... while Bs contains every other Fibonacci number 2, 5, 13, 34, 89,...


Example 4: Let r = e and s = e/(e-1), where e is Euler's Number, the base of the natural logarithm. The Beatty sequences Br and Bs are

Br = { 2, 5, 8, 10, 13, 16, 19, 21, 24, 27, 29, 32, 35, 38, 40, ... }
Bs = { 1, 3, 4, 6, 7, 9, 11, 12, 14, 15, 17, 18, 20, 22, 23, 25, 26, ... }


Beatty sequences are named after the mathematician Samuel Beatty (above), not the actor Warren Beatty (below).

Proof that Beatty Sequences Parition the Positive Integers: Preliminary

Why do these sequences produce a perfect partition of the positive integers when you choose r and s so that 1/r + 1/s = 1? To prove that the Beatty sequences form a partition, we have to prove two things: (1) that no integer is part of both sequences and (2) that no integer is left out.

As preliminary to the proof, we first need to know a basic property of irrational numbers: the product of a rational number and an irrational number is always irrational. In particular, the product of an integer and an irrational number is always irrational.

Another preliminary fact we need to establish is that if r and s are irrational numbers such that 1/r + 1/s = 1, then there is no pair of integers m and n such that n*r = m*s. To prove, this, solve the equation 1/r + 1/s = 1 for s to get s = r/(r-1). If n*r were to equal m*s for some integers m and n, then we would have

nr = ms
nr = mr/(r-1)
n = m/(r - 1)
r - 1 = m/n
r = m/n + 1

The last line is a contradiction since m/n - 1 is a rational number and r is defined to be irrational. Thus, it is impossible to have n*r = m*s for any m and n. Now that we have these preliminaries out of the way, we can dive into the proof.


Proof of (1)

This is a proof by contradiction. Suppose there is a positive integer J that is an element of both Beatty sequences. That is, there exists a J such that J = ⌊nr⌋ = ⌊ms⌋ for some integers m and n. Since J is the rounded down value of nr amd ms, and nr and ms are not whole numbers, we have

J < nr < J+1
and
J < ms < J+1

In other words, nr and ms are both between the consecutive integers J and J + 1. Since we know that nr and ms cannot be equal, let's say without any loss of generality that ms < nr. This inequality can be milked to derive some other relations. One is

s/r < n/m

The relation 1/r + 1/s = 1 gives us several other equivalent relations such as r = s/(s-1), s = r/(r-1), r/s = r - 1, and s/r = s - 1. Thus the inequality above becomes

s/r < n/m
s - 1 < n/m
ms - m < n
ms < n + m

Starting again from the inequality ms < nr and using the fact that r/s = r - 1, we also have

ms < nr
m/n < r/s
m/n = r - 1
m < nr - n
n + m < nr

Now, n + m is some integer that is simultaneously greater than ms and less than nr. But how can that be possible if nr and ms are bound inside the integer interval (J, J+1)? Of course it's not possible; we have a contradiction. Therefore, there cannot be an integer J that belongs to both Beatty sequences.



Proof of (2)

Now we need to prove that no integer is left out. This is another proof by contradiction. Suppose there exists an integer J that is not an element of either beatty sequence. In other words, there are no integers m and n such that the rounded down values of nr or ms are equal to J. In the language of inequalities, we have

nr < J < J+1 < (n+1)r
and
ms < J < J+1 < (m+1)s

If we divide these inequalities by r and s respectively, we get

n < J/r < (J+1)/r < n+1
and
m < J/s < (J+1)/s < m+1

If we add them we get

n + m < J/r + J/s < (J+1)/r + (J+1)/s < n + m + 2

n + m < J(1/r + 1/s) < (J+1)(1/r + 1/s) < n + m + 2

n + m < J < J+1 < n + m + 2

Look carefully at the integer inequality immediately above. At the lower end we have the integer n + m and at the upper end we have the integer n + m + 2. Only one integer can fit between them, not two! We have a contradiction, therefore, there cannot be any integer J that is left out of both sequences. This completes the proof that the Beatty sequences are complements of one another and partition the positive integers.


Other Facts About Beatty Sequences

Is it possible to find irrational numbers r and s, such that 1/r + 1/s = 1 and the Beatty sequences Br and Bs are precisely the evens and odds? It turns out no, but you can get very close. Choose r to be the irrational number

r = 2. 01 001 0001 00001 000001 0000001...

and s to be its complement given by s = r/(r-1). Then the Beatty sequences are

Br = { 2, 4, 6, 8, 10, 12, 14, ....}
Bs = { 1, 3, 5, 7, 9, 11, 13, 15, ... }

The first several terms of each series look like the evens and the odds, but if you keep computing the elements ⌊kr⌋ and ⌊ks⌋ you will see that eventually Br contains 196, 198, 201, 203, 205, ... and Bs contains the terms 195, 197, 199, 200, 202, 204, 206, ... In fact both series will switch off from evens and odds infinitely many times.


Another question is, do r and s have to be irrational? What if we choose rational numbers r and s such that 1/r + 1/s = 1, will the sequences Br and Bs still partition the integers? The answer is also no, because there will be infinitely many integers included in both sets.


What About 3-Way Beatty Sequences?

Suppose you take three distinct irrational numbers r, s, and t such that 1/r + 1/s + 1/t = 1. If you construct the sequences

Br = { ⌊1r⌋, ⌊2r⌋, ⌊3r⌋, ⌊4r⌋, ... }
Bs = { ⌊1s⌋, ⌊2s⌋, ⌊3s⌋, ⌊4s⌋, ... }
Bt = { ⌊1t⌋, ⌊2t⌋, ⌊3t⌋, ⌊4t⌋, ... }

will these three sets partition the positive integers? The answer turns out to be no. In fact, no matter what values of r, s, and t you choose, the sets Br, Bs, and Bt will not form a partition. Nor will it work if you take four, five, or six distinct irrational numbers whose sum of reciprocals equals 1. The construction of Beatty sequences does not generalize; it only works for two irrational numbers to form two sets.


Almost Identical Beatty Sequences

Take r = 3^(1/3), the cube root of 3, and s = 1 - 1/r. The respective Beatty sequences of r and s are

Br = {1, 2, 4, 5, 7, 8, 10, 11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 25, 27, 28, 30,...}
Bs = {3, 6, 9, 13, 16, 19, 22, 26, 29,...}

Now take r = 1/Ln(2), the reciprocal of the natural logarithm of 2, and s = 1 - 1/r. The respective Beatty sequences of r and s are

Br = {1, 2, 4, 5, 7, 8, 10, 11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 25, 27, 28, 30,...}
Bs = {3, 6, 9, 13, 16, 19, 22, 26, 29,...}

Not until the 599th term of these sequences do we get the first difference! As it turns out, it is impossible for two Beatty sequences to be identical unless they are generated by the same irrational number. If two irrational numbers are very close, the first several (or first few hundred or first several thousand) terms will be identical, but eventually they will diverge. For comparison,

1/Ln(2) ≈ 1.4426950
3^(1/3) ≈ 1.4422496


Another Curious Integer Partitioning Sequence

Consider the sequence

R = {1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150,...}

The gaps between consecutive terms in the sequence above form the new sequence

S = {2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21,...}

It turns out that the R and S are complements; all the integers missed by R are in S and vice versa. R is called the Hofstadter Figure-Figure sequence. These are not Beatty Sequences because they are not generated by a pair of irrational numbers, but they are another interesting example of partitioning sequences.


Comments

    0 of 8192 characters used
    Post Comment

    • poetryman6969 profile image

      poetryman6969 2 years ago

      An interesting mathematical exercise.

    Click to Rate This Article