2
Output an infinite sequence of positive integers, such that, for each element in the sequence, all positive integers that have not yet been output have a positive probability of being chosen, and no value is repeated.
For example, if the first integer is 3
, then 3
may not be output again, but all other positive integers have a positive probability of being chosen for the second integer.
Acceptable output methods
- Writing to STDOUT, with a consistent, unambiguous separator between integers (such as a newline), with output prior to termination of the program
- A named or unnamed function which returns an infinite iterable (such as a Python generator)
- A named or unnamed function which outputs the sequence one integer at a time each time it is called within a single execution of the program
- A named or unnamed function or program which outputs the next integer in the sequence when called with the previous integer(s) as its sole argument(s) (the first call may either take no arguments or take a seed argument, which may be included in the arguments to later calls)
Rules
- There will be no input except an optional seed value, which will be an infinite sequence of random bits.
- Submissions must be capable of producing different outputs given different initial conditions (outputting the same sequence every time is not acceptable).
- Each element of the sequence must be chosen randomly out of the valid elements (positive integers not already present in the sequence).
- You may assume that you have infinite memory available.
- You may assume that any real numbers returned by a PRNG are infinite-precision. In other words, if you have a function called
rand
that returns a random value in[0, 1)
, you may assume every real value in that interval has a positive probability of being chosen, rather than just the subset of the reals that are representable with floats. - Each integer must be output in a finite amount of time after the last integer (so you can't wait until program termination to output part of the sequence). The first integer must be output in a finite amount of time after the program is started or the function is called.
2So, shouldn't the first number (and all the following ones) have an infinite number of digits? – Arnauld – 2017-05-21T21:07:02.527
@Arnauld Integers are finite. You're outputting an infinite number of integers, not integers with infinite length (which don't exist). – Mego – 2017-05-21T21:09:24.957
@LuisMendo I'm not sure what you're asking. – Mego – 2017-05-21T21:10:14.327
4What I mean is that if the sequence really is infinite (which of course is not going to be the case in practical implementations), the number of digits of the numbers tends to infinity. And if each element of the sequence is chosen randomly out of the valid elements, I don't see why the first numbers of the sequence should be small ones. But I may be missing something. – Arnauld – 2017-05-21T21:29:05.317
@Arnauld There is no requirement that all valid integers have equal probability (in fact, there can't be, because then that probability would be infinitesimal). It's perfectly valid to have the probability of an integer
n
being chosen be1/n
, which would cause smaller values to have much larger probabilities than larger values. – Mego – 2017-05-21T21:30:21.907Let us continue this discussion in chat.
– Mego – 2017-05-22T05:46:37.057Related. – Martin Ender – 2017-05-22T06:46:20.820
Let us continue this discussion in chat.
– Jonathan Allan – 2017-05-22T18:51:59.730