viernes, 3 de marzo de 2017

Las secuencias de Bruijn

(Publicación original en francés)

Pi es un número irracional (es incluso trascendental), ya que no se puede escribir como una fracción, sus cifras decimales nunca son cíclicas. Por ejemplo: 22/7 = 3,142857142857142857 ... Para pi, hay infinita cantidad de dígitos no periódicos, por lo que a simple vista, hay secuencias de todos los dígitos diferentes.

Es normal encontrar a su fecha de nacimiento en los dígitos de Pi, pero ¿Podemos encontrar cualquier secuencia de números (finitos) en decimales de Pi, por ejemplo, 5 millones de números consecutivos, o el trabajo completo traducido a Shakespeare en números? Para ello, pi debería ser un número normal.

Precaución: No calcular pi en binario, ya que violaría el Copyright de todas las obras humanas habidas y por haber.

No es solo con el número pi, existen otros números que también son irracionales normales. Hay un número infinito números normales. Un ejemplo a destacar sería el número de Champernowne. Este número es una concatenación de los números naturales.

C10 = 0,12345678910111213141516171819...

Los números construidos de esa manera son números porque cualquier secuencia finita decimal se repite indefinidamente con probabilidad uniforme. En C10, el inicio de la secuencia de 1234, mucho más tarde, se encontrará 123312341235, luego 112331123411235, y así, 1234 se encuentra estadísticamente 1/10000 en grupos de 4 cifras

¿Un número normal compacto?

Los números naturales son un desastre de decimales, ya que contienen las obras completas de Shakespeare un número infinito de veces. Podemos imaginar una secuencia más compacta que eso.

Tratamos de compactar el número de Champernowne.
  • No repetir los ya presentes decimales. Por ejemplo, después de 1234567891011, no escribiremos 12 porque ya está presente. Esto es inválido 12345678910112.
  • No repetir los números ya presentes en cifras decimales anteriores: En el ejemplo anterior, el 12 es ya presente en los primeros lugares decimales, por lo que podemos ir directamente a 13.
Entonces quedaría así:

0,123456789 10113141516171819 20212242526272829 303233536...

Vemos que gana sólo unas décimas porcentuales, pero podemos ir más allá: Los primeros 9 decimales de C10 no se utilizan para nada, ya que necesariamente están presentes en decimal 10 al 99, que son inútiles ya que están incluidos en decimal del 100 al 999 y así sucesivamente.

Secuencias de Bruijn

En primer lugar, ¿Es inteligente hacer una serie normal compacta mediante la concatenación de números enteros consecutivos? ¿Podemos hacer una secuencia que sea más compacta que la enumeración?

La secuencia de Bruijn (en inglés) hace exactamente eso, y muy bien, ya que cada número de n dígitos en base b está presente sólo mediante la función Bruijn(base,exponente).

En el artículo expuesto de la Wikipedia se encuentra un enlace externo en Javascript, que es un generador de secuencias de Bruijn.

B(10,3) = 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 0 1 1 0 1 2 0 1 3 0 1 4 0 1 5 0 1 6 0 1 7 0 1 8 0 1 9 0 2 1 0 2 2 0 2 3 0 2 4 0 2 5 0 2 6 0 2 7 0 2 8 0 2 9 0 3 1 0 3 2 0 3 3 0 3 4 0 3 5 0 3 6 0 3 7 0 3 8 0 3 9 0 4 1 0 4 2 0 4 3 0 4 4 0 4 5 0 4 6 0 4 7 0 4 8 0 4 9 0 5 1 0 5 2 0 5 3 0 5 4 0 5 5 0 5 6 0 5 7 0 5 8 0 5 9 0 6 1 0 6 2 0 6 3 0 6 4 0 6 5 0 6 6 0 6 7 0 6 8 0 6 9 0 7 1 0 7 2 0 7 3 0 7 4 0 7 5 0 7 6 0 7 7 0 7 8 0 7 9 0 8 1 0 8 2 0 8 3 0 8 4 0 8 5 0 8 6 0 8 7 0 8 8 0 8 9 0 9 1 0 9 2 0 9 3 0 9 4 0 9 5 0 9 6 0 9 7 0 9 8 0 9 9 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 1 9 1 2 2 1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 2 8 1 2 9 1 3 2 1 3 3 1 3 4 1 3 5 1 3 6 1 3 7 1 3 8 1 3 9 1 4 2 1 4 3 1 4 4 1 4 5 1 4 6 1 4 7 1 4 8 1 4 9 1 5 2 1 5 3 1 5 4 1 5 5 1 5 6 1 5 7 1 5 8 1 5 9 1 6 2 1 6 3 1 6 4 1 6 5 1 6 6 1 6 7 1 6 8 1 6 9 1 7 2 1 7 3 1 7 4 1 7 5 1 7 6 1 7 7 1 7 8 1 7 9 1 8 2 1 8 3 1 8 4 1 8 5 1 8 6 1 8 7 1 8 8 1 8 9 1 9 2 1 9 3 1 9 4 1 9 5 1 9 6 1 9 7 1 9 8 1 9 9 2 2 2 3 2 2 4 2 2 5 2 2 6 2 2 7 2 2 8 2 2 9 2 3 3 2 3 4 2 3 5 2 3 6 2 3 7 2 3 8 2 3 9 2 4 3 2 4 4 2 4 5 2 4 6 2 4 7 2 4 8 2 4 9 2 5 3 2 5 4 2 5 5 2 5 6 2 5 7 2 5 8 2 5 9 2 6 3 2 6 4 2 6 5 2 6 6 2 6 7 2 6 8 2 6 9 2 7 3 2 7 4 2 7 5 2 7 6 2 7 7 2 7 8 2 7 9 2 8 3 2 8 4 2 8 5 2 8 6 2 8 7 2 8 8 2 8 9 2 9 3 2 9 4 2 9 5 2 9 6 2 9 7 2 9 8 2 9 9 3 3 3 4 3 3 5 3 3 6 3 3 7 3 3 8 3 3 9 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 5 4 3 5 5 3 5 6 3 5 7 3 5 8 3 5 9 3 6 4 3 6 5 3 6 6 3 6 7 3 6 8 3 6 9 3 7 4 3 7 5 3 7 6 3 7 7 3 7 8 3 7 9 3 8 4 3 8 5 3 8 6 3 8 7 3 8 8 3 8 9 3 9 4 3 9 5 3 9 6 3 9 7 3 9 8 3 9 9 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4 9 4 5 5 4 5 6 4 5 7 4 5 8 4 5 9 4 6 5 4 6 6 4 6 7 4 6 8 4 6 9 4 7 5 4 7 6 4 7 7 4 7 8 4 7 9 4 8 5 4 8 6 4 8 7 4 8 8 4 8 9 4 9 5 4 9 6 4 9 7 4 9 8 4 9 9 5 5 5 6 5 5 7 5 5 8 5 5 9 5 6 6 5 6 7 5 6 8 5 6 9 5 7 6 5 7 7 5 7 8 5 7 9 5 8 6 5 8 7 5 8 8 5 8 9 5 9 6 5 9 7 5 9 8 5 9 9 6 6 6 7 6 6 8 6 6 9 6 7 7 6 7 8 6 7 9 6 8 7 6 8 8 6 8 9 6 9 7 6 9 8 6 9 9 7 7 7 8 7 7 9 7 8 8 7 8 9 7 9 8 7 9 9 8 8 8 9 8 9 9 9

Esto incluye 1000 caracteres en lugar de los 3000 que se requeriría para una lista. Si se observa con detenimiento, 900 no está presente en la secuencia. Esto se debe a que es cíclica, hay que imaginamos bucle, luego del 999 se agrega el 000 del principio (999000), y así se forma el 900.

Esta naturaleza cíclica permite iniciar la función B(b,e) en cualquier lugar mediante la adopción de "e dígitos" y pasar a la siguiente desplazando una figura, ya sea hacia la izquierda o hacia la derecha y así sucesivamente. Después de realizar los cambios, así bn, nos encontramos en el punto de partida en el conocimiento para ser pasado sólo una vez cada número entre 0 y bn-1. ¡impresionante!

Por ejemplo, para abrir una puerta protegida por un código de 3 dígitos, sin la tecla intro, se abrirá tan pronto como la cinta de tres números secretos de forma consecutiva. Si olvida el código, B(10,3), devuelve la secuencia que va a abrir la puerta para asegurarse pulsando las teclas mínimas.

También podemos notar que la siguiente secuencia establece 256 bits en el byte 256 posible binario. La compresión es por 8 en relación con la enumeración.

B(2,8) = 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1

Volviendo al número normal compacto

En B(10,n), todos los números de n dígitos, se representan sólo una vez.

Se intenta ofrecer tantos números posibles en un número compacto. B(10,∞), lo que garantiza es que cada número de longitud infinita aparece sólo una vez.

Los primeros dígitos de pi son:

3 141 592 653 589 793 238 462 643 383 279 502 884 197 169 399 375 105 820 974 944 592 307 816 406 286 208 998 628 034 825 342 117 067 982 148 086 513 282 306 647 093 844 609 550 582 231 725 359 408 128 481 117 450 284 102 701 938 521 105 559 644 622 948 954 930 381 964 428 810 975 665 933 446 128 475 648 233 786 783 165 271 201 909 145 648 566 ...

Como no es cíclico, son infinitos decimales de pi.

Manipular números infinitos requiere muchas precauciones, así que hay que conformarse con un número casi normal, al igual que el universo astronómico, puede ser infinito, pero sólo un volumen finito es accesible para nosotros: B(10,1000000). En este número muy grande allí está formada la cantidad de un millón de números, pero no aparece la obra completa de Shakespeare, ni todos los otros libros publicados ni escritos, ni toda la información acumulada por la humanidad, ya que son significativamente más bajos, aunque el número es colosal. Además, como cada bloque de un millón de dígitos de pi, otros números trascendentes como el de euler, también debería contener el primer millón de dígitos de pi.

Nota: De hecho, Bailey y Richard Crandall propusieron en 2001 una demostración de normalidad en base 2 de pi, euler, y otras constantes fundamentales, basada en la conjetura que no se ha comprobado.

No hay comentarios.:

Publicar un comentario

Si usted lo desea, puede dejar una opinión sobre el artículo, si falta o sobra algo, si parece bueno o malo, de lo contrario ignore este mensaje.