# Algorithms

## Summation of a Partial Beatty Sequence

 \sum_{i=1}^{n}\mathcal{B}_{r\in\mathbb{Z}}^i = \sum_{i=1}^{n}\lfloor ir \rfloor

A partial Beatty sequence is the sum of all the Integer portions of positive multiples between 1 and n of an Irrational number. Calling it a partial sequence denotes that there is an upper limit, as opposed to an infinite sequence.

As an example, we will use r=\sqrt{2}, n=5.

The square root of 2 is 1.414214. Multiply this by 2 and get 2.8288427, and so forth up to 5. Summing up the integer portions we get the value 19.

### Raleigh-Beatty Theorem

Rayleigh’s theorem, states that a sequence, consisting of all the positive integers that are not in the sequence, is itself a Beatty sequence generated by a different irrational number.

For any Beatty \mathcal{B}_r^n sequence where r > 1 there exists a complementary sequence \mathcal{B}_s^n where s>1 is defined as \frac{1}{r}+\frac{1}{s}=1. The union of both sequences is the set of all Integers from 1 to n.

We can find an equation for s in terms of r.

\begin{align}
\begin{gather*}
\frac{1}{s} + \frac{1}{r} = 1 \\ \downarrow \\
\frac{1}{s} = 1 - \frac{1}{r} \\ \downarrow \\
\frac{1}{s} = \frac{r}{r} - \frac{1}{r} \\ \downarrow \\
\frac{1}{s} = \frac{r-1}{r} \\ \downarrow \\
s = \frac{r}{r-1}
\end{gather*}
\end{align}

The complement consists of all integers less than ‘n’ not in the sequence. Where the Beatty sequence for r=\sqrt{2}, n=5 is \{1, 2, 4, 5, 7\}. The complimentary Beatty sequence is \{3, 6\}.

For any sequence dividing the value by the equation will give you the index of the value that is less than N = \mathcal{B}_r^n. This allows us to find the last index of the complement because the last value of the complement is lower than that of the sequence. \lfloor \frac{\mathcal{B}_r^i}{s} \rfloor.

\lfloor ir \rfloor = \mathcal{B}_r^i \rightarrow \lfloor \frac{\mathcal{B}_r^i}{r} \rfloor = i-1


\mathcal{B}_r^n is the largest term in the sequence, dividing that by ‘r’ would give you the index of the sequence .

For clarity we will express the largest value of the sequence as N = \mathcal{B}_r^n , and the upper index of the complement as m = \lfloor N/s \rfloor.

\begin{align}
\begin{gather*}
N = \mathcal{B}_r^n\\ \\
m = \lfloor N/s \rfloor\\ \\
\sum_{i=1}^{n}\lfloor ir \rfloor +
\sum_{j=1}^m
\lfloor js \rfloor =
\frac{N^2 + N}{2}
\end{gather*}
\end{align}

### Building up to the Solution

Since the union of any Beatty sequence and its complement will cover all the positive integers. This leads to the realization that any Integer can be expressed at either \lfloor ir \rfloor or \lfloor js\rfloor.

The sum of the sequence in question:

\begin{align}
S(n, r) = \sum_{i=1}^{n}\mathcal{B}_r^i
\end{align}

The sum of the complementary sequence:

\begin{align}
S(m, s) = \sum_{j=1}^{m}\mathcal{B}_s^j | s = \frac{r}{r-1}
\end{align}

By way of the Raleigh-Beatty Theorem, the two sums are equivalent to the sum of the Integers from 1 to the highest Beatty sequence value (\mathcal{B}_r^n). This can be rearranged to say; the sum of a Beatty sequence is the difference in the sum of all encompassed Integers and the sequence’s complement.

\begin{align}
\begin{gather*}
S(n,r) + S(m,s) =
\sum_{i=1}^Ni \\
\downarrow \\
S(n,r) =
\sum_{i=1}^Ni -
S(m,s)

\end{gather*}
\end{align}

At this point we want to express the sum of the complement in terms of sum the original sequence. We will do this by extracting \mathcal{B}_r^i from \mathcal{B}_s^i. To do so we will need to define a value for s, we will use \sqrt{2}.

### Expressing the Complement in Terms of the Original

Starting with r and s (1), we assign a value to r.

\begin{align}
r = \sqrt{2}, s= \frac{r}{r-1}
\end{align}

Substitute r for \sqrt{2}

\begin{align}
s= \frac{\sqrt{2}}{\sqrt{2}-1}
\end{align}

Simplify

\begin{align}
\begin{gather*}
s= 1-\frac{\sqrt{2}(\sqrt{2}+1)}{(\sqrt{2}-1)(\sqrt{2}+1)} \\
\downarrow\\
s= \frac{2+\sqrt{2}}{1} \\
\downarrow\\
s=2+\sqrt{2}
\end{gather*}
\end{align}

Whole integers can be brought out of the floor function.

\begin{align}
\begin{gather*}
\mathcal{B}_s^i = \lfloor is\rfloor=\lfloor i(2+\sqrt{2})\rfloor \\
\downarrow \\
\lfloor 2i+i\sqrt{2}\rfloor \\
\downarrow \\
2i+\lfloor i\sqrt{2}\rfloor \\
\end{gather*}
\end{align}

Express \mathcal{B}_s^i in terms of \mathcal{B}_r^i.

\begin{align}
\begin{gather*}
\text{since } \mathcal{B}_r^i=\lfloor i\sqrt{2}\rfloor \\
\downarrow\\
\mathcal{B}_s^i = \mathcal{B}_r^i + 2i
\end{gather*}
\end{align}

### Recursive Function

Express the complement sum in terms of the original sum.

\begin{align}
\begin{gather*}
S(m,s)=
\sum_{i=1}^m \mathcal{B}_s^i\\
\downarrow\\
\sum_{i=1}^m(\mathcal{B}_r^i+2i) \\
\downarrow\\
\sum_{i=1}^m\mathcal{B}_r^i+\sum_{i=1}^m2i \\
\downarrow\\
\sum_{i=1}^m\mathcal{B}_r^i+2\sum_{i=1}^mi \\
\downarrow\\
S(m, r) + 2(\frac{m(m+1)}{2}) \\
\downarrow\\
S(m,s)=S(m, r) + m(m+1)

\end{gather*}
\end{align}

From (5) using (11)

\begin{align}
\begin{gather*}
S(n,r) =
\sum_{i=1}^Ni -
S(m,s) \\
\downarrow \\
S(n,r) =
\sum_{i=1}^Ni - [S(m,r) + m(m+1)]\\
\downarrow \\
S(n,r) =
\sum_{i=1}^Ni - S(m,r) - m(m+1)
\end{gather*}
\end{align}

Expressed as a recursive function.

\mathcal{S}(n, r)=
\begin{cases}
0 \leq n \leq 1 & n \\
n > 1 &
\sum_{i=1}^Ni - S(m,r) - m(m+1)
\end{cases}

### External References

https://en.wikipedia.org/wiki/Beatty_sequence