kitchen table math, the sequel: from the SMO junior exam

Saturday, November 20, 2010

from the SMO junior exam

(The competition is meant for 14 to 16 year olds.)

This was from the 2004 exam:
Find the number of digits in N where N is the product of all positive divisors of 100,000,000. (Note: For any positive integer A, we regard A itself as one of the divisors.)

Another one:
The number A=200420052006...2040 is formed when one puts the consecutive integers from 2004 to 2040 together. What is the remainder when A is divided by 9?


solution discussion for the first one:

Divisors come in pairs -- every divisor x, there must be a divisor n/x, and their product is n. (But if the divisor is a square root of n, then it is the same as the other divisor and it is only counted once.) How many pairs are there?

For n=10 there are two pairs (10-1 5-2), and we note the product is 10^2 = 100.
For n=100 there are five pairs (100-1, 25-4, 20-5, 10-10, 50-2) but one pair is degenerate and the product is 100^4 * 10 (=10^9).
For n=1000, there are eight pairs. Divisor product = 1000^8.
For n=10^8, the script I wrote in Mathematica tells me there are 81 divisors and the divisor product is 325.

The number of divisors for 10^n has an interesting trend, too. It seems to be (n+1)^2.


Allison said...

10^4 is 10000.

Perhaps it is cleaner to show people that the prime factorization of 10^k is
2^k 5^k.

le radical galoisien said...

You can /prove/ that of course, but sometimes I find that knowing the proof is not quite the same as conceptual mastery.

Using mathematica, Length[Divisors[1000]] gives 16 divisors, but there are 25 digits in its product.

Length[Divisors[10000]] ==> 25 divisors

(I wrote a short script to investigate this for any n.)

le radical galoisien said...

interesting. that the sequence of squares alternate from odd and even -- because the square of an odd number is always odd.

but it happens to work out that it makes a formula very convenient, in the case of degenerate pairs.

le radical galoisien said...

For n^k as well.

Length[Divisors[6^7]] = 64 -- that is (7+1)^2.

So this can be generalised for any n, not just n = 10^b.

le radical galoisien said...

unproven, but probably true (?) statements:

If n is prime, then n^k has k+1 divisors.

If n is a square of a prime, then n^k has 2k+1 divisors.

If n has two prime factors (e.g. n=6), then n^k has (k+1)^2 divisors.

if n is a cube of a prime (e.g. 8), then n^k has 3k+1 divisors.

if n has three prime factors, then n^k has (k+1)^3 divisors.

trying to work out the trend (not prove!) for the case to any n.

The prime factorization of the number of divisors for any whole number is interesting.

le radical galoisien said...

sorry if this seems like elementary playing -- I've not been exposed to number theory for many years. It's just something that doesn't come up in the sciences a lot.

Do the mainland Chinese pay a lot of attention to number theory?

Now I had an Indian teacher (Mr M. Ravi) in sec 1, who exposed me to the SMO. Alas, I've not had a math teacher like that since. Sure I've had useful math teachers, but he was a well-published-adult-with-the-curiosity-of-a-child sort of guy. In fact I think he wasn't a regular teacher at ACSI -- he just randomly ambushed me at a school recess one day, sized me up and said I looked like the kind of person who would be curious enough to attend a mysterious session about something mathy at 1 pm on Fridays.

Michael Weiss said...

If n is prime, then n^k has k+1 divisors.

Sure. The divisors are precisely:

1, n, n^2, n^3, n^4, .... , n^k

All you need to know, really, is that any divisor of N can be constructed by choosing a subset of the prime factors of N.

So, for example, if N = (p^a)(q^b), where p and q are both prime, then you can build any divisor by taking "some p's" (where "some" is any number from 0 to a) and "some q's", (where "some" is any number from 0 to b). So there are (a+1) choices of how many p's to take, and (b+1) choices of how many q's to take, which makes (a+1)(b+1) possibile divisors you can build.

Catherine Johnson said...

How come there's nothing in this question about Iceland?

That's what I want to know.