|
I took a swing at it and I did 2 problems lol. One for the morning and one for the afternoon. It's really cool and hard.
That was some epic 6 hour battle hahaha!!
Anyways the last problem is pretty hard, I couldn't do it so if anyone want to have a go at it! please! 
We have a sequence:
a0, a1, ..., a2009
a0 = 0, always
ai for i>=1 has to be either one of these:
ai = 2^k + aj for any non-negative integer k, and for any aj such that j<i
or
ai = aj mod ak, for j, k < i (doesn't matter if j<k or k<j)
a2009 = n, always. n is ANY positive integer.
so to rephrase the problem, in case it's not clear or it might help you understand it better:
if we start with 0 on a0, how can we make any positive integer n in 2009 steps, filling a0, then a1, a2, ... finally ending with n at a2009 where each time we try to fill some ai we must obey one out of these 2 rules:
1) ai is a sum of 2^k and aj for some aj occuring before ai
or
2) ai is a mod of ak and aj, where ak and aj occurs before ai (does not matter if ak occurs before or after aj)
How to do it?! I get this feeling we'll eventually run out of usable bits as 2^k can only add some 1 bit of information per iteration, I just dunno haha. This procedure must be made in constant and not linear time since 2009 is just some fancy cap. I feel that you should hit your target goal n say, at the 10th step then just repeat n over and over as n mod some large number.
Anyways take a swing at it!!
edit:
by mod I meant the element in the modulo class, i.e. b mod c is an element of {0, 1, ..., c-1}
|
|
|
cant you just say
a0 = 0
a1 = 2^0 + a0 = 1
a2 = 2^1 + a0 = 2
a3 = 2^1 + a1= 3
a4 = 2^2 + a0 = 4
a5 = 2^2 + a1 = 5
Like that you can make any number you want once you reach your number you can just ceep repeating the samething. in example if n were 5 you would ceep saying
an = 2^2 + a1
|
|
|
|
|
I've been looking around for interesting maths based problem solving sites and figured you guys might have some suggestions. Currently I'm slowly working through projecteuler.net
|
On December 06 2009 22:41 Marradron wrote:
cant you just say
a0 = 0
a1 = 2^0 + a0 = 1
a2 = 2^1 + a0 = 2
a3 = 2^1 + a1= 3
a4 = 2^2 + a0 = 4
a5 = 2^2 + a1 = 5
Like that you can make any number you want once you reach your number you can just ceep repeating the samething. in example if n were 5 you would ceep saying
an = 2^2 + a1
Surely that process only works for n<=2009
|
Umm, either I haven't read your question correctly or you haven't got the right one, but how about:
a0 = 0
a1 = 2^0+a0 = 1
a2 = 2^1 + a0 = 2
a3 = a4 = ... = a2008 = 2^1+a0 = 2 (you could make these any number you want really)
If n is odd, then n = 1 mod 2 = a1 mod a2, so a2009 can be n.
If n is even, then n = 0 mod 2 = a0 mod a2, so a2009 can be n.
Edit: I think there was a misunderstanding: when the OP says ai = aj mod ak, he doesn't mean ai is congruent to aj mod ak, but that ai = aj % ak, or in other words that ai is the remainder when aj is divided by ak.
|
I did 4 problems but I didn't really try this one.. it sounded way too hard lol. What exactly are you trying to figure out? which values of n are possible? or whether given an n if it's possible to do it.
|
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.
|
On December 06 2009 22:56 Ludrik wrote:
I've been looking around for interesting maths based problem solving sites and figured you guys might have some suggestions. Currently I'm slowly working through projecteuler.net
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.
|
|
|
I did not take the test, I am just using what I think the OP means.
|
On December 07 2009 01:44 Hamster1800 wrote:
I did not take the test, I am just using what I think the OP means.
Sorry mixed you up with someone else in the thread. Could you elucidate to me how you got a7? 2^(m*r) % 2^m +3 doesn't seem to equal 3^r for many values of m and r (I made sure m >> r too), though it's true for some of them.
|
On December 07 2009 01:14 searcher wrote:
a series a0...a2008 such that a2009 can be any n
Such a series is impossible to construct, so it is obvious that this wasn't the question. You can't construct larger numbers with the mod operation and you certainly can't create every n in N using just 2^k+c with a finite choice of c and for any k.
|
On December 07 2009 02:02 searcher wrote:Show nested quote +On December 07 2009 01:44 Hamster1800 wrote:
I did not take the test, I am just using what I think the OP means. Sorry mixed you up with someone else in the thread. Could you elucidate to me how you got a7? 2^(m*r) % 2^m +3 doesn't seem to equal 3^r for many values of m and r (I made sure m >> r too), though it's true for some of them.
Oh you are right, it is (-3)^r (+2^m if need be)....Just take r to be even. Unfortunately, there's still a problem in a_6. I'll look into it later when I have more time, but someone else can probably fix it before then.
|
On December 07 2009 02:10 Klockan3 wrote:Show nested quote +On December 07 2009 01:14 searcher wrote:
a series a0...a2008 such that a2009 can be any n Such a series is impossible to construct, so it is obvious that this wasn't the question.
Not if you used my original interpretation of what the OP meant by "ai = aj mod ak", which I took to be "ai is congruent to aj modulo ak". Since I have realized that my interpretation is most likely wrong (otherwise my trivial solution above would be correct) I should probably remove that comment.
|
On December 07 2009 02:11 Hamster1800 wrote:Show nested quote +On December 07 2009 02:02 searcher wrote:On December 07 2009 01:44 Hamster1800 wrote:
I did not take the test, I am just using what I think the OP means. Sorry mixed you up with someone else in the thread. Could you elucidate to me how you got a7? 2^(m*r) % 2^m +3 doesn't seem to equal 3^r for many values of m and r (I made sure m >> r too), though it's true for some of them. Oh you are right, it is (-3)^r (+2^m if need be)....Just take r to be even. Unfortunately, there's still a problem in a_6. I'll look into it later when I have more time, but someone else can probably fix it before then.
Do you use the % for a modulus operation? Like 23%9=5?
Then at least I would get 2^(m*r)%2^m+3 =(2^m)+3*(1-2^r) if m>>r.
|
On December 07 2009 02:19 Klockan3 wrote:Show nested quote +On December 07 2009 02:11 Hamster1800 wrote:On December 07 2009 02:02 searcher wrote:On December 07 2009 01:44 Hamster1800 wrote:
I did not take the test, I am just using what I think the OP means. Sorry mixed you up with someone else in the thread. Could you elucidate to me how you got a7? 2^(m*r) % 2^m +3 doesn't seem to equal 3^r for many values of m and r (I made sure m >> r too), though it's true for some of them. Oh you are right, it is (-3)^r (+2^m if need be)....Just take r to be even. Unfortunately, there's still a problem in a_6. I'll look into it later when I have more time, but someone else can probably fix it before then. Do you use the % for a modulus operation? Like 23%9=5? Then at least I would get 2^(m*r)%2^m+3 =(2^m)+3*(1-2^r) if m>>r.
2^(m*r) = (2^m)^r = (-3)^r mod (2^m+3). What you have is 2^(m+r).
To fix the other part, we were looking at 2^(m*l+k). If l is even, we're fine since (-3)^l = 3^l. If l is odd, we'll break it into two steps: 2^(m*(l-1) + k) and then 2^(m*(l-1) + k + 1) + 2^(m*(l-1) + k) = 3*2^(m*(l-1)+k), which will be congruent to 3*((-3)^(l-1)*2^k) = 3^l * 2^k.
|
On December 06 2009 23:14 searcher wrote:
Umm, either I haven't read your question correctly or you haven't got the right one, but how about:
a0 = 0
a1 = 2^0+a0 = 1
a2 = 2^1 + a0 = 2
a3 = a4 = ... = a2008 = 2^1+a0 = 2 (you could make these any number you want really)
If n is odd, then n = 1 mod 2 = a1 mod a2, so a2009 can be n.
If n is even, then n = 0 mod 2 = a0 mod a2, so a2009 can be n.
Edit: I think there was a misunderstanding: when the OP says ai = aj mod ak, he doesn't mean ai is congruent to aj mod ak, but that ai = aj % ak, or in other words that ai is the remainder when aj is divided by ak.
the latter is what I meant.
|
I'm pretty there's an upper bounds on what this sequence can generate. It would be extremely large, but it's there.
|
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
|
this thread hurts my head
|
On December 07 2009 00:40 Commodore wrote:Show nested quote +On December 06 2009 22:56 Ludrik wrote:
I've been looking around for interesting maths based problem solving sites and figured you guys might have some suggestions. Currently I'm slowly working through projecteuler.net Old Putnam problems are available http://www.unl.edu/amc/a-activities/a7-problems/putnamindex.shtmlI 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?
|
On December 07 2009 04:20 evanthebouncy! wrote:Show nested quote +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
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)
|
On December 07 2009 04:32 datscilly wrote:Show nested quote +On December 07 2009 04:20 evanthebouncy! wrote: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 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.
|
On December 07 2009 04:25 ForTheSwarm wrote:Show nested quote +On December 07 2009 00:40 Commodore wrote:On December 06 2009 22:56 Ludrik wrote:
I've been looking around for interesting maths based problem solving sites and figured you guys might have some suggestions. Currently I'm slowly working through projecteuler.net Old Putnam problems are available http://www.unl.edu/amc/a-activities/a7-problems/putnamindex.shtmlI 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?
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?
|
Might be a good time for you to put your genius mind to use and solve the problem for us, Klockan3? Now that you have the proper wording, the solution should trivially follow from the definitions.
|
I took it: pretty fun, even though I only got two of them. By chance, this was one of the ones I (think I) got. Hamster's answer looks more or less like it, but all that dense terminology and symbolism makes my eyes hurt to look at, so I'll just post an example of how it works, which is probably easier to read, albeit less formal.
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.
|
|
|
|
|
|
EPT
Starcraft has become my nerd activity of choice.
