EPTAnyone took putnam math contest today? - Page 2
| Blogs > evanthebouncy! |
|
stoned_rabbit
United States324 Posts
| ||
|
evanthebouncy!
United States12816 Posts
On December 07 2009 00:29 Hamster1800 wrote: Okay...I think I've got it. First let's notice that 2 is a generator modulo 3^r for all r. That is, the set of residues of 2^k mod 3^r over all k are all of the residues relatively prime to 3^r. This can be shown because 2 is a generator mod 9, and then the standard primitive root lifting argument shows it for all r > 2. Therefore, we know that if 3^r >> n, we can write n as the remainder of 2^k * 3^l mod 3^r for some k and l (let 2^k = n mod 3^r and l be the number of 3s dividing n). All we then need to show are that we can construct 2^k * 3^l and 3^r in a constant number of steps. We have a_0 = 0. Let a_1 = 2^m for m >> r, k, and l, a_2 = 2^m + 1, and a_3 = 2^m + 3. Now we let a_4 = 2^(m*l + k) and a_5 = 2^(m*r). a_6 = a_4 % a_3 = 2^k * 3^l, and a_7 = a_5 % a_3 = 3^r. Finally a_8 = a_6 % a_7 = (2^k * 3^l) % (3^r) = n. It's easy to then get a_2009 to be equal to n. can we go over "we can write n as the remainder of 2^k * 3^l mod 3^r for some k and l (let 2^k = n mod 3^r and l be the number of 3s dividing n). " this part again? I'm not understanding what's going on >_< I understand that n is definitely in the mod class for 3^r and I understand that 2^k * 3^l can be possibly the same mod class as n but I don't understand how you do it to get 2^k * 3^l to be exactly n still | ||
|
Ganfei
Taiwan1439 Posts
| ||
|
ForTheSwarm
United States556 Posts
On December 07 2009 00:40 Commodore wrote: Old Putnam problems are available http://www.unl.edu/amc/a-activities/a7-problems/putnamindex.shtml I went through some of these while preparing for the Putnam exam. Some of these can be done without anything more than freshman calculus, but many require undergraduate real analysis or abstract algebra. Grad School Math major ftw! Commodore, I'm curious, how did the Putnam go for you? | ||
|
datscilly
United States529 Posts
On December 07 2009 04:20 evanthebouncy! wrote: can we go over "we can write n as the remainder of 2^k * 3^l mod 3^r for some k and l (let 2^k = n mod 3^r and l be the number of 3s dividing n). " this part again? I'm not understanding what's going on >_< I understand that n is definitely in the mod class for 3^r and I understand that 2^k * 3^l can be possibly the same mod class as n but I don't understand how you do it to get 2^k * 3^l to be exactly n still It should be (let 2^k = n mod 3^l and l be the number of 3s dividing n) and is easier to understand if switched (let l be the number of 3s dividing n and 2^k = n mod 3^l) | ||
|
Hamster1800
United States175 Posts
On December 07 2009 04:32 datscilly wrote: It should be and is easier to understand if switched It still needs to be fixed slightly. My apologies. You have to write n = 3^l * b where b is not a multiple of 3. Then we know that (because 2 is a generator mod 3^r) that there is some k such that 2^k = b. These are the k and l you want. I don't have time to prove that 2 is a generator mod 3^r right now. If I get time I'll put that proof here, but it's pretty standard when proving the primitive root theorem. | ||
|
Commodore
United States97 Posts
On December 07 2009 04:25 ForTheSwarm wrote: Grad School Math major ftw! Commodore, I'm curious, how did the Putnam go for you? I scored 11 out of 120 points, which put me in the top 26%. This is one tough exam! You going to take it next year? | ||
|
meaculpa
United States119 Posts
| ||
|
qrs
United States3637 Posts
Just for instance, let's make "n" 500. Lets call j the smallest integer such that 2^j is more than n, so in this case j = 9. a0: 0 a1: 1 (0 + 2^0) a2: 2^j + 1 (a1 + 2^j) = 513 a3: 2^(j+1) = 1024 a4 a3 mod a2 = 2^j - 1 = 511 a5: 2^(j+n-1) = 2^508 = a lot ... a2009 a5 mod a4 = 1 * (j + n - 1 - j - 1) = 500.* Of course for my example of 500 you don't need to do it that way, but the method should work for any number at all. * edit: intuitive demonstration, since I see there was another page of posts discussing this: 512 /512 = 1. 512/511 = 1 remainder 1. 1024/512 = 2. 1024/511 = 2 remainder 2. and so on: with each go-round, the remainder "lags" by one more. Obviously that's not a formal proof, but it should be enough to let anyone see why it's true. Even on the test itself I didn't really do a good job of proving this formally, so I'll probably lose points there. edit 2: On December 07 2009 04:12 stoned_rabbit wrote: I'm pretty there's an upper bounds on what this sequence can generate. It would be extremely large, but it's there. The reason there's no upper bound on what it can generate is that there is no upper bound on what "k" (2^k) can be. | ||
| ||
