A generalized algorithm for Collatz-like "hailstone" sequences
I've always been fascinated with Collatz sequences. Well today, while thinking about multiplicative groups, I realized that under certain constraints they too could be used to generate similar "hailstone" sequences. Moreover, it *should* be fairly easy to prove that all such sequences eventually reach one and that no intervening sequences are cyclic. Unfortunately, my forte is definitely *not* mathematical proofs, so I'll just have to leave it up to someone else to work that out! Another interesting property of the generator is that it can be used to calculate primitive roots - not efficiently, mind you, but it does at least demonstrate the connection with multiplicative groups...
Anyway, here's a basic overview of how it works:
(1) Pick a natural number, and call it the "divisor".
(2) Pick another natural number coprime to divisor and call it "counter".
(3) Set "accumulator" to one.
(4) Add the counter to the accumulator.
(5) Divide accumulator by divisor until the two are coprime.
(6) If the accumulator equals one, increment the counter until it is coprime with the divisor.
(7) Return the value of the accumulator.
(8) Go to step (4) to obtain next value in the sequence.
See below for a link to an implementation of the generator and demo program. Note that for sake of clarity, initialization of the generator and incrementation of the counter is done in a very simple fashion. If desired, these could be modified (using GCD calculations) to increase the overall period of the generator (besides allowing it to reveal more primitive roots); the important thing to remember is that the divisor and counter must always be coprime...
Cheers!
