Es el conjunto de todos los números que dividen a una función específica de sus factores primos, infinito?

Question

Considere la posibilidad de un número $n$ con la descomposición en factores primos $n=p_1^{k_1} \cdot p_2^{k_2} \dots \cdot p_z^{k_z}$. Definimos una función de $f(n)$$f(n)=(p_1^{k_1+1}-1) \cdot (p_2 ^{k_2 +1}-1) \dots \cdot (p_z^{k_z+1}-1)$. Deje $S$ ser el conjunto que contiene todos los enteros impares $n > 2$ tal que $n|f(n)$. ¿Qué propiedades de $S$ puede deducir? Más específicamente:

Es $S$ finito o infinito? ¿Cuáles son algunos de los números que pueden ser parte de $S$? Hay una forma general de estos números?

Yo realmente no sé por dónde empezar, a todos. Gracias por la ayuda!

Answer 1

Lo principal es que el número de $n$ no puede ser squarefree, como el que tiene un mayor factor primo $r$ que es al menos 2 más grande que cualquier otro factor primordial $p,$ $r$ no dividir con $p_j^2 - 1 = (p_j + 1)(p_j -1).$

De todos modos, yo escribí un poco de la cuadrícula con la mano, y me pongo otro ejemplo con $$ n = 3^4 \cdot 5 \cdot 7 \cdot 11^2 \cdot 19 = 6,517,665. $$ con $$f(n) = 2^{12} \cdot 3^4 \cdot 5^2 \cdot 7 \cdot 11^2 \cdot 19. $$

Tenga en cuenta que su función es un poco peculiar. Su $f(n) = \sigma(n) \cdot (p_1 - 1)(p_2 - 1)\cdots (p_z - 1),$ donde $\sigma(n)$ es la suma de los divisores de a $n.$ ¿de Dónde sacaste este problema?

Otro ejemplo con $$ n = 3^4 \cdot 5^4 \cdot 11^3 \cdot 31 \cdot 61 \cdot 71 = 9,046,757,919,375. $$ con $$f(n) = 2^{20} \cdot 3^5 \cdot 5^4 \cdot 7 \cdot 11^3 \cdot 31 \cdot 61 \cdot 71.$$

EDICIÓN, sábado por la mañana: como una "investigación de operaciones" problema, esto tiene un claro enfoque en términos de un programa de ordenador. No en el mismo orden Raymond usado en su búsqueda exhaustiva, sin embargo, exhaustiva, sin embargo. Corregir uno de los obligados en números primos usado, llame a $B,$, por lo que todos los números primos $p_j < B.$ Revisión de un segundo vinculado $M \geq B^2$ que los límites exponentes como en $p^{k+1} < M.$, por Lo que, para cada una de las $p < B,$ el exponente enlazado $k_p$ $$ k \; \leq \; \; k_p = -1 + \left\lfloor \frac{\log M}{\log p} \right\rfloor $$

A continuación, para cada par $(p,k)$ $p < B$ $p^{k+1} < M,$ realizar estrictamente limitados a un pequeño factorización de $p^{k+1} - 1,$ do la división de juicios solamente por parte de los números primos $q$ que son inferiores a $B.$ El punto aquí es que no nos importa lo que los factores primos podría ser que son más grandes que los $B,$ le haría caso omiso de ellos de todos modos. Por lo que la factorización paso es rápido como un rayo.

Supongamos que hay $b$ impares, números primos hasta el$B.$, por Lo que, para cada par $(p,k),$ guardar una lista o vector, para cada uno de los impares primos $q < B$ la entrada es el exponente $v_q (p^{k+1} - 1).$

La búsqueda es ahora, para cada uno de los impares $p < B,$ elegir un exponente $0 \leq k \leq k_p,$ recuperar la lista de todos los $v_q,$ añadir, lo que resulta en una completa factorización de un número de candidato $n$ y un factorización, de $f(n)$ utilizando sólo los números primos $q < B.$ Esta información es suficiente para decidir si $n | f(n).$ Yo hice algo como esto a mano, primero con $B=20,$ más tarde con $B=75.$ sin Embargo, yo estaba haciendo selecciones por los ojos. No puede ser, hay generalmente, las formas de construir en los criterios de selección para evitar la comprobación de todos los posibles $b$-tuplas. Mirando a Raymond de la lista de nuevo, también me gustaría sugerir que varían de los límites por prime, nos podría permitir a $3^k$ bastante grande $k,$ pero al principio de la con $5$ que puede ser más estrictos con los límites, así como para reducir el final del espacio de búsqueda.

En el caso de que es posible tener dos soluciones que son relativamente primos, el producto de estos dos es una nueva solución. Hasta ahora, sin embargo, parece que el 3 es un factor de todas las soluciones, lo que hace que este comentario probablemente superfluo.

Answer 2

Como complemento a la Voluntad de Jagy del análisis fino, yo sólo voy a añadir el resultado de una búsqueda exhaustiva hasta el$4\cdot 10^9$, seguido por una búsqueda restringida a los números impares $n$ cuyos factores primos $p^k$ compruebe $p\le 73,\ p^k\le 11^3$ el uso de Jagy del método :

$\begin{array} {rl|l} n & \text{factor(n)} & \text{factor(f(n))} \\ \hline \\ 1 & 1 & 1 \\ 819 & 3^2\cdot 7\cdot 13 & 2^8\cdot 3^2\cdot 7\cdot 13 \\ 2941029 & 3^5\cdot 7^2\cdot 13\cdot 19 & 2^{10}\cdot 3^5\cdot 5\cdot 7^2\cdot 13\cdot 19 \\ 6517665 & 3^4\cdot 5\cdot 7\cdot 11^2\cdot 19 & 2^{12}\cdot 3^4\cdot 5^2\cdot 7\cdot 11^2\cdot 19 \\ 14705145 & 3^5\cdot 5\cdot 7^2\cdot 13\cdot 19 & 2^{13}\cdot 3^6\cdot 5\cdot 7^2\cdot 13\cdot 19 \\ 1010238075 & 3^4\cdot 5^2\cdot 7\cdot 11^2\cdot 19\cdot 31 & 2^{17}\cdot 3^4\cdot 5^3\cdot 7\cdot 11^2\cdot 19\cdot 31 \\ 2279297475 & 3^5\cdot 5^2\cdot 7^2\cdot 13\cdot 19\cdot 31 & 2^{18}\cdot 3^6\cdot 5^2\cdot 7^2\cdot 13\cdot 19\cdot 31 \\ \hline \\ 528901498125 & 3^5\cdot 5^4\cdot 7^3\cdot 11\cdot 13\cdot 71 & 2^{20}\cdot 3^5\cdot 5^4\cdot 7^3\cdot 11\cdot 13\cdot 71 \\ 9046757919375 & 3^4\cdot 5^4\cdot 11^3\cdot 31\cdot 61\cdot 71 & 2^{20}\cdot 3^5\cdot 5^4\cdot 7\cdot 11^3\cdot 31\cdot 61\cdot 71 \\ 63327305435625 & 3^4\cdot 5^4\cdot 7\cdot 11^3\cdot 31\cdot 61\cdot 71 & 2^{24}\cdot 3^6\cdot 5^4\cdot 7\cdot 11^3\cdot 31\cdot 61\cdot 71 \\ \end{array}$

(la gente de encontrar otras soluciones deben sentirse libres para editar esta mesa!).

Debo añadir Robert Israel 'Lejos' solución (sin $3$ factor) : $5^{21}\cdot 7^7\cdot 11^4\cdot 23^2\cdot 29\cdot 41\cdot 71\cdot 79\cdot 83\cdot 89\cdot 139\cdot 167\cdot 179\cdot 521\cdot 571\cdot 601\cdot 761\cdot 1201 $ $\cdot 1523\cdot 12207031\cdot 9137\cdot 3221\cdot 5281$

Su secuencia 819,2941029,... aparece desconocido para El On-Line de la Enciclopedia de Secuencias de Enteros™. Usted podría proponer para añadir su secuencia ahí (tal vez con un poco de motivación que nos puede apreciar :-)).

EDIT : no veo clara la regularidad en esta secuencia (a excepción de que sólo relativamente pequeño de los números primos parecen implicados en $n$, y sólo muy pequeños en $\frac{f(n)}n$) y la conjetura de que la secuencia es infinito...

---

ACTUALIZACIÓN: Desde que este problema se dio en una calculadora libre de concurso y a la respuesta de Sarah preguntas que vamos a tratar de encontrar soluciones sin equipo (con más o menos Robert Israel del método). De hecho, la búsqueda de soluciones de este modo será mucho más rápido y más fácil que usar la fuerza bruta.

La primera cosa a observar es que el $f$ define lo que se llama una 'multiplicación de la función" de la teoría de números : $$f(m\cdot n)=f(m)\cdot f(n)\ \ \text{for}\ \ (m,n)=1$$

Esto implica que sólo nos hará falta para examinar $f(p^k)$ $p$ el primer y el $k\in \mathbb{N}$. Para guardar algún lugar voy a reemplazar el $f$ función de la función de $F$ obtenido por la eliminación de los poderes de la $2$ y hacer una pequeña tabla de $F(p^k)$ para valores pequeños de a $p$ $k$ (la primera cosa a hacer cuando no sabes qué hacer!) :

$ \begin{array} {r|ccccc} p & k=1 & 2 & 3 & 4 & 5\\ \hline \\ 3 & 1 & 13 & 5 & 11^2 & 7\cdot 13 \\ 5 & 3 & 31 & 3\cdot 13 & 11\cdot 71 & 3^2\cdot 7\cdot 31 \\ 7 & 3 & 3^2\cdot 19 & 3\cdot 5^2\\ 11 & 3\cdot 5 \\ 13 & 3\cdot 7 \\ 17 & 3^2 \\ 19 & 3^2\cdot 5 \\ \end{array} $

$F(3^1)=\frac{3^2-1}8=1$ no se ven interesantes (hemos perdido la inicial $3$ y no tiene nada)
$F(3^2)=\frac{3^3-1}2=13$ le parece más interesante, así que vamos a buscar (no en todos inspirados por el ordenado de la tabla de arriba...)

• $F(13)=\frac{168}8=3\cdot 7$ ($3$ y un nuevo primer $7$) así que vamos a buscar :

• $F(7)=3$ y tenemos nuestra primera solución :

  $F(3^2\cdot 7\cdot 13)= 3^2\cdot 7 \cdot 13$

Vamos a intentarlo de nuevo con el segundo valor interesante de la tabla :
$F(3^3)=5$ , por lo que vamos a buscar $F(5)$ :

• $F(5)= 3 \cdots$ no lo suficientemente $3$ a continuar... Siguiente intento :

$F(3^4)=11^2$

• $F(11^2)=5\cdot 7\cdot 19\\ $ llegamos $F(5)=F(7)=3$, por lo que vamos a buscar

• $F(19)= 3^2\cdot 5$

  y encontramos nuestra segunda solución :

  $F(3^4\cdot 5\cdot 7\cdot 11^2\cdot 19)=3^4\cdot 5\cdot 7\cdot 11^2\cdot 19$

Voy a dejar de buscar otras soluciones también!