# Find the number of $x$ such that $\sigma_1(x)=n$, $n$ is a given positive integer

$$\sigma_1(x)$$ denotes the sum of the positive divisor of the integer $$x$$. $$\sigma_1(x)=\sum_{d\mid x}d$$.

For a positive integer $$x=\prod_{i=1}^k p_i^{\alpha_i}$$ we have $$\sigma_1(x)=\prod_{i=1}^k\dfrac{p_i^{\alpha_{i}+1}-1}{p_i-1}$$. Therefore, I considered enumerating all the possible $$\dfrac{p_i^{\alpha_{i}+1}-1}{p_i-1}$$ that can divide exactly $$n$$. I wrote a program that calculates $$F(n,p_i)$$ - the number of $$x$$ whose minimum prime factor is above $$p_i$$ - by recursion, and it works well when $$n\le 10^{12}$$. However it doesn't give me further knowledge about my problem, and I cannot figure out it's time complexity, either.

It seems that the answer is less than $$\sqrt{n}$$, but I have no idea to prove it. Does anyone know whether it's true or not? Or is there any efficient algorithm on this problem?

Edit
Let me explain it more clearly: now I want to deicide whether the number of solutions is less than $$\sqrt{n}$$ (or maybe $$O(\sqrt{n})$$). I believe it's true, but I cannot give a proof.

• So you want an efficient method to determine the number of solutions $\sigma(m)=n$ , where $n$ is a given positive integer and $\sigma(m)$ the divisor-sum-functio, do I understand this right ? Commented Feb 10, 2023 at 13:31
• @Peter yes, that's exactly what I need Commented Feb 10, 2023 at 13:59
• Let's take $n=19160064000$ as an example, the number of solutions is $85349$, which is smaller than $\sqrt{n}=138419.9$ Commented Feb 11, 2023 at 11:01

Comment: I use some results in my answer to this question(question /3597960/equation $$\sigma(n)=\sigma(n+1)$$) by Peter. For example numbers $$x=33, 35, 47$$ have $$\sigma(x)=48$$ and we have $$3<\sqrt {48}=6.9..$$. Another example $$x=71, 46, 51, 55$$ have $$\sigma 72$$. In this simple model we have:

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

For example for $$\sigma(48)$$ we have:

$$48=(0+1)(47+1)$$ which gives $$(p, q)=(0, 47)$$

$$48= (3+1)(11+1)$$, which gives $$(p, q)=(3, 11)$$

$$48=(5+1)(7+1)$$, which gives $$(p, q)=(5, 7)$$

That is for $$\sigma(48)$$ we have three numbers 33, 35 and 47.Or for $$\sigma(72)$$ we have four number. Clearly $$3<\sqrt {48}=7.6...$$ and $$4<\sqrt{72}=8.4...$$.

Now suppose we have a number like $$x=48\times 72$$, so the number of solutions for $$\sigma(48\times 72=3456$$ is at least $$3\times 4=12$$ . We probably can construct more than 12 equations like (1) from $$3456$$ and find more solutions. This could be the base for a simpler algorithm for finding number of solutions. Clearly a large number may be written as a product of numerous different factors their number of solution is already found and find number of all solutions.

Update: to answer your question in comment, we have to check all primes less than $$3556/3=1152$$, for example we can find:

$$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$$

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

are some more solutions.

• Thanks! Could you explain "We probably can construct more..." further? I'm not able to find a quick method. Commented Feb 17, 2023 at 11:05