Los 9 billones de nombres de Dios

Question

TLDR; voy en matemáticas aventura y conseguir abrumado :)

Algunos antecedentes:

Mis matemáticas no es muy grande (yo no puedo leer la notación), pero soy un programador competente y razonable solucionador de problemas. He hecho la primera docena o así de Euler problemas y tiene la intención de continuar con eso cuando tengo tiempo.

El problema:

En Arthur C Clarke el cuento de "Los 9 mil Millones de Nombres de Dios" los nombres de Dios son todas las posibles secuencias en un indeterminado alfabeto, que no tengan más de nueve caracteres, donde no hay letra se produce más de tres veces en sucesión.

Por curiosidad, que empecé a jugar con la determinación de cómo muchos de secuencias válidas no están dentro de un rango.

Empecé con la repetición de dígitos en base 10 números, en el fondo es el mismo problema que la repetición de letras en un alfabeto.

No está muy bien informado acerca de las matemáticas, pensé en escribir un programa de iterar sobre los rangos y el recuento de todos los elementos que cumplen la condición anterior, a continuación, poner los resultados en una hoja de cálculo para ver si hay un patrón claro de algún tipo surgido que me permitiera escribir un algoritmo para determinar el número de secuencias válidas en un determinado rango.

Empecé con la restricción de que un dígito podría aparecer sólo una vez, por lo que en el rango 0-99 hay 9 no válido secuencias, 11, 22, 33, etc., dejando 91 válido "nombres de Dios".

Aquí está la tabla de 0-99 a través de 0-99999999. Me detuve allí, porque más allá de que es donde se empezó a tomar mucho tiempo para calcular y yo no quería desviarse de la optimización.

0-99              91
0-999            820
0-9999          7381
0-99999        66430
0-999999      597871
0-9999999    5380840
0-99999999  48427561

También me genera una tabla de dígitos que aparecen no más de dos o tres veces:

0-999            991
0-9999          9820
0-99999        97300
0-999999      964081
0-9999999    9552430
0-99999999  94648600

0-9999          9991
0-99999        99820
0-999999      997300
0-9999999    9964000
0-99999999  99550081

No he llegado a mirar en estos, sin embargo, porque me quedé fascinada por la primera tabla.

La primera tabla que aparece en OEIS como A002452.

Pasando de allí, mirando en todo tipo de cosas diferentes, entre ellos las secuencias de números en diferentes marcador de posición de las columnas en las tablas, las diferencias entre los números en columnas diferentes y/o tablas, etc. Miré a todo tipo de cosas, me gustaría que documentó más, yo estaba de brazos cruzados jugando con una hoja de cálculo y Googlear secuencias. Con una rápida búsqueda en Google me encontré con algunas de estas secuencias en todo tipo de lugares extraños, algunos ejemplos incluyen las transformaciones de Lucas Números, las soluciones a Kakuro / Addoku / Soduku puzzles, repunits, las coordenadas geodésicas de los rostros, incluso el hueso de Ishango, que yo nunca había oído hablar de antes. Es justs va en y en.

Matemáticas está llena de este tipo de cosas ¿no? Y sólo estoy mirando a un pequeño problema de una muy ángulo específico, esto es sólo la punta del iceberg aquí ¿no?

Preguntas/solicitudes de comentarios:

1. Estoy suponiendo que mi aventura no es nada extraordinario en todos y matemáticas está lleno de este inesperado relaciones de las cosas, verdad?

2. ¿Cuál es la manera correcta de describir el problema que se describe en los primeros párrafos, ¿qué necesito para aprender a entenderlo?

3. Me encantaría escuchar cualquier comentario/curiosidades, etc. relativas a esta pequeña aventura, por favor!

Answer 1

Los nombres que usted describe puede ser descrito por una expresión regular, por lo tanto el conjunto de todos los nombres es un lenguaje regular. De forma equivalente, los nombres pueden ser reconocidos por un determinista de la máquina de estados finitos (no puedo pensar en un con $28 dólares de los estados, pero esto probablemente no es la óptima). Si $G_n$ denota el número de nombres de longitud $$ n, se sigue que la generación de la función $\sum G_n x^n$ es racional y puede ser calculado de manera bastante explícita (en diferentes formas), lo que conduce a una forma cerrada para $G_n$ como una suma de exponenciales $\alpha^n$ para varios $\alpha$ (posiblemente con coeficientes polinomiales) a través de la fracción parcial de la descomposición.

En otras palabras, dichas secuencias son bien entendidos desde varios puntos de vista. Lamentablemente, no conozco a un particular de primaria introducción a este material. El más simple trivial ejemplo de una secuencia de este tipo es una secuencia contada por los números de Fibonacci: las palabras son palabras sobre un alfabeto de dos cartas $A, B$, con la restricción de que la carta $B$ nunca puede aparecer dos veces en una fila. Aquí la generación de la función $\sum F_n x^n = \frac{x}{1 - x - x^2}$ y esto le da la forma cerrada

$$F_n = \frac{\phi^n - \varphi^n}{\phi \varphi}$$

donde $\phi \varphi$ son el positivo y negativo de las raíces de $x^2 = x + 1$. Una similar, pero más complicado, cerrado de forma que existe para que la secuencia que usted está interesado en.

Lo más parecido que conozco a una completa referencia es el Capítulo 4 de Stanley Combinatoria Enumerativa, pero esto no es fácil de leer. Sipser la Introducción a la Teoría de la Computación se analiza regular idiomas y máquinas de estado finito, pero no la dirección de la enumerativa de los aspectos de la teoría. Hay también una discusión de estos temas (y mucho, mucho más) en Flajolet y Sedgewick de la Analítica de la Combinatoria (además no es fácil lectura).

---

Desde regular las lenguas son, en cierto sentido, el más sencillo de los lenguajes, las secuencias de conteo de palabras en regular idiomas aparecen con frecuencia en muchas situaciones. Por ejemplo, elija una palabra $w$. El conjunto de todas las palabras en los cuales $w$ no aparece como un subword es un lenguaje regular, y así el uso de la maquinaria describo arriba, uno puede calcular la probabilidad de que una secuencia aleatoria de letras de una cierta longitud o no contener $w$. Esto tiene muchas aplicaciones, por ejemplo, para el estudio de secuencias de ADN, si quieres conocer cómo es la probabilidad de que una determinada secuencia de nucleótidos $w$ podría ocurrir en una hebra de ADN, sin embargo, muchos nucleótidos de largo por casualidad. Más prosaicamente, usted puede calcular, por ejemplo, la probabilidad de volteo de 7 $$ colas en algún momento de los $150$ coin flips.

Answer 2

Estos son bastante vagas preguntas, pero aquí va:

1. Verdadero. Hay un montón de conexiones inesperadas y relaciones, y parte de la diversión es desentrañar el misterio de su ocurrencia (ver, por ejemplo, "bijective pruebas").

2. La combinatoria. Más específicamente, la generación de funciones. Trate de generatingfunctionology. Usted puede encontrar que no es demasiado fácil.

3. El número de secuencias de longitud $n$ compuesto de bits (0 y 1) y ninguna de las dos consecutivos 1 es de $F_n$, el $n$ésimo número de Fibonacci.

Answer 3

Yo estaba trabajando en este problema hace varios años y descubrió un polinomio que calcula el número de 1,2,3,...9 letras de las palabras con la n-letra del alfabeto.

número de palabras = n^9 +n^8 +n^7 -5n^6 +n^5 +n^4 +4n^3 -2n^2 +n

n =9, palabras =432,661,347 Este es el mismo número de Ross Millikan encuentra utilizando una hoja de cálculo

n =12, palabras =5,610,940,140 Ross Millikan en una lista como de 5,6 millones de

n=13, palabras =11,459,252,883 Ross Millikan aparece como 11.5 mil millones de dólares

Aquí todo el mundo parece pensar que (en la historia), los dos contrató a ingenieros de imprimir un 9 mil millones de lista de palabras. La gente de aquí están tratando de calcular que n-letra del alfabeto sistema da a los 9 mil millones de palabras. La lista que los ingenieros impreso era mucho más de 9 mil millones de dólares. En la historia, "[Los monjes] han sido la compilación de una lista que deberá contener todos los posibles nombres de Dios." Los monjes creen que Dios tiene alrededor de 9 mil millones de nombres. "Bien, ellos creen que cuando ellos han listado todos Sus nombres - y calculan que hay cerca de nueve millones de ellos - el propósito de Dios se logrará." Los ingenieros de la impresión de cada posible nombre de Dios. No todo nombre que se imprime es uno de los nombres de Dios.

Supongamos que desea imprimir todos los POSIBLES 2-las letras de las palabras en el idioma inglés. Hay 101 real 2-las letras de las palabras. http://www.yak.net/kablooey/scrabble/2letterwords.html Si usted inicia la impresión de la lista, comenzando con el AA, AB, AC, a través de ZX, ZY, y ZZ. A usted le ha impreso 26^2 =676 palabras posibles(no 101)

Answer 4

Una solución para el problema específico que se puede hacer de la siguiente manera: definir $A(n)$ como el número de cadenas de longitud $$ n con los dos últimos caracteres diferentes, $B(n)$ como el número de cadenas de longitud $$ n con los dos últimos caracteres de la misma, pero la tercera a la última diferentes, y $C(n)$ como el número de cadenas de longitud $n$ con los tres últimos caracteres de la misma, pero la cuarta a la última diferentes (o falta). Podemos establecer un conjunto de relaciones de recurrencia basado en la adición de otro carácter a la cadena. $A(n+1)=8(a(n)+B(n)+C(n)$ porque solo tenemos que añadir un cierto carácter diferente de la última. $B(n+1)=A(n)$ porque tenemos que agregar el mismo carácter hasta el final de la $Una$ de la cadena. Del mismo modo $C(n+1)=B(n)$. Una comprobación de validez es que podemos añadir cualquier carácter a un $A$ o $B$ cadena y todavía estar "en juego", pero no podemos añadir una coincidencia con el personaje a $C$ cadena. Podemos empezar con $Un(1)=9, B(1)=0, C(1)=0$Esto es, en una forma que una hoja de cálculo puede manejar. En realidad, llegar a $432661347$, $\frac{1}{20}^{\text{th}}$ de $9 millones de$ (o $\frac{1}{20000}^{\text{th}}$ teniendo en cuenta que Clarke era Británico). Si su teología no es mejor que su aritmética, debemos estar seguros.

Answer 5

Deje de $p_n(k)$ denotar el número de nombres con longitud $\le$ n para el alfabeto tamaño de la $k$, tal que ninguna carta aparece más de tres veces en sucesión. @RossMillikan 's recursiva solución puede ser utilizado para generar los polinomios $p_n(k)$ (tenga en cuenta que $p_9(k)$ confirma @Jeff 's polinomio de respuesta):

$$ \begin{align} n &\quad p_n(k)\\ 1 &\quad k\\ 2 &\quad k^2 + k\\ 3 &\quad k^3 + k^2 + k\\ 4 &\quad k^4 + k^3 + k^2\\ 5 &\quad k^5 + k^4 + k^3 - k^2 + k\\ 6 &\quad k^6 + k^5 + k^4 - 2k^3 + k^2 + k\\ 7 &\quad k^7 + k^6 + k^5 - 3k^4 + k^3 + k^2 + k\\ 8 &\quad k^8 + k^7 + k^6 - 4k^5 + k^4 + k^3 + 2k^2\\ \color{blue}{9} &\quad \color{blue}{k^9 + k^8 + k^7 - 5k^6 + k^5 + k^4 + 4k^3 - 2k^2 + k}\\ 10 &\quad k^{10} + k^9 + k^8 - 6k^7 + k^6 + k^5 + 7k^4 - 5k^3 + k^2 + k\\ 11 &\quad k^{11} + k^{10} + k^9 - 7k^8 + k^7 + k^6 + 11k^5 - 9k^4 + k^3 + k^2 + k\\ 12 &\quad k^{12} + k^{11} + k^{10} - 8k^9 + k^8 + k^7 + 16k^6 - 14k^5 + k^4 + 3k^2\\ 13 &\quad k^{13} + k^{12} + k^{11} - 9k^{10} + k^9 + k^8 + 22k^7 - 20k^6 + k^5 - 3k^4 + 9k^3 - 3k^2 + k\\ 14 &\quad k^{14} + k^{13} + k^{12} - 10k^{11} + k^{10} + k^9 + 29k^8 - 27k^7 + k^6 - 9k^5 + 21k^4 - 9k^3 + k^2 + k\\ 15 &\quad k^{15} + k^{14} + k^{13} - 11k^{12} + k^{11} + k^{10} + 37k^9 - 35k^8 + k^7 - 19k^6 + 41k^5 - 19k^4 + k^3 + k^2 + k\\ \end{align}$$

Aquí está el Sabio aplicación que he utilizado para obtenerlos:

def namecount(n):
#return a formula for the number of names with length <= n
#for variable alphabet size k
    var('k')
    A,B,C = k,0,0
    tot = A + B + C
    for i in [2..n]:
        a,b,c = (k-1)*(A + B + C), A, B
        A,B,C = a,b,c
        tot += A + B + C
    return expand(tot)

for n in [1..15]: print n, namecount(n)

Sería bueno tener una fórmula para los coeficientes de estos polinomios.