An Attempt at the Collatz Conjecture

When I was searching for a problem to solve on the problem-solving wiki, a problem that "may resist all your attempts to solve" caught my eye. I was curious about how "resisting" the problem is, so here is my attempt at finding a solution for it.

Question: 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 [positive] natural number n there exists a [positive] natural number m such that F(m,n) = 1.

Attempt:
I first start by making sure that I understand the problem. Given the definitions of f(n) and F(m, n), I either need to prove that the statement above is true, or find a counterexample. So first I list some examples to try to find some patterns:

n    m    f(n) recursion results
1    3    4,2,1
2    1    1
3    7    10,5,16,8,4,2,1
4    2    2,1
5    5    16,8,4,2,1
6    8    3,10,5,16,8,4,2,1
7   16   22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
8    3    4,2,1
9   19   28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
10  6    5,16,8,4,2,1
11  14  34,17,52,26,13,40,20,10,5,16,8,4,2,1

So far, no counterexamples are found. I begin to suspect that the statement is true, although I cannot be sure. More examples would strengthen my thinking that the statement is true. But finding m for a large number n can become tedious. The natural thing to do is to write a program that helps me with this task:

def f(n):
    if n % 2 == 0:
        return n / 2
    else:
        return 3 * n + 1
 
   
def F(n):
    m = 1
    n = f(n)
    while n != 1:
        n = f(n)
        m += 1
    return m

The program successfully executes. There does not seem to be any obvious pattern associated with n and m, although for larger numbers n, sometimes m repeats itself for consecutive numbers n. For example:

n           m
940      129
941      129
942      129
943      36
944      36
945      36
946      36
947      36
948      36
949      36

F(m, n) does have a pattern when n is a power of 2 though. In these cases, m is the exponent of that power. For example, when n = 2^1, m = 1;  when n = 2^2 = 4, m = 2;  when n = 2^3 = 8, m = 3, etc. This is due to the fact that a postive power of 2 is always even, so f(n) = n/2 is always executed. After executing m times, f(n) = 1. Since powers of 2 work nicely, what if I write every postive natural number n in terms of powers of 2 plus any remainder? Perhaps m has an indirect relationship with all these powers of 2s.

n
1 = 1
2 = 2^1
3 = 2^1 + 1
4 = 2^2
5 = 2^2 + 1
6 = 2^2 + 2^1
7 = 2^2 + 2^1 + 1
8 = 2^3
9 = 2^3 + 1
10 = 2^3 + 2^1
11 = 2^3 + 2^1 + 1  

After some trial-and-error scratch work on trying to find a pattern between m and n written as powers of 2 and the remainder, I derived no useful results.

Now I list some facts about f(n), F(m, n) and the examples above to see if anything would help to prove the statement:

 n/2 always decreases, while 3n + 1 always increases for a positive natural number n.

 The only way to get down to  1 is if at some point of the recursion, F(k, n), where 1 <= k < m, is a positive power of 2. So we could try to prove that every natural number n, after performing a finite number of f(n), becomes a power of 2.

3n + 1 = 2n + (n + 1). 2n is always even. Since n is odd, n + 1 is even. Then an even number plus an even number is always even. So 3n + 1 is always even. If n is currently odd, then after executing 3n + 1, n becomes even, in which case the new n will be reduced by half using n/2. Thus we know that F(m, n) is not infinitely increasing. Instead, the function F generally goes up and down.

None of these facts directly help with the actual proof. However, the second point leads me to a new direction. I know that every number have a prime factorization. We can separate the prime factorizations into powers of 2 and all others. Then every positive natural number n can be written as n = 2^k * t, where k >= 0, and t is odd (since t contains no more powers of 2). Then it looks like this proof could take the form of Complete Induction, where the two parts 2^k and t may become useful in the induction step.

Let P(n) be the following predicate:
P(n): there exists a positive natural number m such that F(m, n) = 1.

Base Case: n = 1. Then n is odd, so f(n) is executed as follows: 3(1) + 1 = 4, 4/2 = 2, 2/2 = 1. Thus m exists. So P(1) holds.

Induction step:
Assume i is a positive natural number such that 1 <= i < n, and P(i) is true; i.e. there exists a positive natural number r such that F(r, i) = 1. Then there are two cases:

Case1: n is even. Then n = 2^k * t, where k >= 1. Then t = n/(2^k). Since n is at least 2 and 2^k is at least 2, 1 <= t < n, so P(t) is true. i.e. there exists a positive natural number r such that F(r, t) = 1. Also, t = F(k, n) because 2^k is a power of 2, so applying f to the power of 2 k times decreases the number by half until the number no longer contains any more powers of 2. So F(r, t) = F(r, F(k, n)) = 1. This means f is applied to F(k, n) r times. But F(k, n) means f is applied to n k times. So F(r, F(k, n)) = F(r + k, n) = 1. So there exists a positive natural number m = r + k such that F(m, n) = 1.

Case2: n is odd. Then f(n) gives 3n + 1, which is an even number according to my third point mentioned above. Call this number y. Since y is even, by case 1, there exists a positive natural number s such that F(s, y) = 1. But y = f(n). So  F(s, y) = F(s, f(n)) = F(s + 1, n) = 1. So there exists a positive natural number m = s + 1 such that F(m, n) = 1.

Then in both cases, there exists a positive natural number m such that F(m, n) = 1.
Since n is arbitrary, this means for all positive natural numbers n and, if P(i) is true, where 1 <= i < n, then P(n) is true.
Then for all positive natural numbers n, P(n) holds.

It looks like the induction works. But I have a feeling that there is something faulty that I did not catch about an assumption that I made. I will come back to this problem on another day to see if my brain can make some new progress.
     

Term tests are done!

I refrained from writing about term test 2  until now in case the questions are similar for both the morning and evening sections.

I got a little nervous when I flipped through the paper and discovered that there were only two questions for the test. Although that meant plenty of time, it could also have meant that each question was more challenging. With this in mind, I dug right into the first question. I first tried substituting every n in the unwinding equation with 2^k. But after a few unwinding, the equation soon looked very messy and complicated. So I reverted back to doing repeated substitution using n, keeping in mind that n is a power of 2. As I continued solving, the question reminded me of a tutorial question that involved sum of geometric series. Suddenly I was unsure of my approach to this question, because unlike the tutorial question where f(n) was n^2 (the time it takes to divide and recombine), the f(n) for this test question had a lower degree (I cannot remember exactly what it is). Therefore I was hesitant to use the sum of geometric series formula, thinking that perhaps there was a clearer way to do the question. However, since time was limited, and I could not see another immediate problem-solving approach, it was better to come up with an answer than nothing. Having an answer also helped me move on to the next part of the question, which was to prove that my answer was correct.

The second question was slightly easier to solve than the first in my opinion. We had recently handed in Assignment 2, so the questions on A2 were still fresh in mind. Since the second question had to be solved with the help of n-hat (the smallest power of 2 that is greater than or equal to n), I approached the question in the same way I did for A2.

Even though there were only two questions, I had just enough time to finish the test. Now I'm starting to worry about the level of difficulty of the final exam.

OMCOFS: a Fibonacci pattern

When I first scanned through assignment 2, I was somewhat afraid to dig into question 1. OMCOFS (a.k.a Odd Maximal Contiguous Ones Free Strings) seems complicated just by looking at its name. It sounds very scientific and high-level,  like something that would appear in science-fiction movies, something along the lines of UFO. But it turns out that these scary-looking binary strings are much more comfortable to deal with than UFOs. 

Since we have to develop a recurrence, I start the question by first listing some examples of OMCOFS with increasing lengths and trying to find a pattern. I do this by first writing down all the possible binary strings of a particular length, then pick out those ones that are OMCOFS. This is not hard to do for binary strings of lengths 0, 1, 2, 3, and 4. But it becomes more difficult for lengths of 5 or more. I know that there are 2^5 = 32 possible binary strings of length 5, but I can only list 31. I don't know which binary string I'm missing. In the end I had to turn to the wonderful, multi-purpose Python. With the help of a little Python program, I can finally get all the possible binary strings up to length 5 and pick out the OMCOFS.

n      number of OMCOFS      OMCOFS
0                   1                        empty string
1                   1                                0
2                   2                             00, 11
3                   3                       000, 110, 011
4                   5           0000, 1100, 0110, 0011, 1111
5                   8      00000, 11000, 01100, 00110, 11110,
                            00011, 11011, 01111

 

From the "number of OMCOFS column", it is obvious that the recurrence is related to the Fibonacci sequence, but with the numbers shifted upwards. Where the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5..., our recurrence starts with 1, 1, 2, 3, 5, 8... .

 

So we know that the recurrence is:

 

H(n) =    1                            if n < 2

               H(n-1) + H(n-2)    if n >= 2 

 

Now the question becomes: how do I explain why this recurrence correctly counts the number of OMCOFS of length n? It is not enough to just say I found it by looking at the pattern generated by the first few OMCOFS, and it will always be true. There has to be some pattern in the strings themselves such that the strings of length n-1 and n-2 somehow give rise to the strings of length n. But wait! This whole idea of strings sounds strikingly similar to something we did in lecture one day! As I furiously flipped through my past lecture notes, I came across the recurrence of "the number of binary strings without adjacent 0s". The idea is that, to obtain all the binary strings of length n without adjacent 0s, we append a 1 to the binary strings of length n-1 without adjacent 0s, and append a 10 to those of length n-2. With this idea in mind, I come back to our recurrence H(n). I discover that to obtain all the OMCOFS of length n, we just append a 0 to the OMCOFS of length n-1 and append a 11 to those of length n-2! The pattern is explicitly displayed by the OMCOFS I listed above, and it explains why, in numerically terms, we would have a Fibonacci pattern. The number of OMCOFS of length n is just the sum of the number of OMCOFS of length n-1 and n-2.

 

With the first obstacle cleared, I happily go on to unwind the recurrence. ^_^

 

Tutorial 5: Applying the Master Theorem

Today I will write about my thinking and problem-solving steps for question 1 of tutorial 5.

Question: A non-empty array A with integer entries has the property that no odd number occurs at a lower index than an even number. Devise a divide-and-conquer algorithm for nding the highest index of an even number element, or -1 if A has no elements that are even numbers. Use the Master Theorem to bound the asymptotic time complexity of your algorithm.

I start by parsing through the question to understand it:

If A has the property that no odd number occurs at a lower index than an even number, then all even numbers are gathered at the front of A, followed by all odd numbers.

I list some examples:

n = 1:  [3], [2]
n = 2: [4, 1], [1, 3], [6, 4]
n = 3: [2, 6, 5], [2, 6, 8], [5, 3, 7]
n = 4: [4, 3, 1, 7]

Now I reason about what the algorithm should roughly look like based on some scratch work with the examples.

If we do the question by brute force, we would simply be checking each element in the array until we reach an odd number. Then the index of the element before the first odd number is the one we want(*). The worse case for this approach is n, when we would have to check every element in the array.

Using the divide-and-conquer process:

We first have to divide the array into smaller pieces. I decide to divide it into two halves from the middle because for now, I don't see any reason to divide it into more than two pieces. Call the first half L1 and the second half L2.

Check the middle element.
(I): If it's odd, we know that all even numbers come before this element, so we recurse on L1.
(II): If it's even, we know that there could potentially be more even numbers in L2, so we recurse on L2.

Now I think about the base case. The least number of elements a non-empty array can have is 1. There are two cases for this array:

Case 1: the element is odd. Then we should return -1 since there are no even numbers in the array. But because we have to think about how the base case relates to recursion, instead of -1, generally we return the index of the element before the first odd number, as metioned above in (*).

Case 2: the element is even. Then we should return the element's index.

So in pseudo-code, we have:
(# A is a non-empty array, b is the beginning index, e is the end index)

evenIndex(A, b, e):                                   
    if b == e:
        if A[b] is odd:                        # case 1
            return b - 1
        else:                                         # case 2
            return b
    else: (b < e)
        mid = floor[(b + e) /2]
        if A[mid] is odd:
            return evenIndex(A, b, mid + 1)                   # corresponding to (I)
        else:
            return evenIndex(A, mid + 1, e)                   # corresponding to (II)

Everything other than the recursion takes constant time, so the tight bound for those parts is big-theta(1). The recursive part of the algorithm takes max{ T[floor(n/2)], T[ceiling(n/2)]}.

So T(n) = { 1                                   if n = 1
                    1 +  T[ceiling(n/2)]     if n > 1}

Then by Master Theorem,
a = 1, b = 2, d = 0.
So a = b^d.

Therefore T(n) = big-theta(log n).
                                                     
                                                                       

A Split Between Mathematical and Complete Induction

I've always thought that if a predicate can be proven with mathematical induction, then it can be proven using complete induction just as easily and vice versa. It turns out I was wrong. Although there is a cycle for believing in well-ordering, mathematical induction, and complete induction as in WO => MI => CI => WO, the cycle is at the top level. At the working level where we have to do the actual proof using induction, sometimes the trasfer between MI <=> CI is not so smooth.

Such is the case for the quiz question in tutorial 3. For a given recurrence, we are supposed to prove using MI that for every positive natural number n, T(n) >= c lg(n), for some positive real constant c. I noticed that in all of the lecture slides about proving big-O or big-Omega, we use CI. The reason is clear to see, since working with floors or ceilings of n over some nautral number means we can use the induction hypothesis to eliminate the floor or ceiling; ceiling(n/k) is less than or equal to n for a large enough n. Then we can break up lg(n/k) to get lg(n). But how about MI? How do we prove that [T(n) >= c lg(n)] => [T(n + 1) >= c lg(n + 1)]? Logarithms do not work well with addition, because it cannot be broken up easily. When I saw the question, I was at a loss. Eventually I couldn't resist the temptation to use the induction hypothesis for CI on n + 1 for a MI proof, which is definitely not the right way to approach it. But hey, I had a limited amount of time on the quiz! It is interesting and useful to discover that choosing the right induction technique paves the way for presenting a clear proof.

The first test

First of all, I'm really thankful that the term test questions looked familiar to me when I first opened the test paper. For some reason, I always have butterflies in my stomach right before a test. The calmness only comes after I start writing the test and discover that: Hey! I don't have a blank out on this question! I can actually do it!

When preparing for the test, I was a bit thrown off by the principle of well-ordering. I can follow the two examples provided on the lecture slides about well-ordering; but if it were up to me, I would have used Mathematical Induction or Complete Induction to prove the claim. Perhaps it's because we have been exposed to MI and CI longer and have done more proofs using these two techniques in tutorials and A1. Or perhaps the idea of somehow re-wording the claim I want to prove so that it becomes related to a subset of natural numbers seems strange to me. Anyhow, it is probably a good idea to get more practice on well-ordering in order to get better at it.

The sample test really helped me focus on what I should study for. Before, I was looking at the closed form of Fibonacci sequence and got very nervous about deriving something similar to phi. But after doing the sample test, I decided to direct more attention to familiarizing myself with the techniques of induction, which turned out to be the core of the term test.

A1 accomplished!

11:59 pm. Somehow it sounds like an omnious foreshadowing that only we, the students, who depend on the minute-hand of the accurate MarkUs clock know about. Having fought an intense battle against that clock last year in CSC165, I am quite pleased to have finished A1 well before its deadline. From what I remember in CSC165, it was not because of procrastination that led my partners and I to race against time, but because we were always unsure of the solutions that we had generated, and thus the urge to change what we have written until the last minute. Having experienced that, I found this first assignment to be much clearer (of course, after leaving myself a good amount of time for discussion and question).

Surprisingly, the inequality question was not as easy as I thought it would be.  When I first looked at the question, I thought of it as just consisting of purely mathematical reasoning that gets from the left side of the equation to the right side. However, getting there is not as simple as 1 + 1. I had to go back to the 165 Big-O section to review the techniques to tackle these inequalities. But even then, there was no elegant way that lets me solve the problem without assuming in some part of the proof that n >= a certain natural number. The following lecture that talked about inequalites cleared my doubt.

Another question that yielded a different type of uncertainty was question 4. I was pretty sure that I was on the right track after discussing with my friends and digging into the hint provided in 4) about using a stronger claim to prove the desired claim. However, the proof just looked longer than it should be because of the large number of cases that it needed to be divided into. Thanks to the professor's office hours and my friend who continued waiting in-line when I had to go to another class, I was assured that sometimes, a proof needs to be a bit longer in order to be convincing.