Products of Sums

I was trying to work this through recursion, I'm not exactly sure if I got it right. but I think I'm on the right track, since it seems that the greatest sum usually consists of a 3 and/or 2's.


def great_mult(num):
    lists = []
   
    if num <= 3:
        lists.append(num)
        return lists
   
    if num % 3 == 0:
        num = (num - 3)
        lists.append(3)
        lists.extend(great_mult(num))
    else:
        num = (num - 2)
        lists.append(2)
        lists.extend(great_mult(num))
       
    return lists

It's nice to finally have some time to try the problems shown in class.

Free Lunch

Understanding the Problems:
Free lunch consists of a group of friends trying to determine who gets free lunch. The way they decide is that they arrange themselves in a circle and start counting the positive natural numbers in order. The person at the most north of the circle starts counting from 1. Anyone who says an even natural number gets removed from the circle. When we reach the last person this wraps around and goes back to the person at the beginning. This continues until there is exactly one person left, and this person gets free lunch in the end.

Devise a Plan:
I'm going to perform a few basic examples to help clear out exactly what happens

Carry out the Plan:
So a few examples to help clear out what happens in different situations, I left the index underneath and used a list because I was preparing it so that I could code it easily later on. The case below, is just a simple example without any complications.

[1, 2, 3, 4]
(0, 1, 2, 3) - Index
[1, 3]
(0, 1) - Index
[1] - Last One = 1


Here there is no complication in reaching the person who gets free lunch since the number of people stays even until you reach the last person. You just continuously remove the person who is at an odd index in python terms.

[1, 2, 3, 4, 5]
(0, 1, 2, 3, 4,) - Index
[5, 1, 3]
(0, 1, 2) - Indes
[3, 5]
(0, 1) - Index
[3]- Last One = 3

Here is were it gets a bit more tricky, since the last item is on an even index, (the number of people is odd) and is right after someone who gets removed. For the python code to work that person becomes the technical new "first person" and we start counting from them. That is why the 5 moves to the front and then the 3 gets moved to the front, since the lists are odd.


def remove_odd_index(L):
    ''' Remove the odd indeces, which corrolate to the "person"
       counting the even natural numbers.
 
 # Once the list has a length of 1 return that item, which means once theres only one person left,
 # you have the winner.
    if len(L) == 1:
        return L[0]
 
    # Go through all the odd indices and remove them.
    work = L[:]
    for i in range(1, len(L), 2):
        work.remove(L[i])

   # If there is now an odd number of people then the last person because the first
   # in the new "set" of people
    if len(L) % 2 != 0:
        work.insert(0, L[-1])
        work = work[:-1]

   # Continue calling the function until there is one person left
    return remove_eve_ind(work)

Look Back:
I tried doing it with circles and it made it harder to actually see the pattern when dealing with certain numbers of people, such as the pattern of how to deal with even number of people and the pattern that there is when dealing with an odd number of people. It took me a little while to figure out how to insert the last item at the front of the list, and had a lapse in brain power trying to remember that I could just slice the list to remove the last item, but that was just some rustiness in coding. The general concept of the problems I understand when I kept it as a line because it was easier to see that I could just move the last person in an odd numbered list to the front and continued from there.

I also want to thank Mandy from http://mandyxu.blog.com for showing me this problem, it was actually pretty fun to figure it out the code for this.
 

Computable Halt! ...... never mind

I found this concept so strange, the way we prove a function is not computable is by assuming it is computable and showing that it is a halting function and since a halting function is not computable then we can safely assume that our original function is not computable.

I find a lot of these concepts strange but I understand why the proof structure works. If something can't exist then you can't really say it does within your function.

After the assignment I was doing one of the tutorial problems, which was pretty similar to the assignment and it helped clear up some of the stuff that I was unsure of.

Here's how I did it.

Reduce halt to allstop.

all stop(P) = { True if P(x) halts for every input x,
                    { False, otherwise'

def half(P, x):
       def all stop(P):
     
        #Check if P(x) halts
        # for every input X
        # Assume computable

     def not_f(x)
           P(x)
           return "You shall halt"

     return all stop(not_f, x)

The way I explained it to complete the proof was that if P(x) halted, that meant not_f(x) halts, which causes allstop(P) to return True. In the end this means that halt returns True as well. If P(x) doesn't halt, then not_f(x) doesn't halt which means allstop(P) would return False, which would cause the halting function to return False. So when P(x) halts, allstop returns True and halt(P, x) returns True and when P(X) doesn't halt, then allstop returns False and halt(P, x) returns False. So This means I have technically written a working halting function, which doesn't exist to my knowledge. So then we can safely assume that allstop is not computable since it is a halting function.

I hope that explanation makes sense, took a bit of explanation from my assignment partner for it to make sense of it when we were working on the assignment.

Clarifying Big-Oh

Big-Oh notation was a weird concept to me at first, especially when Professor Heap told us that we could just choose to drop values from within the given functions. But after going through the steps it started to make a lot more sense.

Since we are saying that the function that we are making bigger is bounded above by a function that we are making smaller, even if we only have to multiply by a small constant factor. If it is true for that then it is true for all natural number.

Here's a run through from one of the tutorial examples:

Statement: ∃c ∈ R, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ 5n⁴ - 3n² + 1  ≤ c(6n⁵ – 4n³ + 2n)

      Pick c = 3, Then c ∈ R

       Pick B = 1, Then B ∈ ℕ

      Assume n ∈ ℕ                        # n is a generic natural number, to introduce ∀

                  Assume n ≥ B                        # assume antecedent, to introduce ⇒

                              Then 5n⁴ - 3n² + 1

• Since we're saying that  5n⁴ - 3n² + 1 is bound above by c(6n⁵ – 4n³ + 2n) we can continue to make it larger and if it is still bound above then we know it is true.

                              ≤ 5n⁴ + 1        # Remove (-3n)

• For all the natural numbers past the break point, we can safely prove that this will be bound above by this. 

                              ≤ 5n⁴ + n        # n ≥ 1 hence B = 1

                                             = 5n⁴  + n⁴

                                             = 6n⁵                      # Multiply by n

• Here we pick the c, so that this function is true for all natural numbers N. c this helps scale the function to make this true for all natural numbers.

                                             = 3(2n⁵)                     # c = 3

                              = c(6n⁵ – 4n⁵)

                              ≤ c(6n⁵ – 4n³)

                              ≤ c(6n⁵ – 4n³ + 2n)

• Since  c(6n⁵ – 4n³ + 2n) is what we are bounding by we can continue to make it smaller for the same reason stated above, because if this still bounds the bottom function above then it is true for the much larger function.

                              Then 5n⁴ - 3n² + 1  ≤ c(6n⁵ – 4n³ + 2n)

                  Then n ≥ B ⇒ 5n⁴ - 3n² + 1  ≤ c(6n⁵ – 4n³ + 2n)  # conclude ⇒

      Then ∀n ∈ ℕ, n ≥ B ⇒ 5n⁴ - 3n² + 1  ≤ c(6n⁵ – 4n³ + 2n)            # conclude ∀

            Then ∃c ∈ R, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ 5n⁴ - 3n² + 1  ≤ c(6n⁵ – 4n³ + 2n)                                                                                                                   # conclude ∃

Test and Assignments !

Just got my test and assignment mark back and I'm extremely happy with how it turned out. As I stated in my previous post, the assignments do really help in preparing for the test. Of course reviewing the past test and reading all the lecture notes over also helped while also practicing everything we covered in tutorial and lectures to make sure I got down the concepts. It's strangely satisfying reaching the end of a proof and understanding why it makes sense.

Now we're moving on from that and going into Assignment 3, which I believe will cover much of what we have seen of Chapter 4. I think I'm ready for the challenge. I'm still a bit unsteady on some of the ideas of Chapter 4 like how we can just remove certain elements of a function. I understand why we do it, but it just seems strange. I think I'm to use to Calculus we're we can't just make things disappear.

Progress

It's weird but every time I learn something new in this class I find it extremely hard and feel doomed, but after practicing a bit here and there things seem to work out. The way this course is structured works out pretty well. In the sense that the Assignments help develop the skills i need to do well on the Tests. This and the steady pace keeps this, I find, at a manageable pace.

The slog has been a little slow lately and I'm sorry for that. Just keeping up with the assignment and preparing for the tests take up a lot of time.

StreetCar Drama is possible

When I had heard Professor Heap telling us about the street car problem, I didn't think it was possible but it seems it is. I was reading my friend Mandy's blog and she had figured it out. The solution can be found here: http://mandyxu.blog.com/2013/02/28/streetcar-drama/


Heres the problem:
A: Haven't seen you in a long time! How old are your three kids now?
B: The product of their ages (rounded down to the nearest year) is 36.
A: That doesn't really answer my question.
B: Well, the sum of their ages is (fire engine goes by)
A: That still doesn't tell me how old they are.
B: Well, the eldest plays piano.
A: Okay, I see: their ages are (you have to get off the streetcar)

The solution is actually pretty clever and the one tip that I can give without pretty much giving the answer a away is to write out the possible combinations of numbers. It always seems that carrying out a few sample solutions helps find patterns in this course.