Homework two at Udacity’s CS101 gave a little shock to more than a student. The third loop of question 5 was:

n = any positive integer
while n != 1:
    if n % 2 == 0: # the % means remainder, so this tests if n is even
        n = n / 2
    else:
        n = 3 * n  +  1

And the question was: will this loop end sooner or later, will it loop forever, or doesn’t anybody know?

To the abashment of many a student, the answer is “nobody knows”. Many people have tried running the loop with different values of n, you could even try to run it with the largest integer that your programming language and your hardware allow, and the loop always end, so why isn’t the correct answer “yes it ends”? This is a very good introduction to the concept of conjecture. According to the definition of the Merriam-Webster’s dictionary, a conjecture is:

2.c : a proposition (as in mathematics) before it has been proved or disproved

So here is the tricky part: no matter how hard anyone has tried, it has worked, but nobody has yet find a mathematical proof that that loop will end. This very simple little problem even has a proper, famous mathematical name, it’s the Collatz  conjecture. If you search the web, you can find much about it. Very interesting is the Wolfram MathWorld’s page on the Collatz Problem: if you look on the right sidebar, you can find links to demo projects on this little tricky conjecture.

Some may argue that this all has little to do with CS101, learning about programming, but I think it was indeed quite appropriate: a high-level course should not only give you standard information on the subject, but it should also open your mind to new ideas, give you new paths to explore, expand your knowledge. I think that the students that were already familiar with the idea of a mathematical conjecture were immediately hinted by the “Unknown, to anyone” formulation of the third option, and even if they didn’t know of this specific problem, they might have started searching the web for something like “3n +1″. Google it and the problem shows up at the very top. Other students, who might have never heard of what a conjecture is, now have an idea, so I think that, even if it wasn’t something dealt with in the lectures, it is still a great way of teaching, because it asked students to actively look for something. Again, kudos Udacity!

A word to the wise: like so many other open problems in mathermatics, this conjecture is very easy to state, but it doesn’t mean it will be easy to prove, so you’d better think twice before you dive in and try to solve it!