More on Collatz Function(ssssss)

Followup on yesterday's post: I moved from Scheme to C++ and wrote a program that will keep testing Collatz functions generated with fibonacci numbers until it runs out of memory. It verified that functions generated for the first 22 numbers in the series (1, 2, 3 (erm, actually - see below), 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657) work - at least in the range 1 - 100000. After that the multiplications are larger than the native unsigned long type, so C++ can't handle it anymore without loading helper libraries. Since I'm not too familiar with these, this seemed like a good place to stop and get back to fulltime work studying for my algorithms exam.

By an interesting conicidence, the final project (due Wednesday) in that class involves large integer multiplication, so working on that problem is directly related to optimizing the tester program that I wrote yesterday. Serendipity: I've just solved my motivation problem in Algorithms! :-)

The frustrating thing about all of this, of course, is that none of it verifies anything. Without a formal proof, for all I know it's a huge coincidence. But it's been interesting - and I look forward to thinking about the problem more seriously over the break.

Incidentally, my other, much-neglected blog, though still collecting cobwebs as I write, will be revived on 16 December. (Exams finish for me on the 14th, and I'm going to take a day off to watch TV and drink beer on the 15th.) Knuth's book(v.2) is turning out to be extremely helpful for the final project in Algorithms. I'm reading the relevant sections (4.2, 4.3) in volume 2 (which deal with fast multiplication) now. It's definitely a book I (and probably every serious CS student) should read, and anyway, it's bad to start things and not finish them - especially if you're like me and you have self-discipline problems.

[NOTE: I feel the key to all this has something to do with the function for 3. If you look at yesterday's code, you'll notice that 3 doesn't actually fit the generalization I came up with. 1 is trivially true, and 2 is the cannonical example. The generalization I came up with based on Roshan and Will's function, though, is really just sort of what I wanted it to be - not what's actually on paper. In fact, the program I wrote diverges for 3. Interesting that it works for all Fibonacci numbers (tested so far) BUT that one. The explanation seems to have something to do with the difference between the divisor and remainder. This must always be 2 or more. For all subsequent numbers, there are plenty of such remainders, but for three a difference of 2 is the only case. Now, the generalization that there is "A Collatz" function for every fibonacci number seems to be true (at least, so far), but you have to write the function for 3 differently. Why? ]