ConwayLife.com

Given constants n, p, and k, define the generalized Collatz function as:

f(x) = x/p if x is divisible by p
f(x) = n*p+k otherwise

The standard Collatz function, n=3, p=2. and k=1, is believed to settle into a p3 oscillator for any starting x: 4. 2. 1,...
Just like OCA, many parameters n,p,k cause initial values to explode without bound. Examples for (n,p,k) are (5,2,1) and (2,3,1).
However, there are may also be many that exhibit similar behavior to (3,2,1).

Any opinions?

The title is somewhat misleading. It implies something analogous to a CA that can emulate generalized Collatz functions.

testitemqlstudop wrote: f(x) = n*p+k otherwise

Typo: I think you mean f(x) = n*x+k.

I'm not entirely sure what you're asking here. I guess you could think of this as an infinite state 0D CA, though that's not very interesting from a CA standpoint.

You may also be asking how to implement it as a 1D CA. This may help illustrate why the problem is harder than it looks. Essentially it is applying a rule to a potentially infinite memory, as a CA or Turing machine would do, only the infinite memory is represented as a single integer value, lending the question its deceptive simplicity.

Let's stick with the original 3n+1 form of the problem.

If the number is encoded as bits, you test if the rightmost bit is 0 or not and remove it if it is, shortening the string. Otherwise, you multiply by 3, which is like adding the value to itself with one left shift and then add 1, which is like flipping each 1 to 0 until you get to the rightmost 0, which you change to 1.

Adding a number to itself shifted one bit can be implemented easily with a finite state machine going right to left. It's not too hard to see how to embed this operation in a CA like framework (but CAs are Turing complete, so no surprise there).

Two thoughts. Looking at the Collatz conjecture in terms of bit strings is at least useful in developing intuition for why it is hard, though it doesn't prove anything. Conceivably, it would give you a better analytical framework for attacking it, though I don't see how.

Finally, (since you requested opinions) I'm not sure generalizing it is that enlightening given that it looks nearly intractable in its simplest form.

Hmm, there is one thought I had. If you known that the current value of x contains a specific bit substring, e.g.1001, then you can say something about what it will look like in the next step. The hard cases is when you need to calculate 3n+1. The first question is whether the carry propagates from the suffix to the right. The second question is whether the carry propagates when adding 1. So I think representing it as a bit string could help analyze cases.

Starting at 27 looks like this in binary: How about ternary representation? Then 3n is trivial, but testing even/odd is harder.