¿Con qué frecuencia (densidad asintótica, es decir) es la revocación de la representación binaria de $7n$ es un múltiplo de $7$?

Question

Si usted revertir los dígitos binarios de un múltiplo de $3$, el resultado es siempre un múltiplo de $3$. El mismo no es cierto para $7$, pero parece ocurrir más a menudo de lo que $\frac{1}{7}$ del tiempo. Para la diversión, voy a llamar a un número $n$ de manera tal que a la inversa de dígitos binarios de $7n$ representa un múltiplo de $7$ "sevenly" número.

Escribí un simple programa en Python para calcular la frecuencia de sevenly números, y después de dejar que se ejecute a una hora de la proporción había sido la disminución de la general, pero no muy constante, y aún tenía que caer por debajo de $0.25$.

Me preguntaba si alguien sabía de cómo determinar la densidad asintótica de sevenly números. Mi intuición me dice que debería ser $\frac{1}{7}$, pero los cálculos que he hecho parece sugerir que no podría.

EDITAR

Mi programa original no decirme qué número era, sólo la proporción, pero corrí durante una hora, por lo que probablemente se metió en los millones. He cambiado el programa, ya que, a continuación, imprimir el número, también. Aquí está ese código:

def brev(n):
    return int("0b"+(bin(n)[::-1])[:-2],2)

n = 1
sevenlies = 0
while True:
    if brev(7*n)%7 == 0:
        sevenlies += 1
    print("%d\t%f"%(n,sevenlies/n))
    n += 1

Answer 1

Aquí está mi razonamiento sobre el por qué de el número de veces que los restos de mod $7$ partido más que de forma aleatoria.

La clave de las cosas, para mí, se que mod $7$, $2^{3m} \equiv 1, 2^{3m+1} \equiv 2, 2^{3m+2} \equiv 4 $.

Por lo tanto, si $m$ es uno menos que el número de bits de $n$, escribir $n = \sum_{k=0}^m b_k 2^k $.

Si $s(n)$ es la valor de $n$ mod $7$ y $d(0, 1, 2) = (1, 2, 4)$, entonces

$s(n) \equiv \sum_{k=0}^m b_k d(k \bmod 3) $

Invertir los bits, definir $r(n) =\sum_{k=0}^m b_{m-k} 2^k =\sum_{k=0}^m b_{k} 2^{m-k} $.

Entonces, mod $7$,

$\begin{array}\\ s(r(n)) &=\sum_{k=0}^m b_{k} 2^{m-k}\\ &\equiv\sum_{k=0}^m b_{k} d(m-k \bmod 3)\\ \end{array} $

así que

$\begin{array}\\ s(r(n))-s(n) &\equiv\sum_{k=0}^m b_{k} (d(m-k \bmod 3)-d(k \bmod 3))\\ \end{array} $

Siempre $d(m-k \bmod 3) =d(k \bmod 3) $, el término es cero. Esto sucede cuando $m-k \equiv k \bmod 3$ o $m \equiv 2k \bmod 3$ o $2m \equiv k \bmod 3$.

Esto sucede alrededor de un tercio del tiempo de modo que, independiente del valor, un tercio de los bits se anulan.

Answer 2

Si la relación converge a un límite, entonces es $1/7$.

Deje $n'$ ser el inverso de a $n$.
Si $n$'s binarias de expansión de la es $\sum_{k=1}^m d_k 2^k$, entonces, modulo $7$, tenemos
$n' = \sum_{k=1}^m d_k 2^{m-k} \equiv \sum_{k=1}^m d_k 2^{m-k} 8^k \equiv 2^m \sum_{k=1}^m d_k 4^k$,
y por lo $n'$ es un múltiplo de a $7$ si y sólo si $\sum_{k=1}^m d_k 4^k \equiv 0$,
lo que significa que $n$'s de la cadena binaria, cuando se lee en base $4$, es un múltiplo de a $7$.

Deje $a_n$ el número de sevenly números entre el$0$$2^n/7$, por lo que el número de $n$-dígitos cadenas binarias que son múltiplos de $7$ base $2$ y base $4$.

$(a_n)_{n \ge 0} = 1,1,1,2,3,5,10,16,28,56,\ldots$

Si dejas $a^{i,j}_n$ el número de $n$-dígitos cadenas que representan, mmodulo $7$, $i$ cuando se lee en base $2$ $j$ cuando se lee en base $4$, usted tiene relaciones de recurrencia $a^{i,j}_{n+1} = a^{4i,2j}_n + a^{4i+3,2j+5}_n$, por lo que si usted pone todos los números en un vector $V_n \in \Bbb R^{49}$ hay una matriz de $M$ tal que $V_{n+1} = M V_n$.

El polinomio característico de a $M$ es
$(x-2)(x^3-1)^4(x^9 - 10x^6 + 24x^3 - 8)^2(x^9 -3x^6 - 4x^3 - 1)^2$

$2$ es su mayor autovalor, y su espacio propio es generado por el uniforme de vectores $(1,1,1,\ldots,1)$, así como el $n \to \infty$, los componentes de $V_n$ equivalen a $\frac 1 {49} 2^n$, y así como $n$ se hace más grande, $a_n = a_n^{0,0} \sim \frac 1 {49} 2^n$ $\frac 17$ de la $\frac 17 2^n$ números nos están mirando.

Answer 3

Tengo la sospecha de que, finalmente, esta proporción va a ir a donde usted intuit debe estar, que es $\frac{1}{7}$, pero que es inicialmente un poco mayor que el, y que va a tomar un buen tiempo para converger a este valor.

No tengo pruebas de esto, pero tengo mis razones:

Primero notemos que para números pequeños, usted tiene un número desproporcionadamente alto de 'sevenly' números: de Hecho, todos los números del 1 al 10 son 'sevenly'!

Segundo, mientras que algo de esto es debido a la naturaleza de la cadena de bits $111$ 7, al mismo tiempo, algunos de esto es la 'coincidencia'. Por ejemplo, 1 es sevenly por una buena razón, porque el reverso de $111$ $111$ sí ... 1 no sería 'sixly", por ejemplo. Pero el 3 es sevenly porque la cadena de bits de 21 (10101) pasa a ser simétrica, y las cadenas de bits de 35 y 49 de pasar a ser de los demás inversa, lo que 5 y 7 sevenly. Y por último, cualquier número de cuya cadena de bits es $1(000^*1)^*$ será sevenly, y 9 es así (y lo son 17, 33, 65, 73 ...). Así que, de nuevo, creo que la alta proporción de sevenly los números al principio es una combinación de $111$ ser simétricas, así como de pura casualidad.

En tercer lugar, si $x$ es sevenly, a continuación, $2x$ será sevenly así, desde la cadena de bits de $7*2x$ supuesto va a ser la cadena de bits de $7x$ con un 0 después de él, y ese extra de 0 se cae cuando la cadena se invierte.

Del mismo modo, si $x$ es uniformemente $8x+1$ es de manera uniforme, ya que la cadena de bits de $8x+1$ es el bitstring para$x$, seguido por $001$ y un poco de reflexión muestra que al multiplicar por $7$ y, a continuación, invertir cantidades a añadir $111$ frente a la inversión de la cadena de bits de $7x$ que ya sabemos representa un múltiplo de $7$, así que la inversión de la cadena de bits de $8x+1$ representa un múltiplo de $7$.

Por lo tanto, debido a que 1 es sevenly, por lo que se 2,4,8,16, etc. Y porque 3 es sevenly, 6, 12, 24, etc. son sevenly así. Y con 5 obtenemos 10, 20, etc. Asimismo, debido a que 1 es sevenly, por lo que es 9, porque 2 es sevenly, por lo que es de 17, porque 3 es sevenly, por lo que es de 25, etc.

En otras palabras, la proporción extremadamente alta de sevenly los números al principio se propaguen a los números más altos a través de estos tipos de conexiones entre el sevenly números.

Sin embargo, esta alta proporción inicial no se propagan a la perfección. Que es, como seguimos multiplicando el sevenly números por 2 para obtener nuevos sevenly números, espacios comienzan a aparecer ( como vemos con 11,13 y 15, que son los primeros que no sevenly números). Así, la proporción va a bajar. A continuación, una vez más, algunos de estos vacíos se llenaron de nuevo por algunos "nuevo" tipo de sevenly número (la pareja de 19 y 23 es un buen ejemplo ... Y así es 27, el cual se asigna a sí mismo) y esto ralentizará la disminución gradual de la proporcionalidad. Lo que puede tardar un buen rato antes de que la proporción de acercamiento $\frac{1}{7}$.

Sin embargo: estoy pensando que si usted comienza con 'lo suficientemente grande' bitstrings, esta desproporción inicial desaparecerá poco a poco, en que si usted tiene una muy grande bitstring para empezar, la resultante bitstring es probable que sea muy grande así, y por lo tanto sería de esperar que el resultado de cadenas de bits a ser más "random" de nuevo, haciendo que la proporción enfoque de $\frac{1}{7}$ nuevo.

Así que: ¿podría tal vez iniciar su programa con un gran número de e.g $n = 1,000,000$? y ver en qué proporción se obtiene a partir de ese punto?

EDITAR

Marty análisis es muy interesante. En mis ojos, lo que demuestra, en particular, es que si usted se centra en cadenas de bits cuya longitud es un múltiplo de 3, y si el último dígito es un 1, entonces si que la cadena de bits representa un múltiplo de 7, entonces es, al menos para los 'pequeños' de cadenas de bits, significativamente más propensos que los $\frac{1}{7}$ que la inversa de cadena de bits es un múltiplo de 7, lo que explica la mayor proporción de sevenly números. Y esto es porque para el tamaño más pequeño de cadenas de bits, es bastante probable que para obtener igual cantidad de 1's en el 3k posiciones como en el 3k+1 posiciones, y en ese caso estamos tratando con un sevenly número. De hecho, nos encontramos exactamente en este caso con la mencionada vinculación de 5 y 7, pero también tenemos tales emparejamientos de 37 y 55, 53 y 59, 45 y 63 años, y el 57 y 69 ... No es de extrañar tenemos tan muchas sevenly números entre los primeros 70 números!

Por otra parte, estos tipos de emparejamientos ocurrirá con una probabilidad de más de $\frac{1}{7}$ durante bastante tiempo. Para cadenas de bits de longitud de 18 años, la probabilidad de obtener tales emparejamientos es de alrededor de 0,25, e incluso para las cadenas de bits de longitud 30 esto ocurre en alrededor del 18% de los casos!

Esto significa que vamos a ver disproportionaly más sevenly números para los números, al menos en el orden de 1.000.000.000, y en combinación con el anterior mencionado efectos de propagación, la proporción se mantiene significativamente por encima de $\frac{1}{7}$ por un largo, largo tiempo, posiblemente en el cuatrillones. Aún así, me atrevo a predecir que, aunque muy persistente, incluso este efecto eventualmente desaparecer.

EDIT 2

OK, yo generado al azar de cadenas de bits de longitud 99 y utiliza Marty método de averiguar si lo que representa una cantidad (que está en el orden de $10^30$!) que es un múltiplo de 7: Simplemente deje $x$ el número de 1's en el 3k+1 posiciones (es decir, el 1, 4, 7, etc. posición de bit), $y$ el número de 1's en el 3k+2 posiciones, y $z$ el número de 1's en la $3k$ posiciones de bits, y el número es divisible entre iff $4x+2y+z$ es divisible por 7. De aquellos que fueron divisible por 7, miré si la inversa cadena de bits representados un número divisible por 7, y en qué proporción. He encontrado ... (redoble de tambor) ... 0.14!

Esta no es una prueba, pero sin duda confirma mi anterior señaló sospechas de que la proporción de hecho, finalmente, ir a $\frac{1}{7}$, pero eso es sólo que para números pequeños, la proporción es superior por las razones ya indicadas.