0

I need a simple as possible deterministic random number generator from 0-N that I can chuck a number from 1-Infinity into and get a random number out of, without it the pattern repeating over and over again.
Is this even possible? If so what would be a simple example of one? It doesn't have to be safe in any way or have an especially good distribution.

user2741831
  • 225
  • 1
    For example the function $f_N:\mathbb{N}\mapsto{0,1,\dots,N}$ that maps $x\in\mathbb{N}$ to the $x$th digit in the sequence of every base $N-1$ number (in ascending order). For example, if we wanted such a number between $0$ and $9$ we use $f_{10}:\mathbb{N}\mapsto{0,1,\dots,9}$ which maps $x$ to the $x$th digit in the sequence $0,1,2,3,4,5,6,7,8,9,10,11,\dots$. – Peter Foreman Dec 31 '19 at 19:41
  • There is an excellent section on random number generators in Numerical Recipes (chapter 7 in the 3rd ed). – almagest Dec 31 '19 at 19:42
  • here is an introduction to pseudo-random number generators. – lulu Dec 31 '19 at 19:55
  • @Peter Foreman, wouldn't that repeat after 9? – user2741831 Dec 31 '19 at 20:05
  • 1
    Every random number generator must repeat a subsequence. A good algorithm is to take sequential digits of $\pi$, every which subsequence appears infinitely often. – David G. Stork Dec 31 '19 at 20:13
  • @user2741831 Why would it repeat after $9$? The sequence concatenated would be $012345678910111213141516\cdots$. It does not repeat after $9$. – Peter Foreman Dec 31 '19 at 20:16
  • PI is a pretty good idea, thanks, but I hoped for a simpler solution – user2741831 Dec 31 '19 at 20:17
  • @PeterForeman can you explain it again? I don't really now what you mean "with hat maps x∈N to the xth digit in the sequence of every base N−1 number (in ascending order)" I though you just meant the last digit of the number in hexadcimal (if N is 9 for example) – user2741831 Dec 31 '19 at 20:20
  • @user2741831 If we want a 'random' digit in the set ${0,1,\dots,N}$ we can form the sequence of every base $N-1$ number which starts $0,1,2,\dots,(N-1),1:0,1:1,\dots,1:(N-1),2:0,\dots$ then just choose the $x$th digit appearing in the sequence for our 'random' number associated to $x$. – Peter Foreman Dec 31 '19 at 20:24
  • Now it makes sense, thanks a lot @PeterForeman – user2741831 Dec 31 '19 at 20:37
  • @PeterForeman: If your comment was meant for me... Your sequence "$0123...$" is precisely what a random sequence is NOT. Give me a minute or two and i could tell you the value of the trillionth digit, for instance before proceeding algorithmically. The guarantee of repeating subsequences is based on the pigeon-hole principle. – David G. Stork Dec 31 '19 at 20:46
  • @DavidG.Stork I was just answering the OP's question. I assume that when the OP states "the pattern [is] repeating over and over again" they just means that the associated sequence is eventually periodic. The sequence I provide given by$f_N$ is not eventually periodic because of the irrationality of the Champernowne constants. I chose this function in particular as the output is also uniformly distributed. – Peter Foreman Dec 31 '19 at 21:05
  • @PeterForeman that is correct – user2741831 Dec 31 '19 at 21:08

0 Answers0