¿Cómo acortar números primos en una base de datos?

Question

Se me dan mal las matemáticas y el inglés no es mi lengua materna. Tened paciencia conmigo. Gracias.

Estoy ejecutando un script de búsqueda de números primos y escribiendo el resultado en una base de datos SQLite3.

Ahora estoy buscando una manera de acortar estos números primos porque no quiero verme obligado a almacenarlos como cadenas si se hacen muy grandes/largos. No quiero perder precisión, así que la versión acortada debería permitir volver a calcular el valor original.

No me importa si la base de datos tiene datos legibles por humanos. Puedo hacer que sean legibles para humanos cuando vuelva a obtener datos de la base de datos.

Navegado https://oeis.org y https://primes.utm.edu para ver cómo organizan su base de datos, pero después de eso sólo estaba más confuso. ¿Existe alguna práctica recomendada? Estoy realmente atascado.

Answer 1

Podrías intentar guardar la base de datos en formato binario Supongo. Por lo demás, cada cifra de un número tiene un tamaño fijo de presumiblemente 1 byte, mientras que incluso sin mejoras se podrían almacenar números de hasta 256 en 1 byte en formato binario.

También puede consultar Codificación Huffman pero dudo que ayude en un caso de primera.

Answer 2

Consideremos cuánta compresión se puede obtener mediante una codificación inteligente de sus primos para reducir la cantidad de memoria o espacio de archivo que ocupa cada uno.

Sea cual sea la codificación que elijas, supongo que querrás que funcione para cualquier prime, de modo que no importa qué primo codificar por este método, puede recuperar el primo original a partir de la codificación.

Supongamos que tienes una función que te puede decir el $n$ el primo más grande lo suficientemente rápido como para poder codificar el $n$ mayor primo como el número $n$ y almacenarlo en ese formato. Es la codificación más densa posible. Asumiendo que almacenaste el número en formato decimal, para almacenar primos mayores que $15\,485\,863$ (el millonésimo primo) necesitaría utilizar siete dígitos para algunos de los primos. Es decir, mediante este esquema de compresión increíblemente eficiente se podría almacenar números de ocho o nueve dígitos como $15\,485\,867$ o $179\,424\,673$ en sólo siete dígitos. Para almacenar números primos mayores que $179\,424\,673$ (el diezmillonésimo primo) tendrías que utilizar ocho dígitos, y esto le permitiría almacenar primos de nueve dígitos y algunos primos de diez dígitos.

En general, para codificar un primo con valor numérico $N$ de este modo, la propia codificación será de unos $N/\ln(N).$ Esto significa que para codificar un primo con doce dígitos decimales la codificación será será de $10^{11}/\ln(10^{11}) \approx 3.9\times10^9$ al menos eso es, diez dígitos o más. La codificación de un primo grande de doce dígitos se aproximaría más a $10^{11}/\ln(10^{11}) \approx 3.6\times10^{10},$ que tiene once dígitos.

Para codificar primos de hasta veinte dígitos utilizando este esquema, la mayoría de las números después de la codificación serían mayores que $10^{19}/\ln(10^{19}) \approx 2.2\times10^{17},$ un número de dieciocho dígitos.

En resumen, a menos que quiera limitarse a determinadas clases de primos (almacenar sólo los primos de Mersenne, por ejemplo), no vas a va a ser capaz de reducir el espacio de almacenamiento requerido mucho por alguna función inteligente que codifique los números primos utilizando valores numéricos más pequeños.

Lo que usted puede hacer es elegir una representación numérica que almacene números grandes en menos bytes de memoria. SQLite 3 proporciona el tipo de dato INTEGER que almacena un entero con signo de ocho bytes con un valor máximo de $9\times10^{18}.$ Eso cubre (aproximadamente) la primera $2\times10^{17}$ primos. ¿Su script de búsqueda de números primos buscará primos más allá de eso?

Answer 3

Si los genera secuencialmente una forma estándar es almacenar la diferencia entre primos consecutivos.

Esto puede hacerse mucho más compacto (lo hice hace muchos años) utilizando el hecho de que sólo hay 8 primos posibles entre 30n y 30n+29 (son 30n+1, 7, 11, 13, 17, 19, 23, 29).

Almacenando 8 bits en un byte, cada bit dice si ese incremento en particular es primo, los primos en 30n a 30n+29 pueden representarse con un byte.

Tenga en cuenta que 30 = 2x3x5 y 8 = 1x2x4.

Para ir un poco más lejos, desde 210 = 2x3x5x7 y 48 = 1x2x4x6 los primos de 210n+1 a 210n+211 pueden representarse en 48 bits.

Para el caso 30, los incrementos son 2, 6, 4,2, 4, 2, 4, 6.

El algoritmo sería generar inicialmente 2, 3, 5, 7. Entonces, con incrementos de 4,2, 4, 2, 4, 6, 2, 6, comprobar si el bit correspondiente está encendido y, si lo está, emite el valor como un primo.

Para comprobar números hasta $m$ , hay que calcular la primos hasta $\sqrt{m}$ y almacenarlos.