Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Euclidean algorithm shows how all coprime pairs of positive integers can be uniquely obtained from the pair $(1,1)$ by applying the two operations $(a,b) \to (a+b,b)$ and $(a,b) \to (a,a+b)$.

(or speaking with rationals, all the positive rationals $x=b/a$ can be obtained from $1$ by applying the two operations $x \to x/(x+1)$ and $x \to x+1$).

Furthermore, we know that the natural density of coprime pairs among the pairs of positive integers is $6/\pi^2$.
This brings the question : do the set of all childrens of some pair $(a,b)$ have a natural density $d(a,b)$, and if so, what is it ?

Allowing to start from any pair of positive reals, we have that $d(ka,kb) = d(a,b)/k$ if those exist, which suggests that we can simply look for a function $d(1,b/a) = f(b/a)$.
We have, for symmetry reasons, $f(x) = f(1/x)/x$. We also have from the tree construction, the functional equation $f(x) = f(x+1) + f(x/(x+1))/(x+1)$.

Using the symmetry equation, we can rewrite this to get the nicer functional equation : $f(x) + f(1/x) = f(1/(x+1)) + f(x/(x+1))$.

So, is there anything interesting we can say about these functional equations ? How many continuous (or even, differentiable) solutions does the system have ? Does the density we started with have a nice closed-form expression ?

share|cite|improve this question
A simplification: let $f(x) = g(x) / \sqrt{x}$. Then the first functional equation says $g(x) = g(1/x)$ and the second says $$ g(x) \sqrt{x+1} = g(x+1) \sqrt{x} + g((x+1)/x) $$ – Hurkyl Feb 25 '13 at 17:17
I might be wrong, but it seems to me that $d(ka,kb)=d(a,b)/k^2$. If this is the case, my gut feeling says that $d(a,b)=\frac{6}{ab\pi^2}$. Also, just like @Hurkyl suggested, instead of analysing $f(x)$, it might be easier to look at $g(x)=xf(x)$ for which we would get have $g(x)=g(1/x)$ and $(x+1)g(x)=xg(x+1)+g(x/(x+1))$ (and the solution I mentioned above corresponds to $g(x)$ being constant). – Peter Košinár Dec 2 '14 at 11:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.