# Variation of a Beatty Sequence

I've been studying Beatty sequences lately, and, having read and understood a proof of Raleigh's theorem, I know that if $\lfloor \alpha x\rfloor$ is a Beatty sequence with $\alpha\gt 1$, then its complementary Beatty sequence is $\lfloor \beta x\rfloor$, where $$\frac{1}{\alpha}+\frac{1}{\beta}=1$$ However, I'm having a little bit of trouble with the following: as a generalization of the Beatty sequence $\lfloor \phi n\rfloor$, I am considering the similar sequence $\lfloor \phi n-1/3\rfloor$ and trying to find its complement in the natural numbers. I believe that its complement is $\lfloor (\phi+1)n+2/3\rfloor$, but the method of proof used for Beatty's theorem doesn't work in this case. I used the second proof provided here.

EDIT: My conjecture is false (see comments), but I would still like to find the complement of the originally mentioned sequence.

Does anyone know how to find the complement of the following sequence? $$\{\lfloor \phi n-1/3\rfloor\}_{n=1}^\infty$$

• How far did you check it? Commented Jun 24, 2018 at 16:04
• I'm wondering if I'm missing something. Is $\phi$ meant to represent the golden ratio? If so, I find that the 20th term of the $A$ sequence is 32, and the 12th term of the $B$ sequence is also 32. I find many other common terms as well. Commented Jun 27, 2018 at 15:07
• @JohnBarber Gah, you're right. My code was buggy. :( Commented Jun 27, 2018 at 15:11
• The floor function presents a disappointing insolvability of a system of equations it occurs, I am stuck with a very similar predicament to this at the moment Commented Jun 25, 2020 at 15:14

draw a line $y = kx + r$ for $r \in (0;1)$ and $k > 0$ that doesn't go through any point with integer coordinates.

Starting from $(0,r)$, that line will intersect the horizontal lines $x=n$ and vertical lines $y=n$ one at a time (it can never cross two at once since I explicitly said so)

By giving a number to each crossing starting with $0$ for the vertical line $x=0$, you can define two functions $h(n)$ and $v(n)$ such that $h(n)$ is the number of the crossing that crosses the line $y=n$ and similarly for $h(n)$ and horizontal lines.

Now, what is $v(n)$ ? It is $n$ plus the number of horizontal lines that were crossed while reaching the vertical line $x=n$. Putting $x=n$ and solving for $y$ you get that the line $x=n$ is crossed at $(x = n, y=kn+r)$. Hence, $v(n) = n + \lfloor kn + r \rfloor = \lfloor (k+1)n+r \rfloor$

Similarly for $h(n)$, putting $y=n$ and solving for $x$ you get the point $(x = \frac{n-r}k, y=n)$, and so $h(n) = n + \lfloor\frac {n-r}k \rfloor= \lfloor \frac {(k+1)n-r}k \rfloor$

Now by construction the sequences $(h(n))_{n \ge 1}$ and $(v(n))_{n \ge 1}$ are a partition of $\{1;2;3;\cdots\}$

For your problem you would like to have $(k+1)/k = \phi$ and $r/k = 1/3$, so $k = \phi$ and $r = \phi/3$.

The line is $y = \phi x + (\phi/3)$, or $y/\phi = x + 1/3$, and it can't go through any integer point (or else $\phi$ would be rational) so the preceding section applies :

$h(n) = \lfloor \phi n - \frac 13 \rfloor$ and $v(n) = \lfloor (\phi+1)n + \phi/3 \rfloor$ give a partition of $\Bbb N$.

So your answer is $\lfloor (\phi+1)n + \phi/3 \rfloor$ instead of $\lfloor (\phi+1)n + 2/3 \rfloor$

• For whatever it's worth, and because I like numerical verification, I find that the first 1,000,000 or so terms of the actual complement sequence match the answer given above. Commented Jun 27, 2018 at 15:42
• a nicer phrasing would be that the complement of $\lfloor \alpha n + r \rfloor$ is almost always $\lfloor \beta n + s \rfloor$ with $\alpha^{-1} + \beta^{-1} = 1$ and $\alpha s + \beta r = 0$ Commented Jun 27, 2018 at 15:45
• Typos :Your first sentence should say "and $k>0$", second sentence should say "vertical lines $x=n$ and horizontal lines $y=n$", third sentence should say "similarly for $v(n)$ and vertical lines." Commented Jun 27, 2018 at 16:25

To make the Wikipedia proof work, the shifts have to cancel. If we denote your shift of $\frac13$ by $\delta$ and the unknown shift for the complementary sequence by $\epsilon$, the inequalities in the proof become

$$j < k \cdot r - \delta < j + 1 \text{ and } j < m \cdot s + \epsilon < j + 1\;,$$

and then dividing through by $r$ and $s$, respectively, and adding as in the ordinary proof yields

$$j < k -\frac\delta r + m +\frac\epsilon s< j + 1\;.$$

Thus for the proof to go through, you need $\frac\epsilon s-\frac\delta r\in\mathbb Z$. Thus, given $\delta$, you need to choose

$$\epsilon=ks+\delta\cdot\frac sr\;\text{ with }\;k\in\mathbb Z\;.$$

In your case, with $\delta\cdot\frac sr=\frac\phi3$, the simplest choice is $\epsilon=\frac\phi3$ to get the complementary sequence $\lfloor (\phi+1)n+\phi/3\rfloor$.

• Except that's not the complementary sequence. The actual complementary sequence starts out 3, 5, 8, 11..., whereas your sequence starts out 2, 5, 8, 10... Commented Jun 27, 2018 at 15:36
• @JohnBarber: Hmm, I guess you're right; thanks! Commented Jun 27, 2018 at 15:39
• @JohnBarber: Thanks again. I fixed the error and now arrived at the same result as mercio. Commented Jun 27, 2018 at 15:51
• @joriki Gosh, I can't believe I was unable to figure that out. Thank you so much for an answer that uses the same method as the proof I provided. I will award the bounty to you as soon as I can. Commented Jun 27, 2018 at 16:14