Encuentre el número de $x$ tal que $\sigma_1(x)=n$ , $n$ es un número entero positivo dado

Question

$\sigma_1(x)$ denota la suma del divisor positivo del entero $x$ . $\sigma_1(x)=\sum_{d\mid x}d$ .

Para un número entero positivo $x=\prod_{i=1}^k p_i^{\alpha_i}$ tenemos $\sigma_1(x)=\prod_{i=1}^k\dfrac{p_i^{\alpha_{i}+1}-1}{p_i-1}$ . Por lo tanto, me planteé enumerar todas las posibles $\dfrac{p_i^{\alpha_{i}+1}-1}{p_i-1}$ que puede dividir exactamente $n$ . Escribí un programa que calcula $F(n,p_i)$ - el número de $x$ cuyo factor primo mínimo es superior a $p_i$ - mediante recursión, y funciona bien cuando $n\le 10^{12}$ . Sin embargo, no me aporta más conocimientos sobre mi problema, y tampoco puedo averiguar su complejidad temporal.

Parece que la respuesta es menos que $\sqrt{n}$ pero no tengo ni idea para demostrarlo. ¿Alguien sabe si es cierto o no? ¿O existe algún algoritmo eficiente para este problema?

Editar
Lo explicaré más claramente: ahora quiero deicir si el número de soluciones es menor que $\sqrt{n}$ (o tal vez $O(\sqrt{n})$ ). Creo que es cierto, pero no puedo dar una prueba.

Answer 1

Comentario: Utilizo algunos resultados en mi respuesta a esta pregunta(pregunta /3597960/ecuación $\sigma(n)=\sigma(n+1)$ ) de Peter. Por ejemplo los números $x=33, 35, 47$ tienen $\sigma(x)=48$ y tenemos $3<\sqrt {48}=6.9..$ . Otro ejemplo $x=71, 46, 51, 55$ tienen $\sigma 72$ . En este modelo sencillo tenemos:

$\sigma(x)=p+q+pq+1=(p+1)(q+1)\space\space\space\space\space\space (1)$

Por ejemplo, para $\sigma(48)$ que tenemos:

$48=(0+1)(47+1)$ que da $(p, q)=(0, 47)$

$48= (3+1)(11+1)$ lo que da $(p, q)=(3, 11)$

$48=(5+1)(7+1)$ lo que da $(p, q)=(5, 7)$

Esto es para $\sigma(48)$ tenemos tres números 33, 35 y 47.O para $\sigma(72)$ tenemos cuatro números. Claramente $3<\sqrt {48}=7.6...$ y $4<\sqrt{72}=8.4...$ .

Ahora supongamos que tenemos un número como $x=48\times 72$ por lo que el número de soluciones para $\sigma(48\times 72=3456$ es como mínimo $3\times 4=12$ . Probablemente podamos construir más de 12 ecuaciones como (1) a partir de $3456$ y encontrar más soluciones. Esta podría ser la base de un algoritmo más sencillo para hallar el número de soluciones. Es evidente que un gran número puede ser escrito como un producto de numerosos factores diferentes su número de solución ya se encuentra y encontrar el número de todas las soluciones.

Actualización: para responder a tu pregunta en el comentario, tenemos que comprobar todos los primos menores que $3556/3=1152$ por ejemplo podemos encontrar:

$3456=(2+1)(1151+1)\Rightarrow x=2\times 1151=2302$

$3456=(3+1)(863+1)\Rightarrow x= 3\times 863=2589$

$3456=(7+1)(431+1) \Rightarrow x=7\times 431=3017$

También $x=(17\times 191=3247),(23\times 143= 3289),(31\times 107=3317),(71\times 47= 3337)$

son algunas soluciones más.