Why so odd!

Let F ( x ) F(x) be the sum of divisors of a positive integer x x . Let p p be the number of integers x x between 1 1 and 5000 5000 (inclusive) for which F ( x ) F(x) is an odd number. Find p p .


The answer is 120.

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.

2 solutions

Arjen Vreugdenhil
Nov 12, 2015

Same way as Patrick. We look for numbers of the form x = 2 p q 2 x = 2^pq^2 , where p p is a non-negative integer and q q is odd.

For any given p p , the number of values for q q is n p = 5000 2 p 2 . n_p = \left\lceil\frac{\left\lfloor\sqrt{\frac{5000}{2^p}}\right\rfloor}{2}\right\rceil. Thus we have the following: p n p 0 35 1 25 2 18 3 13 4 9 5 6 6 4 7 3 8 2 9 2 10 1 11 1 12 1 \begin{array}{r|r} p & n_p \\ \hline 0 & 35 \\ 1 & 25 \\ 2 & 18 \\ 3 & 13 \\ 4 & 9 \\ 5 & 6 \\ 6 & 4 \\ 7 & 3 \\ 8 & 2 \\ 9 & 2 \\ 10 & 1 \\ 11 & 1 \\ 12 & 1 \\ \hline \end{array}

For example, for p = 7 p = 7 we have the values x = 2 7 1 2 = 128 ; x = 2 7 3 2 = 1152 ; x = 2 7 5 2 = 3200 ; x = 2^7\cdot 1^2 = 128; \ \ \ x = 2^7\cdot 3^2 = 1152; \ \ \ x = 2^7\cdot 5^2 = 3200; their sums of divisors are 255, 3315, and 7905, respectively.

Adding the numbers in the second column we find a total of 120.

Patrick Corn
Sep 24, 2015

It is well-known that F F is multiplicative, i.e. F ( a b ) = F ( a ) F ( b ) F(ab) = F(a)F(b) if a a and b b are coprime.

If a = 2 k a = 2^k , F ( a ) = 2 k + 1 1 F(a) = 2^{k+1}-1 is odd. If b b is odd, then every divisor of b b is odd, so F ( b ) F(b) is odd if and only if the number of divisors of b b is odd, which happens if and only if b b is a square.

Since every positive integer can be written (uniquely) as a power of 2 2 times an odd number, we see that F ( x ) F(x) is odd if and only if x x is a power of 2 2 times an odd square.

It's trivial (but tedious) to count the number of such x x less than or equal to 5000 5000 . There are 120 \fbox{120} of them.

Did it in the same way :)

Zawad Abdullah - 5 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...