The Marsaglia Limit Cycle Theorem

Or something like that. This is really the "Marsaglia Limit Cycle Theorem for LMD2 and Later". I don't know what else to name it. Anyway here's the proof that you always end up in the bright region as opposed to the dark region when considering Marsaglia oscillators which have  (2^(N-1))<=A<(2^N) with X and C both being N bits, implying an oscillator state of 2N bits. I could probably make it more succint, but I think you'll get the idea.

Again, we're talking about multiply-with-carry oscillators, which I prefer to call "Marsaglia oscillators".

Consider again S, the seed of cycle 2. The theorem says that S is the maximum integer which lives on the steady state part of the Marsaglia oscillator's cycle, in other words, the largest integer that you can produce more than once when starting from an arbitrary integer.

---

S=((A-1)*(2^N))+((2^N)-1)

---

First of all, it should be clear that any integer I on [0, S] will iterate to another integer on [0, S]. The reason is that the maximum X value in this range is ((2^N)-1). If you multiply that by A, you get ((A*(2^N))-A). But C is by definition at most (A-1), so you can never actually get the new C greater than (A-1). So if we start in the bright region, we stay there.

Now in the dark region, all the integers are on [S+1, (2^2N)-1]. If we iterate the maximum value on this interval, which happens to be the one which produces the maximum possible output, we get ((A*((2^N)-1))+((2^N)-1)), or ((A+1)*(2^N)-(A+1)). Thus the maximum new C value is just A. We're almost into the bright region.

Let's iterate again. If the maximum possible X value after the first iteration is ((2^N)-1), then AX is going to be (A*((2^N)-1)), or ((A*(2^N))-A). If the maximum new C value after the first iteration is A, then it looks like we can end up with (A*(2^N)), after adding it to AX. But we can't. Because when that first new C value is equal to A, then its associated X is ((2^N)-(A+1)). Since A is at least (2^(N-1)) based in all the LMDx oscillators after LMD1, X must be less than A. Which means that after the second iteration, the maximum new C is now (A-1). Thus we're in the bright region, after at most 2 iterations.