6
$\begingroup$

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$$

$\endgroup$
4
  • $\begingroup$ How far did you check it? $\endgroup$
    – Phira
    Commented Jun 24, 2018 at 16:04
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 27, 2018 at 15:07
  • $\begingroup$ @JohnBarber Gah, you're right. My code was buggy. :( $\endgroup$ Commented Jun 27, 2018 at 15:11
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Jun 25, 2020 at 15:14

2 Answers 2

5
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Jun 27, 2018 at 15:42
  • 1
    $\begingroup$ 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$ $\endgroup$
    – mercio
    Commented Jun 27, 2018 at 15:45
  • $\begingroup$ 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." $\endgroup$
    – r.e.s.
    Commented Jun 27, 2018 at 16:25
4
+100
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$ Commented Jun 27, 2018 at 15:36
  • $\begingroup$ @JohnBarber: Hmm, I guess you're right; thanks! $\endgroup$
    – joriki
    Commented Jun 27, 2018 at 15:39
  • $\begingroup$ @JohnBarber: Thanks again. I fixed the error and now arrived at the same result as mercio. $\endgroup$
    – joriki
    Commented Jun 27, 2018 at 15:51
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jun 27, 2018 at 16:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .