ad

MalliKarjuna Reddy

asked 2016-04-15 03:22:24

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

dev

answered 2016-04-19 10:24:44

Ans: $16$

__Case 1: odd numbers less than 100__

Odd numbers do not have any even factor. i.e., every factor of an odd number is odd.

Therefore,

if number of factors of an odd number is odd, sum of its factors is odd $\cdots(1)$

if number of factors of an odd number is even, sum of its factors is even $\cdots(2)$

Every factor has a pair.

[For example: take the number $8$. $(1,8)$ is a pair. $(2,4)$ is another pair. Therefore, number of factors of a number is expected to be even.]

But there is an exception for this. If the number is a perfect square, one number will not have any pair .

[example: take the number $36$. pairs are $(1,36),(2,18),(3,12),(4,9)$. But $6$ is a factor which does not have any pair].

Therefore,

if a number is a perfect square, number of its factors is odd. ...(3)

if a number is not a perfect square, number of factors is even. ...(4)

From $(1),(2),(3),(4)$

If an odd number is a perfect square, sum of factors is odd.

If an odd number is not a perfect square, sum of factors is even.

Therefore, sum of the factors of the following odd numbers will be odd

$1,9,25,49,81$ ($5$ such numbers)**---(A)**

For other odd numbers, sum of the factors will be even.

__Case 2: even numbers less than 100__

We know that an even number can be written as $2^x$ or $2^x×(\text{odd prime factor})^y$ or $2^x×(\text{odd prime factor})^y$ $×(\text{odd prime factor})^z$ etc.

Since powers of $2$ cannot give odd multiples, number of odd factors of the aforesaid numbers will be $1$ or $(y+1)$ or $(y+1)(z+1)$ respectively.

Therefore, powers of each of the odd prime factors must be even*(or zero which is anyway even)* for number of odd factors to be odd.

In this case, sum of odd factors is odd.

sum of even factors is even.

sum of factors = odd + even = odd.

In other cases, number of odd factors will be even and therefore sum of all factors will be even.

[Let's take some examples to understand the above property clearly. Consider the number $18$ which can be written as $2×3^2$ as product of prime factors. Therefore, number of odd factors of $18$ is $(2+1)=3$. Therefore sum of its factors is odd.

Take another number $54$ which can be written as $2×3^3=54$. In this case, number of odd factors is $(3+1)=4$. Therefore sum of its factors is even.]

Using this property, we can easily find out the even numbers whose sum of the factors is odd. Listing them below.

$2^1=2\\

2^1×3^2=18\\

2^1×5^2=50\\

2^1×7^2=98\\

2^2=4\\

2^2×3^2=36\\

2^3=8\\

2^3×3^2=72\\

2^4=16\\

2^5=32\\

2^6=64$

*(other numbers will be out of the given range 1-99 and hence no need to be considered)*

Therefore, 11 such numbers**...(B)**

From (A) and (B),

Count of numbers less than 100 having sum of factors as odd

$=5+11=16$

Odd numbers do not have any even factor. i.e., every factor of an odd number is odd.

Therefore,

if number of factors of an odd number is odd, sum of its factors is odd $\cdots(1)$

if number of factors of an odd number is even, sum of its factors is even $\cdots(2)$

Every factor has a pair.

[For example: take the number $8$. $(1,8)$ is a pair. $(2,4)$ is another pair. Therefore, number of factors of a number is expected to be even.]

But there is an exception for this. If the number is a perfect square, one number will not have any pair .

[example: take the number $36$. pairs are $(1,36),(2,18),(3,12),(4,9)$. But $6$ is a factor which does not have any pair].

Therefore,

if a number is a perfect square, number of its factors is odd. ...(3)

if a number is not a perfect square, number of factors is even. ...(4)

From $(1),(2),(3),(4)$

If an odd number is a perfect square, sum of factors is odd.

If an odd number is not a perfect square, sum of factors is even.

Therefore, sum of the factors of the following odd numbers will be odd

$1,9,25,49,81$ ($5$ such numbers)

For other odd numbers, sum of the factors will be even.

We know that an even number can be written as $2^x$ or $2^x×(\text{odd prime factor})^y$ or $2^x×(\text{odd prime factor})^y$ $×(\text{odd prime factor})^z$ etc.

Since powers of $2$ cannot give odd multiples, number of odd factors of the aforesaid numbers will be $1$ or $(y+1)$ or $(y+1)(z+1)$ respectively.

Therefore, powers of each of the odd prime factors must be even

In this case, sum of odd factors is odd.

sum of even factors is even.

sum of factors = odd + even = odd.

In other cases, number of odd factors will be even and therefore sum of all factors will be even.

[Let's take some examples to understand the above property clearly. Consider the number $18$ which can be written as $2×3^2$ as product of prime factors. Therefore, number of odd factors of $18$ is $(2+1)=3$. Therefore sum of its factors is odd.

Take another number $54$ which can be written as $2×3^3=54$. In this case, number of odd factors is $(3+1)=4$. Therefore sum of its factors is even.]

Using this property, we can easily find out the even numbers whose sum of the factors is odd. Listing them below.

$2^1=2\\

2^1×3^2=18\\

2^1×5^2=50\\

2^1×7^2=98\\

2^2=4\\

2^2×3^2=36\\

2^3=8\\

2^3×3^2=72\\

2^4=16\\

2^5=32\\

2^6=64$

Therefore, 11 such numbers

From (A) and (B),

Count of numbers less than 100 having sum of factors as odd

$=5+11=16$

preview