wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Sum the Number of Divisors (9/13/2002)
        
(Message started by: william wu on Sep 16^th, 2002, 1:54pm)

Title: Sum the Number of Divisors (9/13/2002)
Post by william wu on Sep 16^th, 2002, 1:54pm

Let c(n) be a function that counts how many positive divisors the positive integer n has, and let

S(n) := summation over d/n { c(d) }

be the sum of the counts c(d) taken over all divisors d of n. For instance, 18 is divisible by 1, 2, 3, 6, 9, and 18, so c(18) = 6. Since c(1) = 1, c(2) = c(3) = 2, c(6) = 4 and c(9) = 3, we find that S(18) = 1+2+2+4+3+6 = 18. Find all roots n of the equation S(n) = n.

Title: Re: Sum the Number of Divisors (9/13/2002)
Post by Pietro K.C. on Sep 17^th, 2002, 10:46pm

This one is tougher than the other two! I'm still not even close, but here are some preliminary results. Let me know your ideas!

First, if n is prime, its divisors are 1 and n, and c(n) = 2. Therefore, S(n) = 3 for n prime, and the only solution of S(n) = n for prime numbers is n = 3.

Before getting on with some more theoretical results, let me just say that I've done some calculations (by hand :P), and the only roots of S(n) = n between 1 and 30 are 1, 3 and 18. Also, S(36) = 36, but I don't intend to check any more numbers for now. I think we can be cleverer.

Let n = p^uq^v...r^w. It is a well-known result that c(n) = (u+1)(v+1)...(w+1). You can see this by noticing that any divisor d of n can have ONLY the same prime factors as n. This means that, for each prime factor p of n (with exponent u), you have u+1 different choices as to how this factor appears in d (including 0, in which case p does not divide d). From elementary combinatorics, the total number of such choices is the product indicated above.

A result that easily follows is that, for two relatively prime numbers a and b, c(ab) = c(a)c(b). This fact, allied with the above formula, can be used to establish that, for n = p^uq^v...r^w,

S(n) = ((u+1)(u+2)/2)*((v+1)(v+2)/2)*...*((w+1)(w+2)/2)

or

S(n) = T_u+1*T_v+1*...*T_w+1,

where T_i is the i-th triangular number. (Give it a try, it's not too hard, and it's instructive!) From this equality it is easy to see that gcd(a,b) = 1 => S(ab) = S(a)S(b).

Now, all I've done so far is solve a few particular cases. For instance, if n is a prime power, say p^k, the above formula gives S(n) = (k+1)(k+2)/2, and if we had that equal to n, the following would result:

(k+1)(k+2) = 2p^k.

Since gcd(k+1, k+2) = 1, one of them must be divisible by p^k, say k+1. Then k+1 = Ap^k, and substituting we have

A(k+2) = 2 <=> A = 1 and k+2 = 2 <=> k = 0 <=> k+1 = 1,

whence p must also be equal to 1, a contradiction. If we had chosen k+2 instead of k+1, we would have

A(k+1) = 2 => A = 2 and k+1 = 1 or A = 1 and k+1 = 2.

The first case gives k = 0 <=> k+2 = 2 = Ap^k = 2p^k <=> p^k = 1 <=> p = 1.

The second case gives k = 1 <=> k+2 = 3 = Ap^k = p^k <=> p = 3, and is consistent with k = 1.

Therefore, the only prime power satisfying S(n) = n is 3.

We can also check the case where n is the product of k distinct primes, all with exponent 1 (i.e. n = p₁...p_k). Here, S(n) = 3^k; therefore, p₁ = 3 and there are no other prime factors to n. That is, k = 1, which means that n = 3. The number 3 sure does appear a lot in this problem!

Well, these are all the concrete results I've got so far. I'll post more if I get more ideas. And please do post your thoughts! This Putnam forum is so quiet.

Title: Re: Sum the Number of Divisors (9/13/2002)
Post by Yournamehere on Sep 18^th, 2002, 1:41am

on 09/17/02 at 22:46:16, Pietro K.C. wrote:

for n = p^uq^v...r^w,

S(n) = ((u+1)(u+2)/2)*((v+1)(v+2)/2)*...*((w+1)(w+2)/2)

or

S(n) = T_u+1*T_v+1*...*T_w+1,

where T_i is the i-th triangular number.

From this, I think the rest falls out. Let me change notation for clarity/generality: let n = p_1^{u_1} * p_2^{u_2} * ... * p_k^{u_k}, and S(n) = T_{u_1+1} * T_{u_2+1} * ... * T_{u_k+1}.

Observe that if n = p_1^{u_1}* m, where p_1 does not divide m, then S(n) = T_{u_1+1} * S(m).

Also note that if n <= S(n), then there must be some prime p_i and corresponding exponent u_i such that p_i^{u_i} <= T_{u_i+1} (if not, then n > S(n)).

Now note

p^u <= T_{u+1} if
p = 2 and u < 4, or
p = 3 and u < 2

(if p>=5, then p^u > T_{u+1} for all u >= 0). So, if n=S(n), then either the exponent of 2 in n must be less than 4, or the exponent of 3 in n must be less than 2. Also, one can show that if both the exponent of 2 and the exponent of 3 are 0, then n = S(n) iff n = 1.(*)

The key observation is that p^x grows much faster than T_x (which is O(x^2)).

Now we split into cases:

Suppose the exponent of 2 is 0 in n; that is, 2 does not divide n, or n = 2^0 * m, where 2 does not divide m. Then S(n) = 1 * S(m), so n=S(n) iff m=S(m). Applying the above reasoning (marked (*)) to m, we must have the exponent of 3 in m being 1; m = 3^1 * d, where neither 2 nor 3 divides d., and S(m) = 3 * S(d). But applying (*) again, d=1. Hence n = 3.

Now suppose the exponent of 2 is 1 in n; n = 2^1 * m, where 2 does not divide m. Then S(n) = 3 * S(m), so if n = S(n), then 3 must divide m. Suppose m = 3^1 * d, and neither 2 nor 3 divide d. Then S(n) = 3 * S(m) = 3 * 3 * S(d), so clearly n != S(n), since 9 divides S(n) but 9 does not divide n. Now suppose m = 3^2 * d. Then S(n) = 3 * 6 * S(d), and n = 2 * 9 * d, so if n = S(n), then d = S(d), and applying (*) we get d = 1. Thus n = 18. Now suppose m = 3^3 * d. Then S(n) = 3 * 10 * S(d) = 30 * S(d), and n = 2 * 27 * d = 54 * d, and, regardless of what d is, S(d) < d (by (*)), so n > S(n). In fact, for all v > 2, 3 * S(3^v) < 2 * 3^v, so if n = 2 * 3^v * d, then S(n) < n.

Continue for when the exponent of 2 is 2 in n; n = 2^2 * m. S(n) = 6 * S(m), so if n = S(n), 3 divides m. n = 2^2 * 3^1 *d doesn't work, since 9 divides S(n) but not n. n = 2^2 * 3^2 * d yields S(n) = 6 * 6 * S(d) = 36 * d, and n = 36 * d, so again d = 1 and we have n = 36. If n = 2^2 * 3^v * d, v > 2, then S(n) < n, as in the previous case.

If n = 2^3 * m = 8*m, then S(n) = 10 * S(m). If 3 does not divide m, then neither 2 nor 3 divide m, so by (*), m = 1, and n != S(n). If m = 3^1 * d, then S(n) = 10 * 3 * S(d) = 30 * S(d), and n = 24 * d. But if d = 5^1 * f, where 5 does not divide f, then S(n) = 30 * 3 * S(f) = 90 S(f), and n = 120 f, so S(n) < n, and similarly for all d = 5^v * f, v > 1.

If the exponent of 3 is 0 in n, and none of the above cases hold, then the exponent of 2 must be at least 4 in n, so by (*), n != S(n).

If the exponent of 3 is 1 in n, and none of the above cases hold, the exponent of 2 is at least 4 in n. Consider n = 2^4 * 3^1 * d = 48 * d; S(n) = 15 * 3 * S(d) = 45 * S(d), so by (*), n > S(n). By similar reasoning as used in the previous cases, if n = 2^v * 3^1 * d, v > 4, then S(n) < n.

Since these are all the possible cases for n = S(n), then we conclude that n = 1 or n = 18 or n = 36 are the only solutions.

I probably could have been a bit clearer in stating the main lemma (*), but it's 1:30 am. :(

The Putnam board will probably be relatively quiet compared to the others, since

1) the questions usually require more knowledge of math, and hence are probably less accessible to the general public, and
2) the questions are hard. For the actual contest, if you only do 2 questions in the alloted 6 hours (with excellent writeup; the above probably would not be considered good), you are pretty much guaranteed a placement in the top 25%.

Title: Re: Sum the Number of Divisors (9/13/2002)
Post by Pietro K.C. on Sep 18^th, 2002, 7:56am

Good work! :D I as well was headed in the compare-exponential-and-quadratic direction, but after realizing that the number of roots was finite (and probably small, too) I got too lazy to do the actual math. :P

I think this is by far the most interesting forum; the others have recently gone too much down the find-out-who-is-who-in-so-many-questions road (though Eric's puzzle forum seems cool). I wish there were new problems more often. Maybe Will won't mind if we contribute a few of our own... :)

By the way, Yournamehere (register, dude!), did you see the problem I posted in the hard section under the title "new puzzle: partitions"? You seem to like mathematics as I do, and I found that an interesting problem. Maybe I should have posted it here.

Title: Re: Sum the Number of Divisors (9/13/2002)
Post by Yournamehere on Sep 19^th, 2002, 12:12pm

I saw the partitions problem, but haven't had time to give it much thought, yet. That problem is fairly "Putnam-like", and might be appropriate to put it here instead.

On the other hand, the problem with the bottle that you posted here doesn't seem very "Putnam-like": not a comment on the quality of the problem itself, but just that it's not something one might expect on the Putnam contest (assuming the contest makers haven't changed the style). Usually Putnam problems are fairly abstract, and have little to do with real-world phenomena. :)