¿Los números primos, expresados en binario, tienen más bits "aleatorios" por término medio que los números naturales?

Question

En mis proyectos de programación, a veces elijo primos grandes cuando quiero bits algo "aleatorios", por ejemplo, para el hashing o la ofuscación trivial mediante XOR o la mutiplicación modular. Mi sensación intuitiva es que los primos en binario son un poco más "aleatorios", pero no estoy seguro de que la realidad lo confirme.

Así que un par de preguntas sobre las que tenía curiosidad:

1. Después de despojarse de la parte delantera y trasera $1$ es la probabilidad de un $1$ en los dígitos binarios restantes de un primo muy diferente al $0.5$ que uno supondría para $\Bbb N$ ¿en general?

2. La "difusión" o distribución de los bits después de la $1$ más "aleatorio" en los primos que en $\Bbb N$ ? No estoy seguro de la métrica estadística que hay que preguntar aquí, así que pido disculpas si la pregunta es vaga; intuitivamente me pregunto si los bits "distribuidos aleatoriamente" como $10010111$ en lugar de $11110000$ son más comunes en los primos.

Si sirve de ayuda, la pregunta podría limitarse a las representaciones de enteros habituales en los ordenadores, por ejemplo, sin signo de 64 bits: $0 \le x \lt 2^{64}$ .

Answer 1

Bien, acabo de escribir un programa rápido para calcular las estadísticas de recuento de bits para los primos y los no primos (compuestos), para intentar resolverlo empíricamente. Usted puede ver el código C++ aquí . Utilicé el método de la Criba de Eratóstenes para generar primos, por lo que se vuelve exponencialmente más lento a medida que aumenta el límite superior, pero para los enteros de 32 bits sólo tardó unos 2 minutos.

Para la pregunta 1, simplemente conté el porcentaje de bits internos que eran 1 (los bits internos son los que quedan después de quitar el 1 inicial y el bit final).

Para la pregunta nº 2 decidí medir el número de "transiciones" de $0 \rightarrow 1$ y $1 \rightarrow 0$ de todas las transiciones posibles en los bits internos. Así que $111000$ tiene 1 de 3 transiciones posibles, para un 33%, y $110100$ tiene 3 de 3 para el 100%.

Aquí están los resultados de las ejecuciones para los enteros sin signo de 8, 16 y 32 bits:

From 4 .. 255:  55 primes, 197 composites.

After stripping leading & trailing binary digits:

Primes had     51.3636% 1's.
Composites had 49.6193% 1's.
Primes had     49.1212% of all possible 0<->1 transitions.
Composites had 49.2301% of all possible 0<->1 transitions.

From 4 .. 65535:  6549 primes, 58983 composites.

Averages after stripping leading & trailing binary digits:

Primes had     49.8745% 1's.
Composites had 50.0139% 1's.
Primes had     49.9531% of all possible 0<->1 transitions.
Composites had 50.0018% of all possible 0<->1 transitions.

From 4 .. 4294967295:  203280748 primes, 4091686544 composites.

Averages after stripping leading & trailing binary digits:

Primes had     49.9719% 1's.
Composites had 50.0014% 1's.
Primes had     49.9974% of all possible 0<->1 transitions.
Composites had 50.0001% of all possible 0<->1 transitions.

Así que, por lo que parece, mi intuición es errónea: no parece haber diferencias significativas ni en los recuentos de 1 ni en la "aleatoriedad" entre los números primos y los compuestos, al menos con estas medidas y rangos concretos.