Can it ever be impossible to invert a PRNG?
I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths? Or is this mathematically and logically impossible?


No, it's not a coincidence. The period is related to the state size, and a smaller sample cannot allow unique inversion due to the fact that every shorter number sequence appears in the total output of MT (with equal frequency to boot).

In general the same does not have to be true. A PRNG can use its state "wastefully" in such a manner that not every state is possible and inversion can happen much earlier than state size. Or it can have correlations that break it even without inversion. Contrarily, an actual cryptographically secure PRNG is expected to produce much more output than the state size without ever being invertible.

So I doubt your equation holds without additional assumptions.