Funciones enteras

Question

Para $x>0$ considerar las siguientes tres funciones:

$$\begin{align} f(x)&=x+1;\\g(x)&=2x;\\t(x)&=3x \end{align}$$

Deje $A(x)$ es el mínimo número de operaciones utilizando únicamente las funciones de $f(x)$ $g(x)$ necesario para obtener $X$$0$.
Deje $B(x)$ es el mínimo número de operaciones utilizando únicamente las funciones de $f(x) $ $t(x)$ necesario para obtener $X$$0$.

Fin o que no existe un conjunto de números que $A(x)<B(x)$.

Answer 1

Para ampliar Antonio sugerencia, para un número $x$, $A(x)$ es simplemente la suma de los dígitos de la representación binaria del número, más el número de dígitos $\lfloor log_2(x) \rfloor$. Del mismo modo, $B(x)$ es la suma de los dígitos de la ternario representación del número, más el número de dígitos $\lfloor log_3(x) \rfloor$.

El valor esperado de $A(x)$ $B(x)$ para un "azar" entero sería:

$E(A(x)) = \frac{3\lfloor log_2(x) \rfloor + 1}2$ y

$E(B(x)) = 2 \lfloor log_3(x) \rfloor + 1$, lo que significa que con $x$ tomado hasta el infinito $\frac{E(A(x))}{E(B(x))} = \frac{3 log_2(3)}4 \approx 1.1887...$

Por lo tanto, es de esperar que $A(x)$ es generalmente más grandes que los $B(x)$. Sin embargo, estadísticamente cualquier número que tiene una representación binaria con menos $1$'s de $2 \lfloor log_3(x) \rfloor + 1 - \lfloor log_2(x) \rfloor$, que sale aproximadamente el $(\frac2{log_2(3)}-1)log_2(x) + 1 \approx 0.26186log_2(x) + 1$. Lo que significa que si un número tiene en su binario de expansión de aproximadamente una cuarta parte o menos de los dígitos (excluyendo el mayor dígito, que podemos eliminar con el $+1$ como debe de ser$1$) $1$s, entonces lo más probable es $A(x) < B(x)$. Esto significa que como $x \to \infty$, el número de enteros con $n$ dígitos que podemos esperar $A(x) < B(x)$ es de aproximadamente $\binom{n}{n/4}$, que no es mucho en comparación con $2^n$, pero todavía tiende a infinito.

Dicho esto, con el fin de responder a la pregunta, tenemos que tratar de encontrar un conjunto infinito de $x$, con lo cual podemos estar seguros de $A(x)<B(x)$. Las potencias de 2 sugerida por mjqxxxx parecen ser buenos candidatos porque ellos minimizar $A(x)$, sin embargo no estoy seguro de cómo usted puede probar $B(x)$ es más grande incluso para esta secuencia (algunos números por muy pequeña probabilidad de tener un muy bajo $B(x)$ valor).