A curious sequence of rationals: finite or infinite?

Question

Consider the following function repeatedly applied to a rational $r = a/b$ in lowest terms: $f(a/b) = (a b) / (a + b - 1)$. So, $f(2/3) = 6/4 = 3/2$. $f(3/2) = 6/4 = 3/2$.

I am wondering if it is possible to predict when the sequence is finite, and when infinite. For example, $f(k/11)$ seems infinite for $k=2,\ldots,10$, but, e.g., $f(4/13)=f(13/4)$ is finite. Several more examples are shown below.

---

$$ \frac{1}{k} \to \frac{k}{k} {=} 1 $$

$$ \frac{3}{7} \to \frac{21}{9} {=} \frac{7}{3} \to \frac{21}{9} {=} \frac{7}{3} $$

$$ \frac{5}{12} \to \frac{60}{16} {=} \frac{15}{4} \to \frac{60}{18} {=} \frac{10}{3} \to \frac{30}{12} {=} \frac{5}{2} \to \frac{10}{6} {=} \frac{5}{3} \to \frac{15}{7} \to \frac{105}{21} {=} \frac{5}{1} \to \frac{5}{5} = 1 $$

$$ \frac{5}{23} \to \frac{115}{27} \to \frac{3105}{141} {=} \frac{1035}{47} \to \frac{48645}{1081} = \frac{45}{1} \to 1 $$

$$ \frac{4}{11} \to \frac{44}{14} {=} \frac{22}{7} \to \frac{154}{28} {=} \frac{11}{2} \to \frac{22}{12} {=} \frac{11}{6} \to \frac{66}{16} {=} \frac{33}{8} \to \frac{264}{40} {=} \frac{33}{5} \to \frac{165}{37} \to \cdots \to \infty ?$$

---

I am hoping this does not run into Collatz-like difficulties, but it does seem straightforward to analyze... If anyone recognizes it, or sees a way to tame it even partially, I would be interested to learn. Thanks!

Answer 1

Note: I've appended some additional material that extends the analysis of, in effect, the pre-images of the pre-images of the fixed point $n/m=1$ of the function $f$, to look at general pre-images and pre-images of other fixed points (i.e., $n/m = (m^2-m+1)/m$ for $m>1$. The new stuff follows a boldface "Added later." End of note

The families Karl Fabian found can be subsumed under a single rule:

$f^{(2)}(a/b)=1$ if and only if $${a\over b}={n+d\over n+d'}$$ where $n>0$, $dd'=n(n-1)$, and $(n+d,n+d')=1$.

It's not hard to show that if $a/b$ has the given form, then $f(a/b)=n$, and it's easy to show that $f(n)=f(n/1)=1$. (The assumption that $n+d$ and $n+d'$ are relatively prime is crucial.) The tricky part is showing that nothing else gets to $1$ in two steps.

It's clear that $f(a/b)=1$ if and only if $a+b-1=ab$, which can be rewritten as $(a-1)(b-1)=0$, so the only numbers that get to $1$ in one step are integers $n$ and their reciprocals $1/n$. It's also clear that $f(a/b)\ge1$ for all $a/b$. Therefore, the numbers that get to $1$ in two steps are those that get to some integer $n$ in one step. Let's see how that can happen.

If $ab/(a+b-1)=n$, then we must have $ab=nk$ and $a+b-1=k$ for some integer $k$. Writing $b=nk/a$, we wind up with $a^2-(k+1)a+nk=0$, so

$$a={k+1\pm\sqrt{(k+1)^2-4nk}\over2}.$$

For $a$ to be an integer, we must have a square inside the square root:

$$(k+1)^2-4nk = m^2,$$

which can be rewritten as

$$(k+1-2n)^2-m^2 = 4n(n-1),$$

or

$$(k+1-2n+m)(k+1-2n-m)=4n(n-1).$$

The two terms on the left hand side have the same parity (they differ by $2m$), hence they must both be even, i.e., $k+1-2n+m=2d$ and $k+1-2n-m=2d'$ where $dd'=n(n-1)$. From this we get $k+1-2n=d+d'$ and $m=d-d'$, so

$$a={2c+d+d'\pm(d-d')\over2}.$$

Choosing the positive sign gives $a=n+d$. (Choosing the negative sign gives $b=n+d'$. If you like, you can assume $a\ge b$ and $d\ge d'$.)

To do just one example, let $n=16$. The choices for $dd'$ are $240\cdot1$, $80\cdot3$, $48\cdot5$, and $16\cdot15$, leading to the four possibilites for $a/b$ (with $a>b$) for which $f(a/b)=16$:

$${a\over b} = {256\over 17}, {96\over19}, {64\over21}, {32\over31}.$$

Note how a factorization like $dd'=6\cdot40$ fails:

$$f((16+6)/(16+40)) = f(22/56)=f(11/28)= {11\cdot28\over38}={154\over19}.$$

Added later: If I've done everything correctly, a similar analysis gives the following nice result about pre-images:

Let $n/m$ be a fraction with $n\ge m$ and $(n,m)=1$. Then $f(a/b)=n/m$ if and only if

$${a\over b} = {n+d\over n+d'}$$

where $dd'=n(n-m)$ and $(n+d,n+d')=m$.

Let's see how this applies to the other fixed points for $f$, namely when $n=m^2-m+1$, for the first few values of $m$.

Skipping the case $m=1$ (which you can check gives the result noted earlier), let $n/m = 3/2$, so that we need $dd'=3$ and $(3+d,3+d')=2$. The only factors are $3$ and $1$, which indeed satisfy $(6,4)=2$, but this only gives $a/b = 6/4=3/2$. In other words, the fixed point $3/2$ has no pre-image other than itself.

For $n/m=7/3$, we have $n(n-m)=28$, for which the possible factorizations are $28\cdot1$, $14\cdot2$, and $7\cdot4$. But the only one of these for which $(7+d,7+d')=3$ is $14\cdot2$, which gives $a/b = 21/9 = 7/3$, so $7/3$ also has no pre-image other than itself.

You can check that the same thing happens for $n/m = 13/4$: The only factorization $dd'$ of $13(13-4)$ for which $(13+d,13+d')=4$ is $39\cdot3$, giving $a/b=52/16 = 13/4$.

But $n/m = 21/5$, finally, is interesting: There are two factorizations that work, namely $84\cdot4$ and $24\cdot14$. The first, as before, gives the fixed point again, $$a/b = (21+84)/(21+4) = 105/25 = 21/5.$$ But the other one gives $$a/b = (21+24)/(21+14) = 45/35 = 9/7.$$ Note, however, that $9/7$ has no pre-image: The factorizations of $9(9-7)=18$ are $18\cdot1$, $9\cdot2$, and $6\cdot3$, none of which produce anything divisible by $7$, much less a pair $(9+d,9+d')$ with $7$ as a common divisor.

In summary (for now), the only fraction with infinitely many pre-images is $n/m=1$ (since $n(n-m)=0$ has infinitely many divisor pairs!); the size of the pre-image set for all other fractions is bounded by the number of divisor pairs of $n(n-m)$. For some of the fixed points of $f$, the pre-image set is just the fixed point itself, while for others (e.g. $n/m = 21/5$), the pre-image set contains additional points. There may be some simple criterion that identifies the fixed points that have no additional pre-images, but I don't offhand see one, possibly because I haven't thought hard enough about it (but maybe because I'm just blind to the obvious).

Answer 2

All fractions $a/b$ with $ a = b(b-1)+1 $ are fixed points because then $(a,b)=1$. Moreover, all solutions to $f^{(2)}(r)=1$ I found so far come from one of these families: $$f\left(f\left(\frac{1}{n}\right)\right)=f\left(1\right)=1$$

$$f\left(f\left(\frac{(n-1)^2}{n^2}\right)\right)=f\left(\frac{n(n-1)}{2}\right)=1$$

$$f\left(f\left(\frac{2n-1}{2n}\right)\right)=f\left(n\right)=1$$

$$f\left(f\left(\frac{n+1}{n^2}\right)\right)=f\left(n\right)=1$$

$$f\left(f\left(\frac{3(2n+1)}{4(3n+1)}\right)\right)=f\left(4n+2\right)=1$$

If initially not much cancellation happens during the iteration and $a\approx b$, then$f^{(n)}(a/b)$ grows superexponential, probably close to $a^{\phi^{n-1}}$ which makes substantial cancellation more and more unlikely, especially that the numerator eventually hits by chance a perfect multiple of the denominator.

Answer 3

[update] Upps, after posting this I see, that Barry has done the similar thing with the term "preimage". I think, the list/tree below is it worth anyway... [endupdate]

I approached the problem from the side of inversion of the given map; beginning at $1/1$ should then occur an infinite tree. The required degree of freedom is taken by the cancelling of common factors in numerator and denominator, which means the choice (though somehow restricted) of a common factor $g$ in the inverted map. It is not easy to optimize the procedure; first one has to find a minimum factor $g$ which allows at all to compute one valid step for the inverse (by construction of a solvable minimal integer squareroot), and then to find subsequent solutions. I used so far brute force for the first couple of tries.
For the description I resolved the rational fraction into a 2-component vector, instead of $ \frac ab$ I use $[a,b]$ as parameter and as result.

Here is a short handplanted tree, beginning at $[1,1]$. From $[1,1]$ we can arrive at any$[k,1]$ by some common factor $g$ this is indicated by $[k,1]$ in the tree below.

Then beginning at $[2,1]$ there is a further subtree, where the siblings of the same level are always on the same column. For instance, $[2,1]$ has only one child $[4,3]$, this has one child $[2,2]$ and this has then an infinite number of childs $[2k,1]$.

After that I began with $[3,1]$, and so on, with the obvious scheme.

We find some "common nodes", for instance $[4,3]$, which occur in different generations of childs, and also "immediate cycles" for instance $[3,2]$

Surprisingly there are a lot of dead ends, $[6,5]$,$[8,7]$ and so on.
If you like to play with it, a crude sample code for Pari/GP is at the end.

 [1,1] 
    --> [k,1]

 [2,1]
   [4,3]
     [2,2]
        --> [2k,1]

 [3,1]
   [6,5]
   [9,4]
     [6,3]
       [4,3]  (... common node)


 [4,1]
   [8,7]
   [10,6]
     [5,2]
       [5,4]
       [10,3]
         [8,5]
           [4,2]
             [4,3]   (... common node)
         [15,4]
           [12,5]
              [8,3]
                [6,4]
                  [3,2]  (!!cycle)
                [16,3]
                  [14,8]
                     [7,2]
                       (???)
                  [40,6]
           [45,4]
   [16,5]

---

\\ The original map
T(v,h=1)=local(a,b);for(k=1,h,a=v[1]*v[2];b=v[1]+v[2]-1;v=[a,b]/gcd(a,b));v

\\The inverse map
{TI(v,maxg=2000,maxj=20)=local(a,b,j=0,x,y);
 list=vectorv(maxj);    \\ list to establish the branch of siblings
 for(g=1,maxg,          \\ test all successive assumed common factors g up to maxg
   a = v[1]*g;b=v[2]*g;
   t1 =  (b+1)^2 - 4*a;
   if(t1<0,next());
   t1=sqrt(t1);
   if(t1<>floor(t1),next());   \\ t1 must be an integer squareroot
   x = bestappr(((b+1)+ t1)/2,1e12) ;
   y = bestappr(((b+1)- t1)/2,1e12) ;
   j++; if(j>maxj,break());   \\ length of sibling-list at most 20
   list[j]=[x,y,g];
  );
  if(j==0,return(Mat([0,0,0])));   \\ we have a dead-end in our argument v
  list=VE(list,j);    \\ shorten the list to the length of actually found siblings
 return(Mat(list))   }


{TIrek(v,level=0)=local(tmp);
 tmp = TI(v); 
 for(r=1,rows(tmp),
    print(level,"   ", tmp[r,]);
     if(level<5 & tmp[r,1]<>0, TIrek([tmp[r,1],tmp[r,2]],level+1));
    );
 return(0);}