9

Given the sequence $a_1 = 0$ and $a_{n+1} = \dfrac{1}{2 \cdot\lfloor{a_n}\rfloor-a_n+1}$ and $p,q\in \mathbb N$ and coprime find $x$ so that $a_x = \dfrac{p}{q}$. I do not even know where would you start with a problem like this.

Jaideep Khare
  • 19,293
chx
  • 1,807
  • I would start by computing at least a few dozen terms in a spreadsheet and see if that brought any enlightenment. – Ross Millikan Mar 24 '17 at 03:08
  • Also, write $a_n = u_n/v_n$ and see what the us and vs do. – marty cohen Mar 24 '17 at 03:12
  • 1
    Some observations, which I have not proven. For $n$ even, $a_n \gt 1$. For $n$ odd, $a_n \le 1$. $a_{2n}=a_n+1$. If $n=2^k, a_n=k$, which is a consequence of the last. If $n=2^k+1, a_n=\frac 1k$. If $n=3 \cdot 2^k, a_n=k+\frac 12$ – Ross Millikan Mar 24 '17 at 03:47
  • @martycohen It appears $u_{n+1} = 2v_n$ so all that needs to be found is the nature/formula of $v_n$ – Jacob Mar 24 '17 at 03:51
  • 2
    @Jacob: I think that should be $u_{n+1}=v_n$. The $v_n$ start off $(1,2)(1,3,2,3)(1,4,3,5,2,5,3,4)(1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5)$ where each set of parentheses has twice as many entries as the previous. To make the next group, take the current group and insert the sum of each neighboring pair of terms, then append the last term plus $1$. This is very reminiscent of the Farey sequence. – Ross Millikan Mar 24 '17 at 03:56
  • @rossMillikan Ahh, my mistake, I accidentally put $2$ in the numerator the recursive formula for $a_n$ instead of $1$, when I was copying it down. – Jacob Mar 24 '17 at 04:01
  • Yes, I can easily see that for $u_n < v_n$ the next one is going to be $v_n/(v_n-u_n)$ so $u_{n+1}=v_{n}$ in that case but I have more trouble when $u_n > v_n$. – chx Mar 24 '17 at 04:29

1 Answers1

3

Observation: $a_k<1$ iff $k$ is odd.

Lemma: If $a_{2n}$ = $a_n$+1.

Proof: By induction. $a_2 = 1 = 1+a_1$. Further suppose $a_{2(n-1)}=a_{n-1}+1$. Denote $x=2\lfloor a_{n-1}\rfloor-a_{n-1}+1$. Then $$a_n=\frac 1x,$$ $$a_{2n-1} = \frac 1{x+1},$$ $$a_{2n} = \frac 1{2\cdot0-\frac1{x+1}+1} = \frac1{\frac{x}{x+1}}=\frac{x+1}{x}=1+\frac 1x = a_n+1.$$

Lemma proved.

Now consider a rational number and the following process with it. While it is greater than or equal to one, subtract one from the number. Otherwise apply the recurrent formula $x\to\frac1{1-x}$. In every application of the formula, the denominator decreases, so we will get eventually to the number 0.

We can follow the process backwards and assign elements $a_k$ to it. We start with $0=a_1$. When we add one to the value, we just jump from $a_k$ to $a_{2k}$. In the other case (after application of $\frac1{1-x}$), we are on an even index $a_k$. So $a_{k-1}$ is odd, so $a_k = \frac1{1-a_{k-1}}$. Since the function $\frac1{1-x}$ is injective, $a_{k-1}$ is the next value in the reverted sequence.

At the end, we reach the original rational number together with its position in the sequence.

Mirek Olšák
  • 1,304
  • $a_{2n-2}=1+a_{n-1}$, so $2\lfloor a_{2n-2}\rfloor - a_{2n-2}+1 = 2+2\lfloor a_{n-1}\rfloor - 1-a_{n-1}+1 = 2\lfloor a_{n-1}\rfloor-a_{n-1}+1+1 = x+1$ – Mirek Olšák Apr 13 '17 at 13:04