3
$\begingroup$

The question says:

Find the smallest positive integer $n$ so that $\sigma(x)=n$ has no solution, exactly two solutions, exactly three solutions.

I could not come up with a good way to solve this question other that trial and error. But I am questioning this method. Is there any better ideas?

$\endgroup$
10
  • 1
    $\begingroup$ I think brute search is optimal, if a bit tedious. You'll find the answer fairly quickly. $\endgroup$ – lulu Dec 9 '18 at 13:35
  • $\begingroup$ Oh, thanks, my method sounds good though. $\endgroup$ – Maged Saeed Dec 9 '18 at 13:35
  • 1
    $\begingroup$ Absolutely, yes. And you are correct about $2,12$. The third part won't take you as long as you fear. Keep in mind $\sigma_1(n)≥n+1$ with equality only for primes. That makes it easy to truncate your search. $\endgroup$ – lulu Dec 9 '18 at 13:36
  • 1
    $\begingroup$ Correct again. $\,$ $\endgroup$ – lulu Dec 9 '18 at 13:39
  • 1
    $\begingroup$ (+1) for the posted solution, good work. $\endgroup$ – lulu Dec 9 '18 at 13:49
4
$\begingroup$

By trial and error, I have found that the solutions are:

  • $\sigma(x) = 2$ has no solution.
  • $\sigma(x) = 12$ has exactly two solutions that are $6$ and $11$.
  • $\sigma(x) = 24$ has exactly three solutions that are $14,15$ and $23$.
$\endgroup$
1
$\begingroup$

The number of divisors of a natural number $n$ is given by $\sigma(n) = \sum_{k=1}^{\infty}\left ( \left \lfloor \frac{n}{k} \right \rfloor-\left \lfloor \frac{n-1}{k} \right \rfloor \right )$.

This may be useful when expanding the summation.

Note that, when $n$ is a prime number, $\sum_{k=1}^{\infty}\left ( \left \lfloor \frac{n}{k} \right \rfloor-\left \lfloor \frac{n-1}{k} \right \rfloor \right )=2$

$\endgroup$
1
  • $\begingroup$ how did you come up with this formula? $\endgroup$ – Maged Saeed Dec 12 '18 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.