Cuántos enteros, de dividir un número que implica sólo tres no-cero dígitos?

Question

Sólo para ser concretos, considerar los dígitos a ser binario. Hasse mostraron que entre todos los números primos, sólo una fracción de $17/24 < 1$ dividir un número de la forma $2^n+1$. Como resultado, los enteros que dividen un número con sólo dos dígitos cero cero densidad.

Por otro lado, desde la $A + A = \mathbb{F}_p$ para un conjunto típico $A \subset \mathbb{F}_p$ de cardinalidad, dicen, $> p/\log{p}$ (y mucho más que eso), y porque en la GRH y con una probabilidad de $1$ hay al menos tantos poderes de $2$ mod $p$, se espera un total de densidad de los números primos para dividir un número de la forma $2^m+2^n+1$. [Añadido: Como se muestra por Skalba en la referencia proporcionada por el "llamado amigo Don," podemos demostrar que esto es cierto para todos los números primos $p \gg_{\epsilon} 0$ tener $r := \mathrm{ord}_p^{\times}2 > p^{\frac{3}{4}+\epsilon}$: considere la posibilidad de Weil obligado para la curva de Fermat de grado $(p-1)/r$. Esto se aplica también a la liga pregunta. ]

Así parecería legítimo preguntar si la probabilidad podría ser positivo para un entero aleatorio tener un multple compuesta de sólo tres no-cero dígitos. Tenga en cuenta que $2^k-1$ no tiene esta propiedad para $k > 3$ (todos sus múltiplos tienen suma de dígitos exceding $ck$), y de esta familia ya proporciona un conjunto infinito de pares de co-primer enteros sin la propiedad.

Sin embargo, pensé que sería difícil creer que un entero aleatorio, con probabilidad positiva, tendrá un múltiplo con delimitada suma de dígitos. Hay una (mejor) heurístico para el número esperado hasta una enlazado $X$ de los enteros positivos de tener un múltiplo de la forma $2^m+2^n+1$? En el extremo opuesto, no la mayoría de las $N$ requieren, para todos sus múltiplos, como muchos como $(1+o(1))\frac{\log{N}}{2\log{2}}$ binario? ¿

Answer 1

Para un entero $n$, llamar a un divisor primo $p$ bueno, si el multiplicativo orden de $2$ modulo $p$ supera $p^{2/5}$, $p^2\nmid n$, y $(p-1, \varphi(n/p))<p^{1/5}$. Si $p$ es un buen divisor primo de $n$, entonces la multiplicación el orden de $2^{\varphi(n/p)}$ es $>p^{1/5}$, por la suma-producto de los resultados de Bourgain existe alguna $k$, tal que para cualquier $a$ existen enteros $e_{1,p}, \ldots, e_{k,p}$, de tal manera que $2^{e_{1,p}\varphi(n/p)}+\dots+2^{e_{k,p}\varphi(n/p)}\equiv a\pmod{p}$. Poner $e_i=\sum_p e_{i,p}$, la suma se toma sobre todos los buenos primos divisores de $n$. A continuación, $e_i\equiv e_{i,p}\pmod{p-1}$ para el bien de todos $p$, lo $2^{e_1}+\dots+2^{e_k}\equiv a\pmod{\prod p}$. Si $p$ es malo,$2^{e_i}\equiv 1\pmod{p}$. Llegamos a la conclusión de que para un determinado valor de $k$ la $k$veces la suma de la multiplicación subgrupo generado por 2 contiene una completa coset del subgrupo de $(\mathbb{Z}/n\mathbb{Z}, +)$ que es isomorfo a $(\mathbb{Z}/P\mathbb{Z}, +)$ donde $P$ es producto de la buena primos divisores de $n$.

Siguiente nos da una cota superior para el promedio del producto de las malas primer divisores. Dado que el número de números primos tales que 2 tiene la pequeña orden es pequeño, y casi todos los números enteros son casi squarefree, la única parte relevante es la condición en la $(p-1, \varphi(n/p))$. Para un primer $p$ el número de $n\leq x$ tal que $n$ ha $<2\log\log x$ primer divisores y $p$ es una mala divisor primo de $n$ es en la mayoría de los $$ \underset{d>p^{1/(10\log\log x)}}{\sum_{d|p-1}}\underset{p\neq q}{\sum_{d|q-1}}\#\{n\leq x: pq|n\} \ll \underset{d>p^{1/(10\log\log x)}}{\sum_{d|p-1}} \frac{x\log\log x}{dp^{1-\epsilon}} \ll \frac{xd(p-1)\log\log x}{p^{1+1/(12\log\log x)}} $$ Si $p>e^{40(\log\log x)(\log\log\log x)}$, esto se convierte en $\ll\frac{xd(p-1)}{p\log^3 p}$. La suma de $p$ converge, por lo tanto nos encontramos con que casi todos los $n\leq x$ no tienen mala divisor primo $p>e^{40(\log\log x)(\log\log\log x)}$.

Sin tener en cuenta una serie de densidad de 0, el promedio del logaritmo del producto de la mala primos divisores de $n$ es mayor que el promedio del logaritmo del producto de las pequeñas primer disivors, que es $$ \ll \sum_{p\leq e^{40(\log\log x)(\log\log\log x)}} \frac{\log p}{p} \ll \log\log x\log\log\log x $$

Llegamos a la conclusión de que hay una constante $k$, de tal manera que para casi todos los $n$ tiene un divisor $d<(\log\log n)^2$, de tal manera que el $k$veces la suma de las subgrupo generado por 2 cubre modulo $n$ la progresión aritmética $k\pmod{d}$. Para tal $n$ cada entero en el intervalo de $[1, d]$ puede ser escrito como la suma de $\log d\ll\log\log\log n$ potencias de 2, por lo tanto, para casi todos los $n$ todos los residuos clases modulo $n$ puede ser escrito como la suma de $\ll\log\log\log n$ potencias de 2. En particular, en casi todos los $n$ dividir un número con la suma de los dígitos $\ll\log\log\log n$.