Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.