Cómo encontrar el k-ésimo dígito del enésimo número en esta secuencia

Answer 1

Si está buscando el k-ésimo dígito de a (n) solo necesita averiguar los primeros k dígitos del mismo, no el número entero.

Además, no es necesario “calcular” números: es solo una cadena.

Insertar caracteres en una cadena larga puede ser ineficiente: una estructura de datos eficiente en el tiempo para dicha cadena podría ser una lista encadenada, pero consumirá memoria.

Espero que esto ayude, sin estropear su esfuerzo de investigación.

[Editar]
El problema me pareció divertido y lo pensé un poco más …

Si bien el número de dígitos de a (n) crece rápidamente, la buena noticia es que su problema está limitado .

En el lado n, considere que cuando [matemáticas] n> 10 ^ k [/ matemáticas] encontrar el k-ésimo dígito es trivial y es simplemente el k-1-dígito de n.

Además, el primer dígito de a (n) es siempre 1 y el segundo dígito aa (n) es siempre el primer dígito de n. Hasta ahora para k = 1 yk = 2. En términos más generales, se pueden encontrar soluciones de trival para [math] k <D_n + 1 [/ math], [math] D_n [/ math] es el número de dígitos de n (es decir [math] D_n = floor (log_10 (n )) + 1 [/ matemáticas].

En el lado k, es posible calcular explícitamente el número de dígitos [math] d_n [/ math] de a (n) (requiere dos fórmulas de recurrencia simples, que producen series geométricas que dependen de ny el número de dígitos de n, [matemática] D_n [/ matemática], y arrojando un resultado casi explícito). Cuando [math] k> d_n [/ math], no hay resultado. Por ejemplo, para n = 9, k debe ser menor que 257.

Hasta ahora, no he encontrado una idea más inteligente para reducir radicalmente la complejidad del algoritmo para n mayor que 10. Recuerde que es o (nk), solo si puede asegurarse de que insertar un dígito dentro de una cadena sea una constante tiempo de operación.

Una idea interesante podría ser paralelizar el algoritmo, ya que dada una estructura de datos adecuada para representar la cadena de dígitos, los k nuevos dígitos pueden insertarse en paralelo en cada iteración hasta n. Y más adelante, las iteraciones también se pueden canalizar : uno puede comenzar a insertar dígitos para una nueva iteración mientras que la actual ni siquiera está terminada (solo debe tener cuidado de que esta nueva iteración no se haga cargo de la anterior …). Esto llevaría a una carga bastante pesada en la CPU …

En el lado de la memoria, una cadena de dígitos truncada al k-ésimo dígito puede empaquetarse en [math] k + 1 [/ math] bytes. Una implementación básica de una cadena usaría [math] 9 k [/ math] bytes suponiendo compensaciones de 64 bits, y considerando la alineación de palabras habitual de las estructuras, en la práctica [math] 16 k [/ math] bytes.

F.

Answer 2

Puede ver esto como un problema de programación dinámica. No te asustes, te ayudaré.

Comience por encontrar una relación de a (k, n) con a (__, n-1).
¿Qué tal cuando k está INCLUSO ?
¿Y qué pasa cuando k es impar?
Responda lo que pensó y podemos continuar.

Answer 3

Cuando k es par, puede observar fácilmente que n será la respuesta, ya que n se habría insertado entre cada dos números. Por lo tanto, todas las posiciones pares están ocupadas por n.

Ahora, cuando K es impar: piense en eliminar todas las posiciones pares, el número que quedaría será un (n-1) y su K se reduciría a K / 2 (división entera) +1

por ej.
1. encontrar el séptimo número en un (4)
es lo mismo que encontrar el 4to número (7/2 + 1) en un (3)
ahora 4 es par y ans será 3 en sí mismo.
2. encontrar el quinto número en un (3)
es lo mismo que encontrar el tercer número (5/2 + 1) en un (2)
es lo mismo que encontrar el segundo número (3/2 + 1) en un (1)
que será 1.

Espero que esto aclare las cosas.

Answer 4

La secuencia de dígitos en [matemática] a (n) [/ matemática] viene dada por los dígitos de [matemática] n [/ matemática] y los dígitos de [matemática] a (n-1) [/ matemática]. De hecho, deje que [math] d (x, i) [/ math] sea un dígito de [math] x [/ math] con índice [math] i [/ math]. Deje también [matemáticas] a (n, k) = d (a (n), k) [/ matemáticas]. Estoy adoptando un sistema de posición indexado 0, por lo que el primer dígito es el que está en la posición 0. Entonces, sabemos que la representación de [math] a (n) [/ math] es:

donde [math] | n | [/ math] es el número de dígitos de [math] n [/ math].

Esto puede ser suficiente para que vea que los dígitos de [matemáticas] a (n-1) [/ matemáticas] están presentes en [matemáticas] a (n) [/ matemáticas] en las posiciones [matemáticas] 0, | n | + 1, 2 | n | +2, \ ldots, i (| n | +1), \ ldots [/ math].

Ahora, deje que [math] r \ equiv k \ pmod {| n | + 1} [/ matemática] con [matemática] 0 \ le r <| n | +1 [/ matemática] ( es decir, [matemática] r [/ matemática] es el recordatorio de la división de [matemática] k [/ matemática] por [matemáticas] | n | +1 [/ matemáticas]). Si [math] r = 0 [/ math], esto significa que estamos viendo uno de los dígitos de [math] a (n-1) [/ math], el que tiene índice [math] \ frac {k} {| n | +1} [/ matemáticas]. De lo contrario, estamos viendo uno de los dígitos de [math] n [/ math], es decir, el que tiene índice [math] r-1 [/ math].

Para poner esto en código (python, para ser exactos):

matemáticas de importación

def nd (n): # número de dígitos
return int (math.ceil (math.log (n + 1, 10)))

def a (n, k): # dígito de a (n) en el índice k
si n == 1:
devolver ‘1’

ndn1 = nd (n) + 1
q, r = divmod (k, ndn1) # q es el resultado de dividir, r es el recordatorio
si r == 0:
devuelve a (n – 1, q)
más:
retorno str (n) [r – 1]

Este código parece ejecutarse en tiempo lineal con respecto a [math] n [/ math], ya que para obtener a(n, k) necesita obtener (a veces) a(n - 1, ...) . Pero el valor de [math] k [/ math] seguirá dividiéndose entre [math] | n | +1 [/ math] y, por lo tanto, alcanzará valores pequeños rápidamente, por lo que el código se ejecuta en [math] O (\ min (\ log k, n)) [/ math] time, que, dado que los argumentos de la función están delimitados por [math] 2 ^ {63} [/ math] puede simplificarse efectivamente a [math] O (\ log k) [/ matemáticas]. Además, a menudo obtendrá un valor de [math] r \ neq 0 [/ math], finalizando así el proceso sin recurrencia. Por ejemplo, [math] a (99,2 ^ {62} -1) [/ math] termina en dos pasos.

Todavía hay un problema con esto: si prueba el código, verá que obtiene un resultado para a(1,2) , que en su lugar debe estar indefinido ([math] a (1) [/ math] tiene solo 2 dígitos). De hecho, este código devolverá un resultado para cualquier valor de [math] k [/ math], pero solo debería devolverlo cuando [math] k [/ math] es menor que el número de dígitos de [math] a (n )[/matemáticas].

Calcular el número de dígitos no es exactamente trivial, pero se puede determinar con un poco de inducción. No he formalizado la prueba que se necesita, pero puedo ver que el número que queremos es [matemáticas] 1 + 2 ^ {b_2} \ cdot 3 ^ {b_3} \ cdot \ ldots [/ math], donde las bases de los poderes son [matemática] 2, 3, \ ldots [/ matemática], hasta [matemática] | n | + 1 [/ math], para algunos exponentes [math] b_i [/ ​​math].