SLOG Entry #11 Week 11 Diagonal Progress

The lecture on Monday was like no other lecture we've had so far. Finally, something really grabbed my attention. I was completely new to the halting problem before and the idea of a program that could predict the behaviour of functions fascinates me. On that note, the way Professor Heap showed that the halting function cannot exist didn't convince me. The so-called naval_gaze function didn't impress me at all but it did make me think about naval_gaze itself. Basically, the function takes itself as input and returns where or not it halts by using an imaginary halting function. It then provides a contradiction because the function itself doesn't halt when halt is called on it. This makes me very skeptical. It seems to me that the function is set up in a way simply to provide a contradiction. Having said that, I could probably make a function that takes almost any function that is commutable as input and comes up with a contradiction. Does that mean that the function is non-computable? No.

I won't talk about the tutorial in this blog post because I would like to post my partial solution to the diagonal problem in here. After a about an hour of drawing many different grids, I came up with a formula that worked for many numbers less than double digits and for many odd numbers in double digits.

To begin, I recorded the result of many different grids. 1x2, 1x3, 1x4, 2x3, 2x4, 2x5, 2x6, 3x3, 3x4, 3x7, 3x9, 4x6, 4x8, 4x 10, 7x5, and 7x12 to name a few.

I first noted that for any two numbers n and m, if one of the numbers is odd and they don't divide each other  then the number of squares covered is equal to (m+n)-1. I also noticed that if both numbers are even and one divides the other, then the numbers of squares is max(n, m). I then tried to reduce cases where both numbers are even but don't divide each other to a case when one is odd so that I could the first algorithm (m+n)-1. I did this by dividing both m and n by 2 and multiplying (m+n)-1 by how many times I divided them both by two. I soon realized that this didn't work for a grid that is 40x60.  In other words, my formula needs to be tinkered with some more.

My function is this: 

def diagonal(n,m):

    if n < m:

        if m%n == 0:

            return m

        

        elif n%2 == 0 and m%2 == 0:

            count = 1

            while n%2 == 0 and m%2 == 0:

                n = n//2

                m = m//2

                count = count + 1

            

            return (count*((n+m) - 1 ))

    

        elif n%2 == 1 or m%2 == 1:

            return (n+m) - 1  

    else:

        if n%m == 0:

            return n    

        

        elif n%2 == 0 and m%2 == 0:

            count = 1

            while n%2 == 0 and m%2 == 0:

                n = n//2

                m = m//2

                count = count + 1

            

            return (count*((n+m) - 1 ))

        elif n%2 == 1 or m%2 == 1:

            return (n+m) - 1     

It works for most inputs less than double digits but of course that's not good enough for me.

So I am continuing to look for a more correct function that involves reducing complicated cases to simple cases. I feel that I'm very close to the right answer and I really hope to get it in by next week.