¿Cada dos números enteros positivos están relacionados por una composición de estas dos funciones?

Question

¿Cómo se puede probar o refutar esto? ...

Conjetura :
Supongamos que $p$ , $q$ son primos distintos, y definimos $\ f(n) = n p, \ g(n) = \left \lfloor \frac{n}{q} \right \rfloor$ para todos $n \in \mathbb{N_+}$ Entonces
para todos $x,y \in \mathbb{N_+}$ existe una composición $F = g \circ g \circ \cdots \circ g \circ f \circ f \cdots \circ f$ tal que $ \ y = F(x) $ .

Una conjetura más débil está implícita en la pregunta del título -- igual que la anterior, pero permitiendo composiciones con las funciones en arbitraria orden.

Si se trata de algo conocido o debatido en otra parte, pido disculpas (he buscado); en tal caso, se agradecería una referencia.

(Un análogo conjetura de Donald Knuth con las funciones factorial y raíz cuadrada entera sugirió esta pregunta).

Answer 1

El fuerte es cierto. Como ejemplo, tomemos $p=2, q=3, x=1$ . Entonces los números que podemos alcanzar son $\lfloor \frac {2^r}{3^s} \rfloor$ con $r,s \in \Bbb N_+$ . Dado $y$ tenemos que encontrar $r,s$ tal que $\log y \lt \log \frac {2^r}{3^s} \lt \log(y+1)$ ou $\log y \lt r \log 2 - s \log 3 \lt \log (y+1)$ Como podemos aproximar $\frac {\log 3}{\log 2}$ arbitrariamente cerca de un racional, podemos hacerlo. El mismo argumento sirve para $p,q,x$ siempre que los registros sean racionalmente independientes.