Posts Tagged ‘Collatz Conjecture’

Dr. Paul Stanford departed from our recent lectures on applied mathematics and contest preparation to give our students a glimpse into the fascinating world of pure mathematics.  Dr. Stanford is particularly skilled at teaching deep ideas without the need to resort to complex algebra, I’ll attempt in this recap to do his lecture a small bit of justice.

Dr. Stanford began with one of the simplest concepts, points on a plane and arrows connecting those points.  Many of these arrows considered together and connecting a set of points yield all sorts of interesting directed graphs or “digraphs.”  This idea becomes more interesting when restrictions are imposed such as the rule that no two arrows can originate from the same point.  When a sequence of arrows loop back upon themselves they form a shape like a “hairy circle” from the title of the lecture.

Dr. Stanford further restricted the cases with the following rules:  no two arrows can connect to the same point and no symmetry is allowed.    These restrictions yielded only four possibilities including those with only a single point connecting back on itself and the possibility of having no points or arrows at all.

Dr. Stanford then proceeded to show how basic arithmetic could be carried out in each of these four systems by shifting along the chains of arrows and by considering the very special case of the arrow that points back to its own origin.

In the second half of the lecture, Dr. Stanford built upon this foundation as he introduced the Collatz Problem:

Think of a number.

If it is even, divide by two.

Otherwise, triple it and add one.


Does this always reach one?

Dr. Stanford lead the students through multiple examples using positive integers, some of which filled both whiteboards but eventually came back to one.  In fact Dr. Stanford told us that while this process always yields one for numbers from 1 to 2.7 \times 10^{16},  nobody has proven that it is true of all positive integers!  Dr. Stanford reminded the students that for mathematicians multiple examples are not “proof” and that numbers even as large as 23 thousand, trillion are not especially large to mathematicians.

However, when Dr. Stanford started the Collatz problem with negative integers, it was common that loops would appear.  Drawn on the board, the chain of calculations was strangely similar to the hairy circles from the previous lecture.  This lead to a discussion of how one could detect when loops appear in an algorithm.  At this point the lecture began to  bridge between pure mathematics and some real problems in computer science.

One method for detecting a loop would be to track and remember every point in the path but this would burden even the most powerful computer.  A more clever method is the “tortoise and the hare” strategy.  This involves sending two runners through the system, one moving twice as quickly as the other.

Dr. Stanford proved how this method would eventually prove the existence of a loop and how a second tortoise could confirm the exact point where the loop begins.

The two lectures formed an exciting and satisfying trip through the world of numbers.  If I have misrepresented or ignored pertinent points from the lecture please feel free to mention them in the comments section below.

Read Full Post »

%d bloggers like this: