Given some number $n$ and a seed number $s$<$n$, I want a random number generator (RNG) that will go through all integers <$n$ before coming back to $s$. The resulting random number must be roughly uniformly distributed (which of course it will be if you go through the entire sequence, so I mean for any "large" subsequence) and roughly un-autocorrelated. Furthermore I want the RNG to be "efficient" in that it takes up little memory and little computation. Perhaps I can say that it is $O(1)$ w.r.t. $n$ in terms of memory and computation.

For instance, I can think of a RNG right now that will fulfill the former requirements, but not the latter: Create a list of all numbers $0$ through $n-1$. "Mark off" the seed number $s$. Then take a random number $r$ from a Mersenne Twister RNG, move $r$ numbers to the right and if that number hasn't been marked off report it back and then mark it off. Continue the process until you've marked off all numbers in the list. - This method will report back non-repeating, un-autocorrelated integers, but will be super memory and time intensive.

I imagine the ideal answer to be some sort of small equation to provide the next number in the sequence based upon this number (or perhaps the last few).

Can such a RNG be proven to exist? Are such specific RNGs know to exist? Can their existence be disproven?

Editorial note: If anyone reading has super edit power... please feel free to clean up my post to make me sound more mathy (I am but a lowly engineer). Retag me too please.

Given some number $n$ and a seed number $s \lt n$, I want a random number generator (RNG) that will go through all integers $\lt n$ before coming back to $s$. The resulting random number must be roughly uniformly distributed (which of course it will be if you go through the entire sequence, so I mean for any "large" subsequence) and roughly un-autocorrelated. Furthermore I want the RNG to be "efficient" in that it takes up little memory and little computation. Perhaps I can say that it is $O(1)$ w.r.t. $n$ in terms of memory and computation.s$

For instance, I can think of a RNG right now that will fulfill the former requirements, but not the latter: Create a list of all numbers $0$ through $n-1$. "Mark off" the seed number $s$. Then take a random number $r$ from a Mersenne Twister RNG, move $r$ numbers to the right and if that number hasn't been marked off report it back and then mark it off. Continue the process until you've marked off all numbers in the list. - This method will report back non-repeating, un-autocorrelated integers, but will be super memory and time intensive.

I imagine the ideal answer to be some sort of small equation to provide the next number in the sequence based upon this number (or perhaps the last few).

Can such a RNG be proven to exist? Are such specific RNGs know to exist? Can their existence be disproven?

Editorial note: If anyone reading has super edit power... please feel free to clean up my post to make me sound more mathy (I am but a lowly engineer). Retag me too please.

Given some number $n$ and a seed number $s \lt n$, I want a random number generator (RNG) that will go through all integers $\lt n$ before coming back to $s$. The resulting random number must be roughly uniformly distributed (which of course it will be if you go through the entire sequence, so I mean for any "large" subsequence) and roughly un-autocorrelated. Furthermore I want the RNG to be "efficient" in that it takes up little memory and little computation. Perhaps I can say that it is $O(1)$ w.r.t. $n$ in terms of memory and computation.

For instance, I can think of a RNG right now that will fulfill the former requirements, but not the latter: Create a list of all numbers $0$ through $n-1$. "Mark off" the seed number $s$. Then take a random number $r$ from a Mersenne Twister RNG, move $r$ numbers to the right and if that number hasn't been marked off report it back and then mark it off. Continue the process until you've marked off all numbers in the list. - This method will report back non-repeating, un-autocorrelated integers, but will be super memory and time intensive.

I imagine the ideal answer to be some sort of small equation to provide the next number in the sequence based upon this number (or perhaps the last few).

Can such a RNG be proven to exist? Are such specific RNGs know to exist? Can their existence be disproven?

Editorial note: If anyone reading has super edit power... please feel free to clean up my post to make me sound more mathy. Retag me too please.