Practice

When given a particular problem to solve you need to be able to approach the task in a logical manner and to find ways to break up the problem into smaller parts. For all of the business applications you will be asked to design there will always be many ways to provide the required solution with some resulting in more efficient code than others. How good you are as a programmer will be demonstrated by how you go at picking out one of the better ways of solving the problem.

When it comes to other areas such as Artificial Intelligence, you may not be able to develop a complete solution as there can be any unknowns which cannot really be dealt with properly until you get a lot more information. That's why the AI development process is iterative with versions being implemented and tested so as to obtain more data to reduce the number of unknowns for the development of the next version.

One way to test yourself on your ability to break complex problems down into smaller parts in order to work efficiently toward a solution is to pick one of the many unsolved mathematical conjectures and to see how far you can get in breaking that problem into smaller parts and seeing how many of them you can solve. If you do this before you read up on what work has already been done on the problem after you make your best effort then you will be able to see how well you did with your problem solving attempt.

To give myself some practice in problem solving I selected the Collatz Conjecture. I found a reference to this on a homework site that basically asked the students of whatever class it was to analyse the problem. The site didn't give any further information beyond what the conjecture is and so I decided to see how far I could get with it before looking at what work had already been done. The following text apart from the last paragraph was written in about an hour while I was actually doing my analysis of the problem and generating the partial solutions that I mention.

Given a positive integer n, if it is odd then calculate 3n+1. If it is even, calculate n/2. Repeat this process with the resulting value. The unsolved question about this process is: If you start from any positive integer, does this process always end by cycling through 1,4,2,1,4,2,1,? Mathematicians believe that the answer is yes, though no one knows how to prove it.

Let's start by looking at the sequence we get with a few starting values (we'll skip over those that are already represented in prior sequences just by changing the starting point in the sequence):

1,4,2,1,4,2,1,4,2,1,
12,6,3,10,5,16,8,4,2,1,4,
9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,
15,46,23,70,35,106,53,160,80,40,20,
19,58,29,88,44,22,11,34,

So what do we know so far? Well looking at these sequences we know that if the sequence ever drops to 20 or less that sequence will end up cycling through 4,2,1,4,2,1 because with the sequences we have looked at we have covered all of the sequences starting with all of the numbers 1 through 20 and have shown that they all end up with this sequence.

So the question can be changed to whether the calculation will always at some point provide us with a single digit number. For all even numbers where we are dividing by two, each division will either give us another even number to divide again or it will give us an odd number. For those numbers that are powers of two we will therefore always end up eventually with 8,4,2,1 while for even numbers not a power of two we will eventually end up with an odd number. For the odd numbers, multiplying by three and adding one will always give us an even number. So there are two ways to get to an even number but only one way to get to an odd number.

Since all the even numbers either end up with one of the above sequences or give us an odd number that hasn't been tested yet, we can say that if this conjecture can be proved for all odd numbers then it will automatically be true for all even numbers as all even numbers can be divided by two enough times to eventually give an odd number.

We can use the following JavaScript code to show that the conjecture is true for all numbers up to and including 1000 as the code logs 490 entries that say true without ever getting caught in an infinite loop (as would happen if it found a number where the conjecture wasn't true). Every odd number under 1001 will eventually reduce to a number under 21 as this code demonstrates and from what we looked at above every number under 21 soon reduces to the 1,4,2,1,4 sequence.

var collatz = function(n) {
if (n < 21) return true;
if (n%2===0) n/=2;
else n =n*3+1;
return collatz(n);
};
for (var i = 21; i<=1000; i+=2)
console.log(collatz(i));

We can replace the 21 references in this with 1001 and specify a bigger number in place of the 1000 (eg. 2000) to show that those numbers eventually reduce to smaller numbers that we have already proved will end in that repeating sequence.

Now we can take another approach to so as to find another partial solution to this problem. In the 50% of cases where the number two after an odd number is even, the number after that will always be smaller than the odd number we started with as (3n+1)/4 is always less than n and if the numbers get smaller then they will eventually fall below the biggest number we have tested or will end up with a smaller odd number than the one we started with. For the 50% where the number two after an odd number is also odd there is a 50% chance that the number two after that will be even and that therefore the next odd number will be smaller than than the last one (but not necessarily smaller than the one before).

This leaves us with two possibilities that we haven't yet proven as being impossible to occur.

  1. That there exists a sequence which will eventually return to the same odd number that we started with and therefore will simply loop through the same sequence over and over.
  2. That there exists a sequence of alternating odds and even numbers that rarely generates even numbers that are not divisible by a greater power of two and which therefore has the numbers just continue to get bigger and bigger with only an occasional dip.

With this second case we would have an infinite series of different numbers that on average just get bigger except that in an infinite series of numbers you will eventually get one that is a power of two which will therefore divide down until you get back to the 4,2,1 sequence. The sequence before it gets to such a number can be infinitely long but the probability of a number satisfying any condition occurring in an infinitely long string of numbers is 100% provided that the conditions for such a number can occur at all (and we know that there are positive integers that satisfy this condition). So an infinitely long sequence of numbers that doesn't eventually start looping cannot occur.

So we have eliminated another alternative. That only leaves the possibility of huge integers forming their own loop that never falls below the smallest odd number in that loop as a possibility that we haven't ruled out.

Note that I wrote all of the above prior to doing any investigation into what work has already been done on this. Upon reading up on other work I found that all numbers up to 5.7641018 have been tested and found to lead to the 4,2,1,4 sequence. Also it has apparently been demonstrated that each odd number is on average 3/4 of the previous odd number and that there are two division steps for every multiplication step for almost all possible starting values. It has also been proven that if the looping options I didn't rule out to occur that the sequence of numbers before it starts to repeat must be at least 35400 in length (as compared to the three in the case that every number tested so far reduces to). So basically in my analysis I determined which possibilities had not yet been eliminated but not to the same level of detail as has been determined through far greater analysis.

 

This article written by Stephen Chapman, Felgall Pty Ltd.

go to top

FaceBook Follow
Twitter Follow
Donate