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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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