Beatty’s theorem

Here's a surprising theorem [1].

(Beatty's theorem) Let a and b be any pair of irrational numbers greater than 1 with 1/a + 1/b = 1. Then the sequences { na } and { nb } contain every positive integer without repetition.

Illustration

Here's a little Python code to play with this theorem.We set a = e and make b what it has to be to make the reciprocals add to 1.

We can't tell from a finite sample whether the sequence covers all the integers, but we can at least verify that there are no repeats.

 from math import exp, floor a = exp(1) b = 1/(1 - 1/a) N = 100 nums = set() for n in range(1, N+1): nums.add(floor(n*a)) nums.add(floor(n*b)) print(len(nums))

We put 200 numbers into our set, and since they're all unique, the set will have 200 elements when we're done.

Except it doesn't! We get 199 elements. Is there some subtle issue with floating point accuracy, where two numbers that should have different floors happen to have the same floor?

No, it's nothing that complicated. When n = 0, 0 a and 0 b are both 0.

The theorem implicitly assumes that n ranges over positive integers, not non-negative integers [2]. If we modify our loop to

 for n in range(1, N+1):

then we do indeed get 200 distinct integers.

Coverage

Beatty's theorem says that every integer k will eventually be part of one of the two sequences. That is, there will be some n such that k either equal na or nb. How big might n be relative to k?

To get an idea, let's modify the script above to report the smallest number that hasn't occurred and the largest number that has occurred. We do this by taking the following line on at the end.

 print(min(set(range(1, 2*N)) - nums), max(nums))

This prints 159 and 271. That is, all the numbers from 1 through 158 have appeared, as well as numbers up to 271.

Now let's do a longer run, changing N to 1000. Our code prints 1583 and 2718. So once again the numbers are filling in somewhat in order. Over three quarters of the numbers from 1 to 2000 have occurred.

Let's crank N up to 1,000,000. Now we get 1581978 and 2718281. Each time, the smallest number not visited seems to be going up proportionally, as well as the largest number that has been visited.

That maximum number 2718281 looks familiar. In fact, it's approximately 1,000,000 times e. In terms of our program parameters, it's approximately Na.

And what about the lower number? It doesn't look familiar, but we might guess Nb, and indeed b = 1.5819767....

Theorem

Based on the experiments above, we guess the following theorem. Define

S(N) = { na | 1 n N } { Nb | 1 n N }.

Then the smallest positive integer not in S(N) is

(N+1) min(a, b)

and the largest element in S(N) is

N max(a, b).

Without loss of generality, assume a < b.

The largest element of S(N) will occur is as large as possible, i.e. n = N, and so the largest value in S(N) will be Nb.

The number (N+1) a is not in S(N) since none of the elements of the Beatty sequences repeat, and it is the smallest number not in S(N).

One more run

Let's illustrate our new theorem with a = 2.

Or program prints 1414214 and 3414213. The smallest number not encountered is 1414214, which equals 1000001 2 .

Now b = 1/(1 - 1/2) = 3.4142135.... and the maximum is indeed 1000000 b.

Notes

[1] Ezra Brown and Richard K. Guy. The Unity of Combinatorics. MAA Press, 2020.

[2] This is another example of a theme I return to regularly: it helps to test a theorem with a program, even if you're certain the theorem is correct, because you're not only testing the theorem, you're testing your understanding of the theorem. Beatty's theorem has been around over a century, and if it were wrong then we'd know by now. But my initial Python script revealed a requirement that was not explicit in the given statement of the theorem.

The post Beatty's theorem first appeared on John D. Cook.