Every two positive integers are related by a composition of these two functions?

How would one prove/disprove this? ...

Conjecture:
Suppose $p$, $q$ are distinct primes, and define $\ f(n) = n p, \ g(n) = \left \lfloor \frac{n}{q} \right \rfloor$ for all $n \in \mathbb{N_+}$; then
for all $x,y \in \mathbb{N_+}$, there exists a composition $F = g \circ g \circ \cdots \circ g \circ f \circ f \cdots \circ f$ such that $ \ y = F(x) $.

A weaker conjecture is implicit in the title question -- same as above, but allowing compositions with the functions in arbitrary order.

If this is something well-known or discussed elsewhere, my apologies (I did search); a reference would then be welcome.

(An analogous conjecture by Donald Knuth involving factorial and integer-squareroot functions suggested this question.)

Solution 1:

The strong one is true. As an example, let us take $p=2, q=3, x=1$. Then the numbers we can reach are $\lfloor \frac {2^r}{3^s} \rfloor$ with $r,s \in \Bbb N_+$. Given $y$, we need to find $r,s$ such that $\log y \lt \log \frac {2^r}{3^s} \lt \log(y+1)$ or $\log y \lt r \log 2 - s \log 3 \lt \log (y+1)$ As we can approximate $\frac {\log 3}{\log 2}$ arbitrarily closely by a rational, we can do this. The same argument works for general $p,q,x$ as long as the logs are rationally independent.