ODD Factos

[sourabh33]

How many positive integers less than 100 have exactly four odd factors but no even factors?

A. 14
B. 15
C. 16
D. 17
E. 18

Source: 800Score

[SoCan]

I actually get 19. If the question means 4 DIFFERENT odd factors, then I get 16.

I'm sure there's a more elegant solution, but I didn't see it right off the bat, so with a 2 minute limit in mind (this ended taking me around 2:30), I went about it like this:

- As with any number, two factors are going to be 1 and itself. Since we need EXACTLY four odd factors, we're looking for odd prime number pairings whose product is less than 100 (that is, we're looking for numbers N whose factors are {1, prime factor1, prime factor2, N}).
- If one of your prime factors is 3, then the second factor has to be less than 33. Include all the odd prime numbers up to 33 (this is where it helps to have memorized prime numbers). There are 10, including 3 itself (3, 5, 7, 11, 13, 17, 19, 23, 29, 31).
- If one of your prime factors is 5, then the second factor has to be less than 20. Include all the odd prime numbers up to 20, but exclude 3 because the {3,5} pairing has already been counted. There are 6, including 5 itself (5, 7, 11, 13, 17, 19).
- If one of your prime factors is 7, then the second factor has to be less than 14. Include all the odd prime numbers up to 14, but exclude 3 and 5 because the {3,7} and {5,7} pairing has already been counted. There are 3, including 7 itself (7, 11, 13).
- There aren't any other pairings to consider because the next prime number is 11, and 11*11 is greater than 100 (remember we've already counted {3,11}, {5,11} and {7,11}).
- 10+6+3 = 19. This obviously isn't among their answers, so I'm guessing they meant 4 DIFFERENT factors, in which case take out {1,3,3,9}, {1,5,5,25} and {1,7,7,49}.

[sourabh33]

Brilliant!

As you rightly pointed out, the question must be asking for different odd factors. In addition, I agree it is a poorly worded question.

However, you may consider including 27 {1,3,9,27} in addition to the 16 you mentioned. Including 27, the answers should be 17.

[SoCan]

Brilliant!

As you rightly pointed out, the question must be asking for different odd factors. In addition, I agree it is a poorly worded question.

However, you may consider including 27 {1,3,9,27} in addition to the 16 you mentioned. Including 27, the answers should be 17.

You're right, and 17 is indeed the answer for total factors. So just looking at prime pairings isn't the way to go with questions like this one. When trying to figure it out in the time limit, I chose to work with just prime numbers to eliminate the chance I would accidentally count numbers that had more than 4 factors. Would like to see someone show a solution that doesn't use as much brute force.

[Anurag@Gurome]

It is easiest to put down the numbers and count.
They are 15, 21, 27, 33, 35, 39, 51, 55, 57, 65, 69, 77, 85, 87, 91, 93, 95.
The total number is 17.

[SoCan]

It is easiest to put down the numbers and count.

That's no fun

[GMATGuruNY]

How many positive integers less than 100 have exactly four odd factors but no even factors?

A. 14
B. 15
C. 16
D. 17
E. 18

Source: 800Score

To determine the number of factors of an integer:

1. Prime-factorize the integer
2. Add 1 to each exponent
3. Multiply

For example:
24 = 2^3 * 3^1.
Adding 1 to each exponent and multiplying, we determine that 24 has (3+1)*(1+1)= 8 factors.

Thus, for a number to have exactly 4 odd factors, there are 2 cases:

Case 1:
x^1 * y^1, where x and y are distinct odd prime numbers.
Adding 1 to each exponent, we'll get (1+1)*(1+1) = 2*2 = 4 odd factors.
If x=3, y can be 5,7,11,13,17,19,23,29,or 31, yielding 9 numbers.
If x=5, y can be 7,11,13,17,or 19, yielding 5 numbers.
If x=7, y can be 11 or 13, yielding 2 numbers.
Case 1 yields 9+5+2 = 16 numbers.

Case 2:
x^3, where x is an odd prime number.
Adding 1 to the exponent, we'll get 3+1=4 odd factors.
Only 3^3=27 works, since 5^3=125 is too large.
Case 2 yields 1 number.

Total numbers = 16+1 = 17.

The correct answer is D.