Surgery is making me boring though I'm guessing most of you won't mind. Also, I thought that this was a good little problem to get you all up to speed in Scheme so it should work well in ML also.
For this assignment you will be doing some simple coding in ML just to make sure that you understand how things work. For fun, I'm going to have you play with the 3n+1 problem. This is a deceptively simple little problem, but it is gets a fair bit of attention because no one has managed to prove how it behaves. The basic idea of the problem is this. You write a function that takes one integer argument, n. If n is 1, you return something. If it is not 1 then it calls itself and the value of the argument it uses depends on the whether n is even or odd. If n is even then the call should be made with the value n/2. If the number is odd, the argument to the call is 3*n+1. You will write several versions of this function that return different things and then some other functions that use those.
To see how this works, lets consider the example of a call with the value 3. That gives us the following series in the calls: 3, 10, 5, 16, 8, 4, 2, 1.
The reason this function is interesting is that no one has proved that it stops for all positive integers. Note that when the value is odd it calls itself with a bigger number. When the value is even, it calls itself with a smaller number. If the number is ever a power of two it quickly drops back down to 1 and the method stops. This happens for every number that has ever been tried with this function, but that's far from proof that it happens with all numbers.
I want you to write two versions of the 3n+1 problem. The first, which you should define as tnp1, returns how many iterations had to be done before it got to the value 1. The second version, which you should call tnp1list, should return a list of all the elements in the series. So if you call them with 3 as an argument you get something like this.
- tnp(1,3);
val it = 8 : int
- tnp1list(3);
val it = [3, 10, 5, 16, 8, 4, 2, 1] : int list
Once you have those two functions, I want you to write one more function and call it testvals. This function will take three arguments. The first is a function to test. The second and third are the starting argument value and ending argument values. It then calls the supplied function with one argument whose value goes from the value of the first number to that of the second number. It returns a list that contains all the return values from those calls consed together.
This idea of this function is that you can call it with tnp1 and a range of values to see how many iterations those values take to exit. So if you run (testvals tnp1 1 99) it will return a list that has how many iterations were done for the values 1 up to 99 in the 3n+1 problem.
Submission: You will use my submission application to turn in your solution to this. It should be a single text file with a .sml ending on it. To grade it, I will run it with sml and make sure that it returns the right values for a number of different calls to the different functions.
Extra Credit: For extra credit, find a way to merge your two versions of the 3n+1 problem into a single version. To give you a hint on how you might do this, you could pass in another argument to the function and have it be a function.