Entry #6 - Creating An Induction Function

For my final entry, I've decided to create a basic representation of induction in Python code. For this, I considered my parameters to be a statement and an int value that is greater than 0 (since that would emulate the natural numbers set). I have to define what I mean by statement:

'''

A statement is a string that contains two parts, both of which use x as

a variable. The two parts are seperated by one of the 

following signs:

<, >, <=, >=, ==, !=

When x is given a value and then the statement is evaluated,

it should return a bool.

ex. '2 ** x == 2 ** x' is a statement

'''

Now that it has been defined, I wrote down the following:

def inductor(statement, value=1):

    """ (statement, int) -> bool

    Precondition: value > 0

    

    Return whether induction works given the statement and the value

    """

    

    x = value 

    y = value + 1

    

    antecedent = statement.replace('x', str(x)) 

    consequent = statement.replace('x', str(y))

    

    if eval(antecedent) == True:

        if eval(consequent) == True:

            return True

        else:

            return False 

              

    else:

        return False 

        

The idea behind inductor is that we give it a statement and then input a start value to first check that the antecedent is true. If it is, we then see if the consequent is true. If it is, then we return True to prove induction works and if it is false, we know that induction cannot work. I did consider the antecedent to be false to return False in inductor despite rules of vacuous truth.

Let's consider the lecture example of 3 to the power of x being greater than or equal to x to the power of 4. The statement is written as so:

'3 ** x >= x ** 3'

When we type inductor('3 ** x >= x ** 3'), the following occurs:

1. The antecedent becomes '3 ** 1 >= 1 ** 3' since x = 1, which can be simplified to '3 >= 1'. Since it is True, we can then check the consequent.

2. The consequent becomes '3 ** 2 >= 2 ** 3' since y = x + 1, which can be simplified to '9 >= 8'. Since it is True, we return True.

3. Thus we can conclude that the statement '3 ** x >= x ** 3' can be inducted from its base case.

Now we could type inductor('3 ** x >= x ** 3', 2) and check to see if that's True. If it does return True (which it does), we can conclude that the statement works from 1 to 2 and then we can check to see if it works for 3. And we could keep going on and on until we hit a brick wall or we get tired of checking cases. To simplify this process, I created a second function called inductable_within.

def inductable_within(statement, end_value, start_value=1):

    ''' (statement, int, int) -> str

    

    Precondition: start_value < end_value

    

    Return if the statement can be proven by induction within the range of start_value and end_value

    '''

    

    for i in range(start_value, end_value):

        is_ind = inductor(statement, i)

        if is_ind:

            pass

        else:

            if start_value == i:

                return 'This statement cannot be inducted with the start value: {0}'.format(i)

            

            else:

                return 'This statement can be inducted from {0} up until {1}'.format(start_value, i)

        

    return 'This statement can be inducted within {0} and {1}'.format(start_value, end_value)

This allows us to check if the statement can be inducted within a certain range. So rather than inserting the statement into inductor 10 times and changing the start value, we can type inductable_within('3 ** x >= x ** 3', 10) and get the following string: 

'This statement can be inducted within 1 and 10'

This can also indicate when a statement breaks like so:

inductable_within('x + 2 < 10 - x', 5)

'This statement can be inducted from 1 up until 3'

If we plug in all the numbers in [0, 5], we get this:

1 + 2 < 10 - 1 | 3 < 9 | True
2 + 2 < 10 - 2 | 4 < 8 | True

3 + 2 < 10 - 3 | 5 < 7 | True

4 + 2 < 10 - 4 | 6 < 6 | False

5 + 2 < 10 - 5 | 7 < 5 | False

It is evident that this statement will not work for all natural numbers, since it will stop being true when x > 3. But what about the statement '3 ** x >= x ** 3'? Is it true for all natural numbers or will it break? If we try inductable_within('3 ** x >= x ** 3', 100), we get:

'This statement can be inducted within 1 and 100'

How about inductable_within('3 ** x >= x ** 3', 1000)?

'This statement can be inducted within 1 and 1000'

And inductable_within('3 ** x >= x ** 3', 10000)?

'This statement can be inducted within 1 and 10000'

Dare we go to inductable_within('3 ** x >= x ** 3', 100000)? After a while it does return:

'This statement can be inducted within 1 and 100000'

But these large ranges don't do much to prove it works for all natural numbers, just that it works for these large ranges. If we did have some representation of the set of natural numbers and we ran it with a modified form of inductable_within, how would we know whether it loops infinitely (since the set is practically infinite) or if it eventually halts to produce: 'This statement can be inducted from 1 up until (the number in which the induction implication is no longer true)'? The only way to know for sure is if we had some sort of function that could determine if inductable_within halts for all natural numbers. But we don't have that so therefore we cannot be certain of any statement being true for all natural numbers. We either would have to confide that it is true for all natural numbers or find one example in which the statement breaks.

Conclusion:

• inductor works to create a base case
• inductable_within works to find the range in which a statement can be inducted
• inductable_within cannot fully prove that induction works for all set of natural numbers since there does not exist a halting function

Entry #5: Using Python To Assure M And N Imply MN

For assignment 2, I wanted to see if there was some way I could express one of the claims in a Python program. I tried the floor question, but I saw it better fit to solve that through paper and pencil and the occasional calculation. Claim 2.2 on the other hand was a bit more accessible to my abilities:

For every m and n in the set of natural numbers, there exists an k in the natural numbers such that m = 7k + 3 and there exists a j in the natural numbers such that n = 7j + 4 imples that there exists an i in the natural numbers such that mn = 7i + 5. 

First, I made the following:

def is_m(num): #7k + 3 = m
    return ((num - 3) // 7) == ((num - 3) / 7)

def is_n(num): #7j + 4 = n

    return ((num - 4) // 7) == ((num - 4) / 7)

def is_mn(num): #7i + 5 = mn

    return ((num - 5) // 7) == ((num - 5) / 7)

This checks that we can represent the number as m or n or as mn. Let's consider 10, 18, 26, 27.

        10  18  26  27
is_m    T   F   F   F
is_n    F   T   F   F
is_mn   F   F   T   F

As we can see here, we can write 10 in m-form, 18 in n-form and 26 in mn-form. But what are the values of k, j or i? We use the following to figure it out.

def k_value(m): #check with is_m(m)
    m = m - 3
    temp = m / 7
    if (m // 7) == temp:
        return int(temp)
    else:
        return False
    
def j_value(n): #check with is_n(n)
    n = n - 4
    temp = n / 7
    if (n // 7) == temp:
        return int(temp)
    else:

        return False

k_value(10) returns 1 which means that if we considered m = 10, then in m = 7k + 3, k = 1. With j_value(18), 2 is returned meaning that if n = 18 and n = 7j + 4, j = 2. Using these random m and n, we can try to see if the two imply an mn:

def m_and_n_imply_mn_v1(m, n): #simple
    k = k_value(m)
    j = j_value(n)
    mn = m * n
    polynomial = 7*(7*j*k + 3*j + 4*k + 1) + 5

    return mn == polynomial

m_and_n_imply_mn_v1(10, 18) returns True but the explanation behind why polynomial is written the way it is seems unclear. First we need to consider what the i value, which seems to be replaced by the polynomial within polynomial.

def i_value(m, n): #check with is_mn(m * n)
    mn = m * n
    mn = mn - 5
    temp = mn / 7
    if (mn // 7) == temp:
        return int(temp)
    else:

        return False     

i_value(10, 18) returns 25 meaning that the product of 10 and 18 equals to 7 times 25 plus 5. To see this more clearly, we use a more complex version of m_and_n_imply_mn:

def m_and_n_imply_mn_v2(m, n): #detailed
    i = i_value(m, n)
    k = k_value(m)
    j = j_value(n)
    if i == (7*j*k + 3*j + 4*k + 1):
        sub_poly = str(7*j*k) + ' + ' + str(3*j) + ' + ' + str(4*k) + ' + 1'
        seven_jk = '7*' + str(j) + '*' + str(k) 
        three_j = '3*' + str(j)
        four_k = '4*' + str(k)
        sub_rep = seven_jk  + ' + ' + three_j + ' + ' + four_k + ' + 1'
        print('j = ' + str(j) + ', k = ' + str(k) + ', i = ' + str(i) + ', m = '
              + str(m) + ', n = ' + str(n) + ', mn = ' + str(m * n) )
        print('i = 7jk + 3j + 4k + 1')
        print(str(i) + ' = ' + sub_poly)
        print(sub_poly + ' = ' + sub_rep)
        print('7i + 5 = mn   ->  ' + '7*' + str(i) + ' + 5 = ' + str(m * n))
        print('m*n = ' + str(m) + '*' + str(n) + ' = ' + str(m * n)) 
        print('Therefore m = 7k + 3 and n = 7j + 4 imply mn = 7i + 5')
    else:

        return False

m_and_n_imply_mn_v2(10, 18) prints out the following:

j = 2, k = 1, i = 25, m = 10, n = 18, mn = 180
i = 7jk + 3j + 4k + 1
25 = 14 + 6 + 4 + 1
14 + 6 + 4 + 1 = 7*2*1 + 3*2 + 4*1 + 1
7i + 5 = mn   ->  7*25 + 5 = 180
m*n = 10*18 = 180
Therefore m = 7k + 3 and n = 7j + 4 imply mn = 7i + 5

Now if we consider a random mn such as 26, we need to modify i_value like so:

def i_value_mn(mn): #check with is_mn(mn)
    mn = mn - 5
    temp = mn / 7
    if (mn // 7) == temp:
        return int(temp)
    else:

        return False

i_value_mn(26) returns 3. This makes the converse implication false since there is no way that 3 = 7jk + 3j + 4k + 1 can be represented by natural numbers. Consider the following.

m_and_n_imply_mn_v2(3, 4):

j = 0, k = 0, i = 1
i = 7jk + 3j + 4k + 1
1 = 0 + 0 + 0 + 1
0 + 0 + 0 + 1 = 7*0*0 + 3*0 + 4*0 + 1
7i + 5 = mn   ->  7*1 + 5 = 12

m_and_n_imply_mn_v2(10, 4):

j = 0, k = 1, i = 5
i = 7jk + 3j + 4k + 1
5 = 0 + 0 + 4 + 1
0 + 0 + 4 + 1 = 7*0*1 + 3*0 + 4*1 + 1

7i + 5 = mn   ->  7*5 + 5 = 40

m_and_n_imply_mn_v2(3, 11):

j = 1, k = 0, i = 4
i = 7jk + 3j + 4k + 1
4 = 0 + 3 + 0 + 1
0 + 3 + 0 + 1 = 7*1*0 + 3*1 + 4*0 + 1

7i + 5 = mn   ->  7*4 + 5 = 33

i can equal 1, 4 and 5 at low values of natural j and k but not 2 nor 3. 

Conclusion:

• m and n imply mn
• mn does not completely imply m or n

#####################################

Bonus: As an extension of my previous entry, I have here all of the code for the penny piles problem:

def half_l2r(drawers):
    """ (list of ints) -> list of ints
    Precondition: len(drawers) == 2 
    
    Return drawers with half of drawers[0] added to drawers[1]
    >>> half_l2r([64, 0])
    [32, 32]
    """
    ret = list(drawers)
    if drawers[0] % 2 == 0:
        ret[0] = drawers[0] // 2
        ret[1] = drawers[1] + ret[0]
    return ret

def half_r2l(drawers):
    """ (list of ints) -> list of ints
    Precondition: len(drawers) == 2 
    
    Return drawers with half of drawers[1] added to drawers[0]
    >>> half_r2l([16, 32])
    [32, 16]
    """
    ret = list(drawers)
    if drawers[1] % 2 == 0:
        ret[1] = drawers[1] // 2
        ret[0] = drawers[0] + ret[1]
    return ret

def prime_factors(n): #returns the prime factors of a number
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def product_list(L): #returns the product of the items in a list
    product = 1
    for item in L:
        product = product * item
    
    return product

def is_multiple(x, n): #is x a multiple of n?
    is_it = False
    if x == n:
        is_it = True
    else:
        i = 1
        y = n
        while x != y and y < x:
            i = i + 1
            y = n * i
            if x == y:
                is_it = True
    return is_it

def possible_products(L): #returns the possible products
    poss_prod = []
    if len(L) == 2:
        product = L[0] * L[1]
        poss_prod.append(product)
    elif len(L) > 2:
        i = 0
        while i < len(L):
            sub = list(L)
            sub.remove(sub[i])
            sub_prods = possible_products(sub)
            j = 0
            while j < len(sub_prods):
                temp1 = sub_prods[j] * L[i]
                temp2 = sub_prods[j]
                j = j + 1
                if temp1 not in poss_prod:
                    poss_prod.append(temp1)
                if temp2 not in poss_prod:
                    poss_prod.append(temp2)                
            
            i = i + 1    
            
    return poss_prod

def poss_prod_fixer(poss_prod): #fixes the results of possible_products
    poss_prod.sort() 
    poss_prod.reverse()
    poss_prod.remove(poss_prod[0]) #we do not want the product of all integers

def penny_possible_halving(drawers, penny_goal):
    """ (list of ints, int) -> bool
    
    Precondition: len(drawers) == 2 and (drawers[0] == 0 or drawers[1] == 0)
    
    Return if drawers can be resorted so that one value equals penny_goal
    using half_l2r and half_r2l
    
    >>> penny_possible([64, 0], 40)
    True
    >>> penny_possible([0, 34], 2)
    False
    """
    gen_L = []  #For convenience, we will refer to this as a generic list
    gen_L.append(drawers)
    i = 0
    while i < len(gen_L):
        if gen_L[i][0] == penny_goal or gen_L[i][1] == penny_goal:
            return True
        
        if gen_L[i][0] % 2 == 0 and gen_L[i][0] != 0:
            l1 = half_l2r(gen_L[i])
            if l1 not in gen_L:
                gen_L.append(l1)
        
        if gen_L[i][1] % 2 == 0 and gen_L[i][1] != 0:
            l2 = half_r2l(gen_L[i])
            if l2 not in gen_L:
                gen_L.append(l2)
                
        i = i + 1
    
    return False

def penny_possible_conditions(drawers, penny_goal):
    """(list of ints, int) -> bool
        
    Precondition: len(drawers) == 2 and (drawers[0] == 0 or drawers[1] == 0)
        
    Return if drawers can be resorted so that one value equals penny_goal
    using conditions and factorization
        
    >>> penny_possible([64, 0], 40)
    True
    >>> penny_possible([0, 34], 2)
    False
    """
    q = drawers[0] + drawers[1]
    primes = prime_factors(q)
    
    if penny_goal > q:
        return False
    
    #considering [q, 0]
    if (drawers[0] == 0 or drawers[1] == 0) and drawers[0] != drawers[1] :
        if primes.count(2) == len(primes): #q = 2 ** r
            return True 
        elif primes.count(2) != len(primes) and primes.count(2) > 0: 
            #q = (2 ** r) * n
            if penny_goal == 0 or penny_goal == q:
                return True
            
            else:
                while primes.count(2) > 0:
                    primes.remove(2)
                multiple = product_list(primes)
                return is_multiple(penny_goal, multiple)
                #penny_goal is only reached when it is a multiple of n
                
        elif primes.count(2) == 0:
            return penny_goal == 0 or penny_goal == q
            
    if drawers[0] % 2 == 0 and drawers[1] % 2 == 0: #considering [e, e] 
        if drawers[0] != 0 and drawers[1] != 0:
            if drawers[0] == drawers[1]: 
                if primes.count(2) == len(primes):
                    return 0 < penny_goal < q
                elif primes.count(2) != len(primes):
                    if penny_goal == 0 or penny_goal == q:
                        return False
                    while primes.count(2) > 0:
                        primes.remove(2) 
                    multiple = product_list(primes)
                    return is_multiple(penny_goal, multiple)
            else: 
                if primes.count(2) == len(primes):
                    return penny_possible_halving(drawers, penny_goal)
                elif primes.count(2) != len(primes):
                    if penny_goal == 0 or penny_goal == (q/2) or penny_goal == q:
                        return False
                    while primes.count(2) > 0:
                        primes.remove(2) 
                    multiple = product_list(primes)
                    multicheck_1 = is_multiple(drawers[0], multiple)
                    multicheck_2 = is_multiple(drawers[1], multiple)
                    if multicheck_1 and multicheck_2:
                        return is_multiple(penny_goal, multiple)    
                    else:
                        return 0 < penny_goal < q
    
    if drawers[0] % 2 == 1 and drawers[1] % 2 == 1: #considering [o, o]  
        return penny_goal == drawers[0] or penny_goal == drawers[1]
    
    if (drawers[0] % 2 == 0 and drawers[1] % 2 == 1) or (drawers[0] % 2 == 1 and drawers[1] % 2 == 0): #considering [e, o] or [o, e]
        if penny_goal == q or penny_goal == 0:
            return False
        if q == primes[0]: #q is a prime number
            return 0 < penny_goal < q
        else: #q is not a prime number
            if len(primes) == 2: #q = n1 * n2
                both_multiples = False
                multiple = None
                for item in primes:
                    multicheck_1 = is_multiple(drawers[0], item)
                    multicheck_2 = is_multiple(drawers[1], item)
                    if multicheck_1 and multicheck_2:
                        both_multiples = True
                        multiple = item
                if multiple != None: #both items in list are a multiple of any n
                    return is_multiple(penny_goal, multiple)
                else: #both items are not a multiple of any n
                    for item in primes:
                        multiple = item
                        if is_multiple(penny_goal, multiple):
                            return False
                    return 0 < penny_goal < q
            else: #len(primes) > 2
                both_multiples = False
                multiple = None
                multiples = primes
                prod_of_primes = possible_products(primes)
                poss_prod_fixer(prod_of_primes)
                multiples.extend(prod_of_primes)
                multiples.sort()
                conflict = 0
                for item in multiples:
                    multicheck_1 = drawers[0] % item
                    multicheck_2 = drawers[1] % item
                    if multicheck_1 == 0 and multicheck_2 == 0:
                        both_multiples = True
                        multiple = item
                if multiple != None: #both items in list are a multiple of a N/n
                    iron_multiple = multiples.pop(multiples.index(multiple))
                    for item in multiples:
                        multiple = item
                        if multiple > iron_multiple:
                            if penny_goal % multiple == 0:
                                return False                
                    return True                    
                else: #both items are not a multiple of any n/N
                    for item in multiples:
                        multiple = item
                        if penny_goal % multiple == 0:
                            return False
                    return 0 < penny_goal < q                        

            

Entry #4 - The Penny Piles Problem

The Penny Piles problem proved to be far more complicated than the previous problem. The idea of this problem is to figure out what numbers can be possible to obtain from sorting a pile of pennies from two drawers with operations l and r.

l: if the left drawer has an even amount of pennies, move half of them to the right drawer

r: if the right drawer has an odd amount of pennies, move half of them to the left drawer

First, the question gives us the scenario of 64 pennies in the left side and 0 on the right. I came up with this chart:

The chart is extensive but looking at it closely, one can see that you can get any number from 0 to 64. Pondering, I figured that if any number could be represented as 2 to the power of n, you could get any number within the range of 0 to that number and decided to look into making a few tree charts of that.

Looking at numbers before it, one can see that it is possible to write it as such. But now, I have to consider other sorts of numbers. I excluded the idea of odd numbers and having the right drawers have anything more than 0 for the time being.

(NOTE: 12 is actually 2*2*3)

Here we have a slew of numbers with different prime factorization patterns. I kept trying to find relationships between each scenario of them, eventually stumbling across this idea:

q would be our starting number. If q could be written as 2*2*n, then it is possible that 0, n, q/2, q - n and q could be reached. Where as if we can have q = 2*2*2*n, we get a more complicated result. This then left me to consider a number like 48 which could be written as 2*2*2*2*3, leading to this:

 Eventually, I resulted in getting this diagram:

This proved to be difficult for me to figure out what line r could be since it could be an immense line of numbers. all that was certain is that by always going left, [n, q - n] would be achieved. I figured that I would cut my losses and post my progress but upon looking at the trees for 10, 12, 56, 48 and 100 I noticed something.

numbers I can get from [10, 0]:

(0, 5, 10)

numbers I can get from [12, 0]:

(0, 3, 6, 9, 12)

numbers I can get from [56, 0]:

(0, 7, 14, 21, 28, 35, 49, 56)

numbers I can get from [48, 0]:

(0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 36, 39, 42, 45, 48)

I then realized that if a number is a multiple of n within the range of 0 to q, you can get that number. So now I have one idea. Now I have to consider if one drawer has an odd number of pennies and if both drawers have two even numbers that are different.

Let's consider pair [6, 4] and [12, 10] first. The total amount of each is 10 and 22, but neither the total amount, half of the total amount or 0 is present in the tree. Let's consider what is inside it though:

[6, 4] results in (1, 2, 3, 4, 6, 7, 8, 9)

[12, 10] results in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)

It can be gathered that if a pair is [e, e], then it can get any number in range 0 to q (q being e + e) except 0, q/2 and q. 

Now let's look at the two [o, e] pairs:

[4, 3] results in (1, 2, 3, 4, 5, 6)

[11, 4] results in (1, 2, 4, 7, 8, 11, 13, 14)

The only thing that the two share is that they do not reach their sum nor 0. A difference is that 4 + 3 = 7 which is a prime number and 11 + 4 = 15 which is not. Now then, we can consider more cases of odd + even = prime and odd + even = odd not prime separately.

Based on these examples above, I can conclude that if odd + even = prime, then you can obtain any number from 0 to q except 0 and q

Here I can see that if odd + even = not prime, I obtain a series of different results when I switch their values. I realize that the numbers excluded in [11, 4] are then filled in by [3, 12] and [10, 15]. Both of those are prime factors of q and the results that each of them obtain are their multiples. 15 is not included since it is in the range we cannot reach and there is no overlap of numbers which are multiples of both 3 and 5.

With this, I find that if the prime factorization is one prime times itself again, it will obtain the multiples of that prime. Now one case I have to consider is something along the lines 3 different primes timed together.

I can then infer that multiples of single primes can only reach numbers that are solely their own and not ones that are shared with other prime numbers. Or to put it different, if a multiple of a prime is shared with the multiple of a prime times another prime, it will not appear as a possibility. This also applies for something like 125, which would be weird considering it's 5*5*5. But consider multiples of 25 and 5. 

In conclusion:

Let e mean even and o mean odd
Let n mean a prime number (excluding 1)
Let N mean a product of prime numbers

If you want one number in [a, b] to equal x

• For [q, 0]:
  
  If q = 2^r, x == 0 or x == q or 0 < x < q
  
  If q = (2^r)*n, x == 0 or x == q or x is a multiple of n (n can be N too)
  
  If q = odd number: x == 0 or x == q
• For [e1, e2]: (assume q = e1 + e2)
  
  If e1 == e2, 0 < x < q
  
  If e1 == e2 and e/(2^r) = n, x is a multiple of n
  
  If e1 == e2 and e/(2^r) = N, x is a multiple of N
  
  If e1 != e2 and q = 2^r:
  PENDING
  
  If e1 != e2 and q = (2^r)*n or q = (2^r)*N:
  
  If e1 and e2 share a common n/N, then x != 0, x != q/2 and x != q and x must be a multiple of n/N
  
  If not: 0 < x < q and x != (q/2)
• For [o1, o2]: x == o1 or x == o2
• For [o, e]: (assume q = o + e)
  
  If q = prime, 0 < x < q
  
  If q = not prime:
  Factor q as n*N (*)
  
  If o and e are a multiple of n, x is a multiple of n PROVIDED that it is not a multiple of N and x != q
  
  If o and e are a multiple of N, x is a multiple of N and x != q
  
  If o and e are not a multiple of n or N, 0 < x < q and x is not a multiple of n or N
• (*)
  Keep in mind q can adapt the following scenarios:
  
  q = n1*n2 in which case, o, e and x apply to the unique n
  
  q = n1*n2*n3 which could result in:
  
  q = n1*N(2,3)
  q = n2*N(1,3)
  q = n3*N(1,2)
  
  o, e and x apply to n1 only if it doesn't belong in N(1,2) or N(1,3)
  o, e and x apply to n2 only if it doesn't belong in N(1,2) or N(2,3)
  o, e and x apply to n3 only if it doesn't belong in N(1,3) or N(2,3)
  
  We can have n1 == n2, n2 == n3 or n1 == n3 in this scenario
  
  q = n1*n1*n1 becomes n*N which then applies to the original statment
  
  If we had q = n1*n2*n3*n4:
  
  q = n1*N(2,3,4)
  q = n2*N(1,3,4)
  q = n3*N(1,2,4)
  q = n4*N(1,2,3)
  q = n1*n2*N(3,4)
  q = n1*n3*N(2,4)
  q = n1*n4*N(2,3)
  q = n2*n3*N(1,4)
  q = n2*n4*N(1,3)
  q = n3*n4*N(1,2)
  
  
  o, e and x will only apply to n1 if N(a,b) or N(a,b,c) does not contain 1.
  o, e and x will only apply to N(1,2) if N(a,b,c) does not contain 1 and 2
  etc.

EDIT (10-27-2014):

Updated info in conclusion

Entry #3 - Proofs And The Test

In Week 5, I learned a new way to format a proof as well as how one can create a proof by contradiction with a statement that requires you to look at a long list of factors. I'll admit that it still is a tough subject for me to understand completely how to go about a proof. Certainly a frustrating factor is trying to find something that can allow you to show to someone that you understand that the statement is true or false. Another bit that confuses me is when one should comment and when one should assume that the reader would already know it. I should look into finding some problems and making proofs to them so I get more practice. 

Equally as important this week was the test. On the one hand, I feel as if I had studied properly for this test and had all the information that I needed to get a very high mark on it. On the other hand, I know I made substantial/idiotic errors that will cost me dearly. The last question was probably the biggest example of this as I finally had the proper sets and made the right statements true and false but before I could rewrite my answer so it would align properly to my statement, time was up. It may have to do with perhaps worrying that I wouldn't get enough marks if I didn't explain well for the first question which ate up time to do the other questions.

PROBLEM:

This is taken straight from the problem-solving wiki:

Suppose n stands for some positive whole number. Define a function f(n) that associates n with another positive whole number, as follows:
If n is even, then f(n) is n/2
If n is odd, then f(n) is 3n+1

Since f(n) takes any positive whole number as input, and produces a positive whole number as output, it makes sense to talk about f(f(n)) or f(f(f(n))) --- composing f with itself several times. Let's define F(m,n) as f(f(...f(n)...), where f is composed with itself m times. Is the following statement true or false?

For each natural number n there exists a natural number m such that F(m,n) = 1.

EXPLAINING WHY IT'S TRUE:

It is important to note that this is referring to the Collatz conjecture. If we write the statement symbolically we get:

∀ n ∊ ℕ, ∃ m ∊ ℕ, F(m, n) = 1.

Writing out the negation would be:

∃ n ∊ ℕ, ∀ m ∊ ℕ, F(m, n) =/= 1.

If I wanted to make the negation true, I would have to find a natural number that would never reach to 2, since 2/2 = 1. Which would also mean that this natural number would never be converted to a number that equivalent to a power of 2. It's evident that I can't find one that satisfies the negation because there is no number that can't avoid being pulled into being equal to a power of 2. One way to look at it is by an example:

14 = 7 * 2
(3*7 + 1) * (2/2)
(22/2) * 1
(3*11 + 1) # disregard 1 since it's already reached its final point
(34/2)
(3*17 + 1)
(52/2)
(26/2)
(3*13 + 1)
(40/2) # multiple of 10 and power of 2
(20/2)
(10/2)
(3*5 + 1) # by only one step, 5 reaches a power of 2
(16) # we have reached a power of 2

Splitting up any number into its prime factors we could have each number go through the Collatz conjecture separately and they'd reach a power of 2 at any moment. It's important to note that 5 is a prime odd number and it immediately reaches a power with one step and before it got to 5 it was gravitating to a multiple of 10 and a power of 2. Basically speaking, there are little "traps" that occur which snare numbers into sliding down to one which are impossible to avoid.  

Entry #2 - The Folding Problem

The folding problem was quite tricky to wrap my head around. The idea of the problem is to find a way to predict the pattern of the directions of the creases on a piece of paper given the amount of times the paper was folded. I was able to get the first four patterns which gave me this result:

It occurred to me that on pattern 3, something was happening within it. Separating the pattern, I was able to see that pattern 2 and pattern 1 were in it. More importantly I noticed that pattern 2 was not only in pattern 3 twice, but the first time pattern 2 appeared, it had been flipped:

Removing pattern 1, I noticed that the other patterns followed the same format of flipping the previous pattern at the start, having a down arrow in the middle and then proceeding with the previous pattern as normal:

With this, I was able to come up with pattern 5:

With that in mind, I could very much just say that in order to predict the next pattern, start with the flipped version of the previous pattern, add a down arrow and then finish the normal version of the pattern. Looking at pattern 5 closer, I figured that there was another way to predict the patterns once I arranged it as so:

Pattern 3 is once again important to take into consideration since it outlines the patterns that follow it. The blue is the flipped version of the pink (or vice versa if it's more convenient to understand). It is then followed by a green arrow that separates the pattern. The direction in which the green arrow faces is dependent on the first pattern. 

To simplify this construct, let's create a sub-pattern which we will call a pair. One should write the blue pattern with a space and then write the pink pattern and consider it the pair. You repeat the pair 2^(x-3) times, x being the number that your pattern is. Then in order to fill in the spaces, you go to the first space on the left and then fill it in with the first arrow in the x-2 pattern. Keep doing this until both all the spaces are filled and you've finished using all the arrows in the x-2 pattern. Once that is done, the new pattern has been finished.

In summation: (U means up arrow, D means down arrow and S means space)

• Let x be the number of the pattern (Precondition: x >= 3)
• Let P(x) be the pattern itself (ex. P(2) = UDD)
• Let p be a pair in which UDDSUDD
• Repeat p 2^(x-3) times
• Replace the first S in P(x) with the first arrow in P(x-2) and follow along until all S have been replaced and all the arrows in P(x-2) have been used
• P(x) is completed.