Contar con ciertas cifras permitidas - y siente un fractal

Question

Tengo un amigo ~200 años matemático que se ha olvidado de algunos dígitos y ahora él cuenta cosas de una manera muy extraña manera: cuando él va a contar el $n$-th cosa y $n$ contiene un dígito no puede pronunciar y escribir (porque de su senil de la memoria - oh, pobre hombre) que saltar $n$ e intenta pensar en el próximo número más pequeño después de $n$ que no contiene el dígito.

El pobre viejo matemático que se olvidó de los dígitos 0, 2, 5, 6, 7 cargos:
1, 3, 4, 8, 9, 11, 13, 14, 18, 19, 31, 33, 34, 38, 39, 41, 43, 44, 48, 49, 81, 83, 84, 88, 89, 91, 93, 94, 98, 99, 111, 113, ...

Afirma que la segunda cosa es la tercera, la tercera es de cuarta, cuarta, octava y no veo ningún problema en absoluto. Sin embargo tengo un problema ahora, que es seguir molestando:

¿Cómo puedo fácilmente el nombre de la $n$-th cosa en su sistema de conteo?

En general,

Números naturales que contienen ciertos dígitos se cayó de $\mathbb{N}$. ¿Qué es una fórmula para el $n$th número de esta secuencia?

Veamos un complot de los números de mi amigo todavía recuerdo:
$\hskip0.75in$
que se parece a un azar del lúpulo en la primera mirada, pero tomar la diferencia entre el $\left(n+1\right)$th y $n$elemento th y obtendrás esto:
$\hskip0.75in$
de ahí la segunda parte de la pregunta del título. Yo creo que esto es un poco de estructura fractal y por lo tanto existe una relación de recurrencia que es una solución a mi problema.

En primer lugar, he tratado de examinar un ejemplo muy simple: Base 3; digits allowed: 0, 2:

0, 2, 20, 22, 200, 202, 220, 222, 2000, 2002, 2020, 2022, 2200, 2202, 2220, 2222, ...
adyacente diferencias:
2, 11, 2, 101, 2, 11, 2, 1001, 2, 11, 2, 101, 2, 11, 2, ...

Hay algunos "oscilaciones" visto...
$\hskip0.75in$

Notación:
Deje $n$ ser el número que queremos conseguir, $b$ - la base del sistema numérico, $D$ - conjunto de dígitos permitidos, $N(D, b, n)$ - $n$th número en la secuencia de números de base $b$ con sólo permite dígitos $D$.

Hasta ahora, sólo he visto que $N(\{0,2\},3,n^3+1)=N(\{0,2\},3,n^3)+2$.

Ayúdame, por favor (al menos por pequeñas sugerencias o consejos) para deducir las relaciones que me va a ayudar a vencer el problema y, en consecuencia, ayudar a llegar a un compromiso entre mi amigo y yo. :)

---

^{_{Actualización}}

Puede parecer extraño que me pregunte acerca de la generación de secuencias con algunos de ellos ya se encuentran e incluso trazados. De hecho, ya he encontrado una fácil solución de programación que utiliza combinaciones de dígitos para los números y es altamente ineficiente y no se trata de hablar en este sitio. Estoy preguntando sobre puramente matemáticode la solución.

---

^{_{Actualización}}

Acabo de ver la secuencia de las diferencias de mi ejemplo Base 3; digits allowed: 0, 2 que se parece a esto (en decimal): $$\left\{\begin{cases} 1+3^0,\quad n\equiv 2^0-1\pmod {2^1}\\ 1+3^1,\quad n\equiv 2^1-1\pmod {2^2}\\ 1+3^2,\quad n\equiv 2^2-1\pmod {2^3}\\ \cdots\\ 1+3^p,\quad n\equiv 2^p-1\pmod{2^{p+1}}\\ \cdots \end{casos} \right\}_{n\ge0}$$ En otras palabras, si $a(n)$ $n$ésimo elemento de la secuencia, a continuación, $$a(2^{p+1} n + 2^p - 1) = 1 + 3^p, \quad p \ge 0$$ ^{_{Actualización}}
El uso de esta ideas, llego a la conclusión de que $$a(n)=\sum_{i=1}^\infty\frac{1}{2^i}\sum_{j=1}^{2^i}cos(j\,n\,π/2^{i-1})$$ Por lo tanto, $$N(\{0,2\},3,n)=N(\{0,2\},3,n-1)+1+3^\wedge(\sum_{i=1}^\infty\frac{1}{2^i}\sum_{j=1}^{2^i}cos(j\,n\,π/2^{i-1}))$$ Pero esta solución no me ilumine en una solución general.

Answer 1

La respuesta original trabajado si los dígitos se podría decir que se incluye el cero. He guardado. Deje que él sea capaz de decir $0,1,3,4,8$, el algoritmo sería para expresar $n$ base $5$, a continuación, cambiar los dígitos $0 \to 0, 1 \to 1, 2 \to 3, 3 \to 4, 4 \to 8$ y se obtiene el $n^{\text{th}}$ número se puede decir. Así, por $n=1234567,$ tenemos $1234567_{10}=304001232_5 \to 408001242$ $1234567^{\text{th}}$ número se puede decir.

Para la pregunta original, en donde se puede decir $1,3,4,8,9$, debido a $0$ está entre los olvidados de los números, hay $5$ uno de los números de dos dígitos se puede decir (no $4$), $25$ dos números de un dígito que él puede decir, etc. Para números con a $k$ dígitos, hay $5+5^2+\dots +5^k=\dfrac {5^{k+1}-5}{5-1}=N(k)$ encontrar el $n^{\text{th}}$ número que él puede decir, encontrar el $k$ tal que $N(k) \lt n \le N(k+1).$ El número de ha $k+1$ dígitos. Si $n=N(k+1),$ $n^{\text{th}}$ número se puede decir que es una serie de $k\ 9$'s. De lo contrario, calcular los $d_{k+1}=\left \lfloor \frac {n-N(k)}{5^k} \right \rfloor$, que estará en el rango de $[0,4]$ Con la conversión de $0 \to 1, 1 \to 3, 2 \to 4, 3 \to 8, 4 \to 9$ tenemos el primer dígito. Ahora calcular $n_k=n-(1+d_{k+1})5^k$ y expresar $n_k$. Será lo suficientemente grande como para requerir $k$ dígitos. Por ejemplo, si queremos que la $397^{\text{th}}$ número se puede decir, nos encontramos con $k=3, N(k)=155$ números a los que puede decir con hasta tres dígitos. $d_4=\left \lfloor \frac {397-155}{125} \right \rfloor=1$, por lo que el primer dígito es $3$. A continuación, $n_3=397-2\cdot 125=147$ y seguimos $d_3=\left \lfloor \frac {147-30}{25} \right \rfloor=4$, por lo que el siguiente dígito es $9$. $n_2=147-5\cdot 25=22, d_2=\left \lfloor \frac {22-5}{5} \right \rfloor=3$ así que el siguiente dígito es $8$ y por último tenemos a $2$ a la izquierda y el último dígito es $4$. El $397^{\text{th}}$ número se puede decir es $3984$. Espero que recuerda a $0$.

Answer 2

Al menos si sólo quieres asymptotics, es más fácil responder a la inversa de la primera pregunta: ¿cuántos de los números enteros entre el $0$ $N$ (inclusive) puede a su amigo de nombre?

Digamos que el trabajo en base a $b$ y que su amigo sólo puede usar $k$ de los posibles $b$ dígitos, y por simplicidad vamos a suponer que él puede usar $0$. El caso más fácil es al $N = b^n - 1$, ya que en este caso es claro que su amigo puede nombrar exactamente $k^n$ números: de la $n$ posible dígitos, su amigo puede elegir libremente cada uno de ellos para ser uno de los $k$ permitido dígitos.

Es decir, si $f_{b, k}(N)$ es el número de números enteros entre el $0$ $N$ que su amigo puede nombrar, a continuación,

$$f_{b, k}(b^n - 1) = k^n.$$

Esto sugiere que asintóticamente esperamos

$$f_{b, k}(N) \approx N^{ \log_b k }$$

y, por tanto, la inversa de la función debe satisfacer asintóticamente

$$f_{b, k}^{-1}(M) \approx M^{ \log_k b }.$$

Rechazando $0$ no es mucho más difícil y no cambia el asymptotics mucho pero conseguir más preciso de la cuenta es complejo y depende tanto de los dígitos de $M$ y en los dígitos que están permitidos / no permitidos. En el ejemplo original,

$$f_{10, 5}^{-1}(M) \approx M^{ \log_5 10} \approx M^{1.43}$$

aunque esto no será todo lo que precisa para valores aleatorios de $M$ porque mucho depende de si el primer dígito es permitido.