0
$\begingroup$

How many numbers less than 100 have the sum of factors as odd?

Answer is 16

This question and explanation is taken from careerbless.com The link given derives the answer using some properties of number. But, I am trying to solve it in a different way, using a general formula to find sum of the factors of numbers, possibility that may lead to a simple solution.

I have gone through the post in this website where a formula is explained to find sum of the factors of a number. But, it cannot be applied individually for this question (because we need to do it for 1-99 and it takes lot of time).

Is there any shortcut method to derive the answer for this question, possibility using a formula to understand if the sum of the factors is even or odd? Please comment with different approaches for this problem.

$\endgroup$
3
  • $\begingroup$ The question is about the sum of factors. Some of the answers argue with the sum of divisors, but is that really the same? $\endgroup$
    – mvw
    Apr 19, 2016 at 23:57
  • 1
    $\begingroup$ There isn't a short cut but if d is a factor of n then so is n/d so the factors pair up. If n is odd then the factors are odd and add in pairs to evens. So all odd non square have even sums and all odd squares have odd sums. That's half the numbers taken care of. Among the even numbers we just want the ones with an odd number of odd factors. 1 is an odd factor so all powers of 2 will have odd sums. The numbers whose prime factorization have exactly an even number of powers are exactly the numbers we want. With thar they should be easy to list. $\endgroup$
    – fleablood
    Apr 19, 2016 at 23:59
  • $\begingroup$ They are 1,2,4,8,16,32,64,9,18,36,72,25,50,49,98,etc. $\endgroup$
    – fleablood
    Apr 20, 2016 at 0:05

3 Answers 3

4
$\begingroup$

For an odd prime, the sum of divisors of $p^k$ is odd if and only if $k$ is even, so that $p^k$ is an (odd) square.

However, $2^k$ has an odd sum of divisors for any $k \geq 0.$

Your numbers are: $$ 1,9,25,49,81, $$ $$ 2,18,50,98, $$ $$ 4,36, $$ $$ 8,72, $$ $$ 16, $$ $$ 32, $$ $$ 64. $$

I get 16.

$\endgroup$
3
$\begingroup$

The sum-of-divisors function $\sigma$ is multiplicative, with $\sigma(p^m) = 1 + p + \ldots + p^m$ for a prime $p$. In particular, $\sigma(2^m)$ is always odd, while for an odd prime $p$, $\sigma(p^m)$ is odd if and only if $m$ is even. So $\sigma(x)$ is odd if and only if $x$ is of the form $2^k y^2$ where $y$ is odd.

EDIT: The numbers such that $\sigma(n)$ is odd form OEIS sequence A028982. The number of $x \le n$ such that $\sigma(x)$ is odd is OEIS sequence A071860.

$\endgroup$
0
$\begingroup$

Let's consider a few cases: $n$ is even/odd and $n$ is an odd square or not.

  • Suppose that $n$ is odd and is not a square. Then, each of the factors of $n$ can be paired with one another. More precisely, $a$ is paired with $b$ if $n=ab$. Since $n$ is odd, both $a$ and $b$ are odd, but their sum is even. Therefore, the sum of the factors of $n$ is even.

  • Suppose that $n$ is odd and is a square. Then, we can pair each of the factors of $n$ as above, except for the square root. This leaves several pairs of odd integers, and one integer left over. Therefore, the sum of the factors of $n$ is odd.

  • Suppose that $n$ is even and can be written as $n=2^km$ where $m$ is odd. The odd factors of $n$ are precisely the odd factors of $m$. Therefore, we can use the cases above to determine if the sum is odd or even.

Combining these, the odd squares are: 1, 9, 25, 49, 81. Now, we consider powers of two times these to get: 2, 4, 8, 16, 32, 64, 18, 36, 72, 50, 98. These are the 16 possibilities less than 100

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .