By now, we've realized that all the obt. numbers have an expression as irreducible fraction that is $\frac n{2^k}$, with $n$ obviously $odd$ (except for the zero). They all belong to the interval $[0,1]$ and none belongs to $(0.5,0.75)$.
I've seen that is easy to enumerate all of them, starting by $0$ and $1$, then the only one with $k=1$, then those with $k=2$, and so.
And if $k$ is odd, then the last function applied has to be $g(x)$, and so the possible numerators when $k$ is odd are the same available for $k-1$.
Now, if $k$ is even, not only those same numerators available for $k-1$ are still possible (and will be there forever), but those that appear for having applied $f(x)$; these have to come from the obt. numbers with denominator $2^{k/2}$. These numerators will be $2^k-n^2$, where $n$ stands for every possible numerator of the obt. fractions with denominator $2^{k/2}$.
Assuming these two groups of numerators don't have a common element, we can say that the number of obt. fractions with a $2^k$ in the denominator (when expressed as irreducible), say $N_k$ is
$$N_{k-1} \quad \text{if $k$ is odd and $k>1$}$$
$$N_{k-1}+N_{k/2} \quad \text{if $k$ is even and $k>2$}.$$
I've typed all the obt. numbers until $k=10$:
$$0$$
$$\color{#C00}{1}$$
$$\frac12$$
$$\frac14 \quad\frac{\color{#C00}{3}}4$$
$$\frac18 \quad \frac38$$
$$\frac1{16}\quad \frac3{16}\quad \frac{\color{#C00}{7}}{16}\quad\frac{\color{#C00}{15}}{16}$$
$$\frac1{32}\quad\frac3{32}\quad\frac7{32}\quad\frac{15}{32}$$
$$\frac1{64}\quad\frac3{64}\quad\frac7{64}\quad\frac{15}{64}\quad\frac{\color{#C00}{55}}{64}\quad\frac{\color{#C00}{63}}{64}$$
$$\frac1{128}\quad\frac3{128}\quad\frac7{128}\quad\frac{15}{128}\quad\frac{55}{128}\quad\frac{63}{128}$$
$$\frac1{256}\quad\frac3{256}\quad\frac7{256}\quad\frac{15}{256}\quad\frac{\color{#C00}{31}}{256}\quad\frac{55}{256}\quad\frac{63}{256}\quad\frac{\color{#C00}{207}}{256}\quad\frac{\color{#C00}{247}}{256}\quad\frac{\color{#C00}{255}}{256}$$
$$\frac1{512}\quad\frac3{512}\quad\frac7{512}\quad\frac{15}{512}\quad\frac{31}{512}\quad\frac{55}{512}\quad\frac{63}{512}\quad\frac{207}{512}\quad\frac{247}{512}\quad\frac{255}{512}$$
$$\tfrac1{1024}\quad\tfrac3{1024}\quad\tfrac7{1024}\quad\tfrac{15}{1024}\quad\tfrac{31}{1024}\quad\tfrac{55}{1024}\quad\tfrac{63}{1024}\quad\tfrac{207}{1024}\quad\tfrac{247}{1024}\quad\tfrac{255}{1024}\quad\tfrac{\color{#C00}{799}}{1024}\quad\tfrac{\color{#C00}{975}}{1024}\quad\tfrac{\color{#C00}{1015}}{1024}\quad\tfrac{\color{#C00}{1023}}{1024}.$$
$$$$
It can be seen that the last even $k$ for which the numbers obtained from $k-1$ and $k/2$ mix up is for $k=8$ (but anyway, there are no coincidences). For $k=10$ both groups are far from each other. It's not hard to prove that 'overlapping' may only happen for $k$ a multiple of $4$. It is not clear if there are coincidences for larger $k$ (I tend to believe there aren't, but I'll have to use something else than my intuition).
I guess is all I have by now. Not a big deal, but it might help to understand the structure of the set. And it's also interesting to know that there is a simple (and recursive) procedure to check whether a number is obt. or not.
UPDATE
After having played quite a bit with this problem and given it some thought, I still can't prove but I'm quite convinced that the set $\mathcal O$ of 'obtainable' numbers through this procedure ought to be dense in $\mathbb Q \cap\left([0,0.5]\cup[0.75,1]\right)$. That is to say, dense in $[0,1]\setminus(0.5,0.75)$ (since $\mathbb Q$ is dense in $\mathbb R$).
I made a lot of plots of finite subsets of $\mathcal O$ through two procedures:
- The first one, was to enumerate all dyadic functions in $\mathcal O$ with denominator $2^k$ until a given $k$, trough a recurrence as explained before. This led to considerable gaps in the graph (besides the already known 'big gap' at $(0.5,0.75)$, unless $k$ was large (not much more than $200$ or $300$ maybe) and this happened at a point where standard floating point operations did not offer enough precision. This process also required a lot of processing power and time. Nevertheless, it allowed me to verify that as far as floating point precision permitted, there were no repetitions in generated elements of $\mathcal O$ at each step (that is, when $k$ was a multiple of $4$ —while there was overlap between the numerators that appeared as a consequence of applying $g$ to the series corresponding to $k-1$ and applying $f$ to the series corresponding to $k/2$— all the numbers that came up with that procedure were different in fact. Precision failed in fact at $k=60$, where two apparently equal numerators appeared ($n\approx 2.88\times 10^{17}$). A deeper inspection showed that those two numerators were carried from the case $k=59$ and from $k=58$ before. But they weren't numerators for $k=57$, so they had to come from $k=58/2=29$. They did, indeed: they corresponded to numerators $n=1$ and $n=3$; but for double precision it turned out that the corresponding numerators for $k=58$, namely $2^{58}-1$ and $2^{58}-3$, where not distinguishable anymore (but these are different numbers of course). So a plain logic check between double type objects won't work for $k\ge58$.
- The other procedure was a random one, in analogy to what @david-g-stork did. First a natural number $n$ was generated, chosen randomly (this was different from david-g's choice, who took a fixed $n$) from a discrete uniform distribution in the set $\{1,2,\ldots,K\}$, and then $f$ or $g$ where applied 'recursively' and randomly (each with equal probability), starting from $x=0.5$, a total of $n$ times (between both $f$ and $g$). A total of $N$ elements of $\mathcal O$ (counting repetitions, of course) were generated this way. Then the sorted numbers where plotted against index, marking just a dot in each case to minimize overlap and increase the number of gaps visible in the graph. While for initial tests there were some small observable gaps, setting $K=100$ and $N=10^6$ was more than enough to get a pattern entirely analogous to the one found by david-g, with no visible gaps at the given resolution:
The analysis of actual gaps (which in any case are not seen in the graph, but naturally existed given the fact that the generated set was finite), showed that there are areas with much less probability of appearing (what in the graph manifests as stiffer slopes), something that could also be seen in the 'systematic' non random graph.
These 'low density' areas—for instance, that one immediately above $0.25$, but not including $0.25$ itself (which is actually a fairly common result)—tend to distribute themselves in what seems to be some kind of 'fractal' pattern, which is not at all incompatible with discrete recursive dynamics like the one described here.
Of course, there is a lot of formal work to do in order to prove —and even to unambiguously state— each one of these conjectures. But it's all I have by now.
