¿Es posible representar cada número enorme en forma abreviada?

Question

Considere la siguiente expresión.

16313107343153908912074032799466965289077771751767944648966669091376847859711382649033004075188224

Este es un 98 dígito decimal del número. Esto puede ser representado como $424^{37}$ que acaba de 5 dígitos.

o considere la posibilidad de este número:

169073514923335704910781770943386358513266262695082143017841776072866115341460524847957712758961906613726756319811278031296495217851424697035006912866170000718058938908895318046488014239482587502405094704563355293891175819575253800433524527755979112979015643959678935175113080573154675124941893322526864309352491218559149178661812525480110726656169760698869582961494753085501445661456518392243133318400757678300223742779393224526956540729201436933362390428757552466287676706382965998179063631507434507871764226500558776264

Esta $200$ dígito decimal número puede ser expresado como $\log_e 56$ cuando se descartan primera $6$ números y, a continuación, considerar en primer lugar $200$ dígitos.

Ahora la pregunta es, ¿es posible representar todos y cada gran número aleatorio usando muy pocos caracteres como sea posible, en teoría.

...También, ¿hay alguna manera estándar para reducir matemáticamente?

Answer 1

No. El problema es muy simple: hay más gran número de formas abreviadas. Supongamos que me permiten utilizar los números del 0 al 9, el alfabeto inglés, y espacios para describir lo que los números que usted desea; eso es solo el $37$ personajes. Sólo hay $37^{140}$ expresiones se pueden escribir usando estos personajes que es $140$ caracteres o menos (la longitud de un tweet!), tan sólo hay $37^{140}$ números que posiblemente podría tweet a alguien más. En particular, desde la $\log_{10} 37^{140} = 219.5$, esto implica que hay al menos un número con $220$ dígitos que es imposible tweet a alguien sin usar algo distinto de números y en inglés.

Bien, voy a ser aún más generoso: voy a dejar de usar todos los $127$ caracteres ASCII. Eso significa que hay un $127^{140}$ posible tweets, algunos de los cuales matemáticamente describir algún tipo de número, y desde $\log_{10} 127^{140} = 294.5$, existe al menos un número de con $295$ dígitos que es imposible tweet a alguien más (de nuevo, suponiendo que utiliza Twitter ASCII). Yo podría darte todo el Unicode alfabeto y todavía no será capaz de tweet, por ejemplo, el tipo de números primos que criptosistemas de clave pública de uso.

Estos tipos de preguntas son estudiados en ciencias de la computación y la teoría de la información; usted encontrará que la palabra complejidad de Kolmogorov lanzados alrededor, así como la palabra entropía.

Answer 2

Si se sigue desde el principio del casillero que cualquier algoritmo de compresión sin pérdida que reduce el tamaño de al menos un número debe aumentar el tamaño de otro - más la compresión sería invertible. Para más resultados con cualquier libro de texto Teoría algorítmica de la información (complejidad de Kolmogorov), por ejemplo, Li; Vitanyi. Una introducción a la complejidad de Kolmogorov y sus aplicaciones.

Answer 3

Como en otras respuestas, por lo menos, pigeon-hole principio muestra que "la mayoría" de los números no puede ser "describe" en menos caracteres que sus decimal (o lo-que-pick) expresión...

En mi opinión, la pertinente desarrollado cuerpo de ideas es "Solomonov-Chaitin-Kolmogorov" complejidad", que es sobre descriptional (o programa de longitud) de la complejidad, en lugar de en tiempo de ejecución "de la complejidad".

Esto hace recordar a uno de los "más pequeños aburrido número de" pseudo-paradoja, que sostiene que el primer no-interesante número tiene algo de interés porque es la primera...

La conclusión es que el "tamaño" de los números no es fiable, comparable a "descriptional la complejidad", en general, aunque la mayoría de los grandes-ish números también son descriptionally complejo, por pigeon-hole.

Hay un libro de Li y Vitanyi que es no sólo la autoridad, sino que es fascinante legible...

Answer 4

Mi manera de entender esta pregunta, la respuesta es "sí". Simplemente escriba el número en, digamos, la notación hexadecimal, y siempre va a ser más corta que en decimal (si es >=100000). Si usted está buscando el más corto de la representación, sin embargo, que está bien definido sólo si se especifica exactamente lo que cuenta como una representación válida de un número. Después de todo, cada número viene técnicamente puede ser representado en un solo dígito si usted elige una lo suficientemente grande base (al menos uno mayor que el número en sí).

Acerca de la forma estándar para reducirlo: yo diría que el sistema decimal es la forma estándar de la reducción de los números de sólo escribir el número apropiado de guiones. :-) En el sentido señalado por Bill Dubuque, no hay ninguna representación de que es más de espacio eficiente, en principio, que es que si usted transfiere el problema a una forma más abstracta de dominio. Si, por el contrario, se busca el menor representación mediante un conjunto dado de símbolos matemáticos, entonces no, no hay una manera estándar para encontrarlo. También sospecho ningún algoritmo puede hacer mejor que la búsqueda por fuerza bruta (que es, en primer lugar comprobar todos los números representables con 1 personaje, y luego los representable en 2 caracteres, y así sucesivamente). En cualquier caso, nadie debería escribir un número como "loge 56 (registro de 56 base e) cuando se descartan los primeros 6 números y, a continuación, considere la posibilidad de primeros 200 dígitos, de modo que no es concebible conjunto de símbolos estándar que se de cuenta de que de todos modos.

Answer 5

De ello se desprende que, para cualquier singulares o por lotes esquema de compresión, este y este son correctos.

Sin embargo, igualmente se desprende que, independiente de la eficiencia, para cualquier número arbitrario que puede ser reducido a alguna relación en el espacio infinito de todas las relaciones posibles, la respuesta es un gran sí. Por ejemplo, podemos comprender la notación para ser $log_e56$ unidades de distancia de 0 en un discreto o continuo de la secuencia de los números reales, y podemos aprovechar esta propiedad para construir un similar relacional esquema de partición que se expresa en un menor número de bytes de locales de datos.

La diferencia es que, en el caso de infinito heurística de espacio, usted está ocultando reglas de mayor complejidad que los datos de entrada detrás de las escenas. Esto puede funcionar muy bien en limitado computacional contextos (por ejemplo, en situaciones donde es más caro para enviar un mensaje a través del cable de realizar un cálculo a nivel local), pero en el dominio de la expresión pura, es definably menos eficiente.

Poner este concepto en la práctica, usted puede siempre salirse con la elegante, tweet-longitud de las expresiones de sus datos, siempre que la referencia no está contenida dentro del cuerpo de texto. El enfoque correcto es proporcionar a su simplificación para establecer el contexto y ofrecer un puntero (es decir, en la forma de un enlace) a la referencia. Como se puede razonablemente suponer que el espacio para tal punteros es ilimitado (es decir, por la prestación de un cada vez mayor espacio de carácter), siempre vas a ser capaz de proporcionar una necesariamente sucinto de expresión.