Consider the following sequence: let a0>0 be rational. Define an+1=an1−{an}, where {an} is the fractional part of an (i.e. {an}=an−⌊an⌋). Show that an converges, and find its limit.

We can show it converges as follows: suppose an=pn/qn=kn+rn/qn, where pn=knqn+rn, 0≤rn<qn. Then an+1=pn/qn1−rn/qn=pnqn−rn,so the denominator will keep decreasing until it is a divisor of p0 (maybe 1). Also, note we may take pn=p0 for all n.

Further, the limit will be ≤p0gcf(p0,q0), because if f∣p0 and f∣qn, then f∣(p0−knqn)=rn, so f∣qn−rn=qn+1. But the limit may be strictly smaller; for instance, a0=30/7 converges right away to 6.

Can we say anything else about the limit of a sequence starting with a0? This was a problem on a qualifier, so I suspect there is more to the answer, but maybe not.

**Answer**

Wanted to record some observations here...

If we consider the sequence

- p=a1q+r1
- p=a2(q−r1)+r2
- p=a3(q−r1−r2)+r3
- etc.

and try to solve for the remainders in the form ri=cip−diq, there is a nice recursive relation:

First, c1=1 and d1=a1, and in general,

cj=1+aj(c1+…+cj−1) and

dj=(1+a1)(1+a2)⋯(1+aj−1)aj

We can also write cj(1+aj)=c1+…+cj so that

cj=1+ajaj−1(cj−1(1+aj−1)−1). This can be expanded further to obtain the form

cj=1+aj[1+(1+aj−1)[1+(1+aj−2)[1+…[1+(1+a2)]]…], or even

cj=1+aj+aj(1+aj−1)+aj(1+aj−1)(1+aj−2)+…+aj(1+aj−1)(1+aj−2)⋯(1+a2)

Note that the ai are strictly increasing in the sequence. Suppose the procedure terminates at the n-th step (when rn=0). The limit is then p/an, and 0=rn=cn(p/q)−dn or that p/q=dn/cn.

I still don't have a closed form expression, but for instance:

For rationals p/q for which the sequence terminates in the first step, 0=r1=c1(p/q)−d1=p/q−a1, so that q is a divisor of p, and the limit is p/q.

For termination at the second step, 0=r2=c2(p/q)−d2=(1+a2)(p/q)−(1+a1)a2, or that pq=(1+a1)a21+a2. If there exists a1<a2 satisfying this equality, then the sequence terminates in the second step. One such criteria is if d is a divisor of p, q=d+1 and p/d−1<d, then the sequence terminates in the second step to p/d=(1+a1).

For examples: 30/7=(1+4)6/(1+6). Also, 30/4=120/16=(1+7)15/(1+15).

Third step termination: pq=(1+a1)(1+a2)a31+a3(1+(1+a2)), limit is (1+a1)(1+a2), and etc.

Also, it appears that if you plug in an=d in any formula, you can generate for which p the process converges to d by substituting any a1<a2<…<an−1<d. Maybe there's more special structure...

**Attribution***Source : Link , Question Author : Eric Auld , Answer Author : Evan*