Search Results for “beatty sequence”

Source: Beatty sequence

In mathematics, a Beatty sequence (or homogeneous Beatty sequence) is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.
Rayleigh's theorem, named after Lord Rayleigh, states that the complement of a Beatty sequence, consisting of the positive integers that are not in the sequence, is itself a Beatty sequence generated by a different irrational number.
Beatty sequences can also be used to generate Sturmian words.

Definition

Beatty

sequence

Beatty

Examples

Beatty

sequence

History

Beatty

Rayleigh theorem

Beatty

= First proof

= Second proof

For non-zero j, the irrationality of r and s is incompatible with equality, so

j
<
k
⋅
r
<
j
+
1

and

j
<
m
⋅
s
<
j
+
1
,

{\displaystyle j

which leads to

j
r

<
k
<

j
+
1

r

and

j
s

<
m
<

j
+
1

s

.

{\displaystyle {j \over r}

Adding these together and using the hypothesis, we get

j
<
k
+
m
<
j
+
1

{\displaystyle j

which is impossible (one cannot have an integer between two adjacent integers). Thus the supposition must be false.
Anti-collisions: Suppose that, contrary to the theorem, there are integers j > 0 and k and m such that

k
⋅
r
<
j

and

j
+
1
≤
(
k
+
1
)
⋅
r

and

m
⋅
s
<
j

and

j
+
1
≤
(
m
+
1
)
⋅
s

.

{\displaystyle k\cdot r

Since j + 1 is non-zero and r and s are irrational, we can exclude equality, so

k
⋅
r
<
j

and

j
+
1
<
(
k
+
1
)
⋅
r

and

m
⋅
s
<
j

and

j
+
1
<
(
m
+
1
)
⋅
s
.

{\displaystyle k\cdot r

Then we get

k
<

j
r

and

j
+
1

r

<
k
+
1

and

m
<

j
s

and

j
+
1

s

<
m
+
1

{\displaystyle k<{j \over r}{\text{ and }}{j+1 \over r}

Adding corresponding inequalities, we get

k
+
m
<
j

and

j
+
1
<
k
+
m
+
2

{\displaystyle k+m

k
+
m
<
j
<
k
+
m
+
1

{\displaystyle k+m

which is also impossible. Thus the supposition is false.

Properties

A number

m

{\displaystyle m}

belongs to the Beatty sequence

B

r

{\displaystyle {\mathcal {B}}_{r}}

if and only if

1
−

1
r

<

[

m
r

]

1

{\displaystyle 1-{\frac {1}{r}}<\left[{\frac {m}{r}}\right]_{1}}

where

[
x

]

1

{\displaystyle [x]_{1}}

denotes the fractional part of

x

{\displaystyle x}

i.e.,

[
x

]

1

=
x
−
⌊
x
⌋

{\displaystyle [x]_{1}=x-\lfloor x\rfloor }

.
Proof:

m
∈

B

r

{\displaystyle m\in B_{r}}

⇔
∃
n
,
m
=
⌊
n
r
⌋

{\displaystyle \Leftrightarrow \exists n,m=\lfloor nr\rfloor }

⇔
m
<
n
r
<
m
+
1

{\displaystyle \Leftrightarrow m

⇔

m
r

<
n
<

m
r

+

1
r

{\displaystyle \Leftrightarrow {\frac {m}{r}}

⇔
n
−

1
r

<

m
r

<
n

{\displaystyle \Leftrightarrow n-{\frac {1}{r}}<{\frac {m}{r}}

⇔
1
−

1
r

<

[

m
r

]

1

{\displaystyle \Leftrightarrow 1-{\frac {1}{r}}<\left[{\frac {m}{r}}\right]_{1}}

Furthermore,

m
=

⌊

(

⌊

m
r

⌋

+
1

)

r

⌋

{\displaystyle m=\left\lfloor \left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r\right\rfloor }

.
Proof:

m
=

⌊

(

⌊

m
r

⌋

+
1

)

r

⌋

{\displaystyle m=\left\lfloor \left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r\right\rfloor }

⇔
m
<

(

⌊

m
r

⌋

+
1

)

r
<
m
+
1

{\displaystyle \Leftrightarrow m<\left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r

⇔

m
r

<

⌊

m
r

⌋

+
1
<

m
+
1

r

{\displaystyle \Leftrightarrow {\frac {m}{r}}<\left\lfloor {\frac {m}{r}}\right\rfloor +1<{\frac {m+1}{r}}}

⇔

⌊

m
r

⌋

+
1
−

1
r

<

m
r

<

⌊

m
r

⌋

+
1

{\displaystyle \Leftrightarrow \left\lfloor {\frac {m}{r}}\right\rfloor +1-{\frac {1}{r}}<{\frac {m}{r}}<\left\lfloor {\frac {m}{r}}\right\rfloor +1}

⇔
1
−

1
r

<

m
r

−

⌊

m
r

⌋

=

[

m
r

]

1

{\displaystyle \Leftrightarrow 1-{\frac {1}{r}}<{\frac {m}{r}}-\left\lfloor {\frac {m}{r}}\right\rfloor =\left[{\frac {m}{r}}\right]_{1}}

= Relation with Sturmian sequences

=
The first difference

⌊
(
n
+
1
)
r
⌋
−
⌊
n
r
⌋

{\displaystyle \lfloor (n+1)r\rfloor -\lfloor nr\rfloor }

of the Beatty sequence associated with the irrational number

r

{\displaystyle r}

is a characteristic Sturmian word over the alphabet

{
⌊
r
⌋
,
⌊
r
⌋
+
1
}

{\displaystyle \{\lfloor r\rfloor ,\lfloor r\rfloor +1\}}

.

Generalizations

If slightly modified, the Rayleigh's theorem can be generalized to positive real numbers (not necessarily irrational) and negative integers as well: if positive real numbers

r

{\displaystyle r}

and

s

{\displaystyle s}

satisfy

1

/

r
+
1

/

s
=
1

{\displaystyle 1/r+1/s=1}

, the sequences

(
⌊
m
r
⌋

)

m
∈

Z

{\displaystyle (\lfloor mr\rfloor )_{m\in \mathbb {Z} }}

and

(
⌈
n
s
⌉
−
1

)

n
∈

Z

{\displaystyle (\lceil ns\rceil -1)_{n\in \mathbb {Z} }}

form a partition of integers. For example, the white and black keys of a piano keyboard are distributed as such sequences for

r
=
12

/

7

{\displaystyle r=12/7}

and

s
=
12

/

5

{\displaystyle s=12/5}

.
The Lambek–Moser theorem generalizes the Rayleigh theorem and shows that more general pairs of sequences defined from an integer function and its inverse have the same property of partitioning the integers.
Uspensky's theorem states that, if

α

1

,
…
,

α

n

{\displaystyle \alpha _{1},\ldots ,\alpha _{n}}

are positive real numbers such that

(
⌊
k

α

i

⌋

)

k
,
i
≥
1

{\displaystyle (\lfloor k\alpha _{i}\rfloor )_{k,i\geq 1}}

contains all positive integers exactly once, then

n
≤
2.

{\displaystyle n\leq 2.}

That is, there is no equivalent of Rayleigh's theorem for three or more Beatty sequences.