Let F ( x ) be the sum of divisors of a positive integer x . Let p be the number of integers x between 1 and 5 0 0 0 (inclusive) for which F ( x ) is an odd number. Find p .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
It is well-known that F is multiplicative, i.e. F ( a b ) = F ( a ) F ( b ) if a and b are coprime.
If a = 2 k , F ( a ) = 2 k + 1 − 1 is odd. If b is odd, then every divisor of b is odd, so F ( b ) is odd if and only if the number of divisors of b is odd, which happens if and only if b is a square.
Since every positive integer can be written (uniquely) as a power of 2 times an odd number, we see that F ( x ) is odd if and only if x is a power of 2 times an odd square.
It's trivial (but tedious) to count the number of such x less than or equal to 5 0 0 0 . There are 1 2 0 of them.
Did it in the same way :)
Problem Loading...
Note Loading...
Set Loading...
Same way as Patrick. We look for numbers of the form x = 2 p q 2 , where p is a non-negative integer and q is odd.
For any given p , the number of values for q is n p = ⎢ ⎢ ⎢ ⎢ ⎡ 2 ⌊ 2 p 5 0 0 0 ⌋ ⎥ ⎥ ⎥ ⎥ ⎤ . Thus we have the following: p 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 n p 3 5 2 5 1 8 1 3 9 6 4 3 2 2 1 1 1
For example, for p = 7 we have the values x = 2 7 ⋅ 1 2 = 1 2 8 ; x = 2 7 ⋅ 3 2 = 1 1 5 2 ; x = 2 7 ⋅ 5 2 = 3 2 0 0 ; their sums of divisors are 255, 3315, and 7905, respectively.
Adding the numbers in the second column we find a total of 120.