Final Post

So I haven't posted in a while.

I have been so distracted by other things I simply just forgot

So where we left in the problem is proving that x_n = 3k+1 = 2^m somewhere in all sequences. I can do small starting numbers and show that it ends up at 1, but to prove it generally seems insurmountable.

I guess we know that if a number shows up in a previous sequence that contains a one we know that this new sequence also contains a one, because the sequence doesn't depend on the number before that.

I'm stumped. This explains why the problem remains unsolved for everybody.


Oh well. I enjoyed the course and hope that the exam will reflect how well I know the material.

So long.

Week 10

Hi all,

Before I prove something I want to highlight the space race at Dropbox for U of T https://www.dropbox.com/spacerace?r=NTQ4NDE0MjI3OQ. Go to this link to get a lot of space on Dropbox. As of this post everyone gets 15GB for two years.

Anyhow back to proving. Continuing on my problem. I am going to prove that once a power of 2 appears in the sequence we have a 1 in the sequence.

--------

Let P(n) be if the Collatz sequence starting at n has a x_m = 2^k, for some natural numbers m and k, then it contains a 1.

Assume x_m = 2^k.

x_m = 2*2^(k-1) so it is even. Following the sequence we divide by 2.
x_(m+1) = 2^(k-1) = 2*2^(k-2), we again divide by 2.

This procedure continues k times until x_(m+k) = 2^(k-k) = 2^0 = 1

Hence P(n).

--------

So now I know if I can show that the sequence at some point contains a power of 2 then I am done. I know at that point the sequence contains a 1.

More next time

Wendy

Week 9

Hi all,

So I've decided on a new problem, the Collatz Problem.

This is the one where there is a sequence that starts with a positive non-zero natural number and then does the following

• if its even: divide by 2
• if its odd: multiply by 3, then add 1

The point is to show that this sequence will always returns to 1. This problem is unsolved.

My natural instinct is to first show that in the sequence before 1 there will be a previous sequence that we have seen before and know that it returns to 1. After seeing on Wolfram the sequence written out, it seems that all the sequences end the same way.

  It also seems that it might be useful to see how these operations combine for any one number. And especially for one that is prime.

So heres my first part, I shall prove that when the odd operation is done a even operation immeadiately follows.

let a_n be 2k + 1 for some k in natural numbers. then P(n) is that 3a_n + 1 = 2m for some m in natural numbers.

So direct substitution:

3(2k + 1) +1 = 6k + 3 + 1 = 6k+4 = 2(3k + 2) = 2m

where m = 3k + 2

because a_n is an arbitrary odd number. it is true for all odd numbers.


Thats a start.

Wendy

Hi all,

Just posting to give an update. I think my problem is too easy I had it pretty much figured out in my head, it would take me not too long to write it out after that. I think I need a new idea (Danny, any ideas?).

I seem to be understanding the course work. I haven't had much time to commit to it as life has gotten in the way. When I'm in class it all falls into place in my head. I didn't do so great on the midterm, but it's due to a common problem with me, things seem so obvious to me that I don't write them down and then I lose marks for not writing them down. But I am doing really well on the quizzes so it's not so bad.

So long for now,

Wendy

Mathematical Problem Idea

Hi all,

I think I have figured out what I will do for the mathematical problem I need to solve on this slog.

My idea is: to prove that a number is a multiple of 11 if starting from the right you take the first digit, then subtract the second digit, then add the third digit, then subtract the next and so forth; then if that number is a multiple of 11 (positive, negative or zero) then the original number is also a multiple of 11.

I think this might be able to be proved using complete induction. I see a few problems arising. One is proving that the number I get in the add subtract step is smaller than the previous number always (although I think I sorta see how to prove that). Another is how to prove that if the new number is a multiple of 11 the previous one is also. After that it could be fairly straight forward. I guess part of it will be seeing it in action with numbers where the add subtract step gets a number >= 11.

By the way I got this algorithm from http://www.counton.org/explorer/primes/divisibility-tests-for-9-and-11/

So long for now.

Term Test Complete!

Hello,

So the term test is done and it was very straight forward. I think I have this induction thing down.

The next topic looks to be a bit more challenging. Seeing as I haven't seen big-oh in 4 years. I think I'll pick it up as I go and it is slowly coming back to me.

Looking at the floor and ceiling stuff will be need a bit of a refresher. I seem to remember that floor(x) > x - 1 and ceil(x) < x+1. I seem to remember learning that in CSC165 many moons ago. Also floor(x) <= x and ceil(x) >= x.

The definitions of ceil and floor are:

ceil(x) = :
x  if x is an integer
x + (1 - (x mod 1)   otherwise

and floor(x) = :
x if x is an integer
x - (x mod 1)  otherwise.

It seems that last class suggests I should figure out some properties of these operators beyond that.

So long,

Wendy

Week 4 Begins

A quarter of the way through the semester ALREADY. It always goes so fast.

Last week I got my first assignment for this course done. I didn't have a lot of difficulty with it.

I was impressed with myself with the way I solved question 4. Instead of combining the two related claims about binary strings, I proved only the claim about strings beginning and ending with the same bit. I accomplished this through my induction step. I went to the next string by inserting an arbitrary bit in the center (or Ceil(n/2)), thus preserving the same bit at each end. I thought this was clever.

I can see how one would prove this using the combined claim, but I wanted to see if my way would work and it did!

My plans for this week are to start the tutorial #2 problems. I have looked them over, I just haven't sat down to work them out. This is assuming my CSC209 assignment won't hog all my time. At least I got the assignment for this course finished so I'm not rushing on that.

On a side note, I wish my door didn't let in so much noise so I could still be asleep.

So long.