Encontrar la n-ésima posición de aparición de un número en una serie infinita de números

Question

Llamemos a $S$ la cadena infinita que se hace concatenando los enteros positivos consecutivos escritos en base $10$ . Así, $$S = 12345678910111213141516171819202122232425\ldots$$

Cualquier número en $S$ se produce varias veces. La primera ocurrencia de $3$ está en la tercera posición de la serie, la segunda ocurrencia está en la decimoséptima posición, y así sucesivamente.

¿Cómo puedo encontrar la posición de la centésima ocurrencia de $3$ ? ¿Existe un patrón?

Answer 1

Puedes resolverlo pensando en algunas listas:

¿Cuántos 3 hay en el 1-10? -- 1

¿Cuántos 3 hay en el 11-20? -- 1

¿Cuántos 3 hay en el 21-30? -- 2

¿Cuántos 3 hay en el 31-40? -- 10

¿Cuántos 3 hay en el 41-50? -- 1

...

¿Cuántos 3 hay en el 91-100? -- 1

Ahora, ¿cuántos 3 hay en 1-100?

¿Cuántos 3 hay en 101-200?

¿Cuántos 3 hay en 201-300?

¿Cuántos 3 hay en 301-400? (obviamente, suficientes)

Entonces, cuando sepas qué número viene en el lugar 100, sólo tienes que contar el lugar, por ejemplo, volviendo a "contar listas".

Answer 2

Podrías probar a contar con cuidado. Si el mío es lo suficientemente cuidadoso, hago que la 100ª ocurrencia de 3 esté en la 889ª posición.

Es el primer dígito de 333.

He contado así:

En el 1 al 99 hay 10 treses en el dígito de la unidad y 10 en el dígito de la decena, por lo que son 20, y por lo tanto hay $3 \times 20=60$ en 1 a 299.

Ahora en 300 a 329 hay 30 en el dígito de la centena y 3 en el dígito de la unidad, así que son otros 33, haciendo 93 hasta ahora. Ahora mira 330331332333 y verás que el tres de la centena es el primer dígito de 333 que, por algunos cálculos sencillos, está en la posición 889.

Answer 3

Fuerza bruta:

[mariano@godot ~]$ ghci
GHCi, version 6.12.1: http://www.haskell.org/ghc/  :? for help  
Prelude> [i | (d,i) <- concat (map show [1..]) `zip` [1..], d == '3'] !! 100 - 1
889
Prelude>