Infinite Sequence of Unique Random Integers

Question

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.

• Arnauld: So, shouldn't the first number (and all the following ones) have an infinite number of digits?
• user45941: @Arnauld Integers are finite. You're outputting an infinite number of integers, not integers with infinite length (which don't exist).
• user45941: @LuisMendo I'm not sure what you're asking.
• Arnauld: What 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.
• user45941: @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 be 1/n, which would cause smaller values to have much larger probabilities than larger values.

Answer 1

Python 3, (削除) 137 (削除ここまで) (削除) 127 (削除ここまで) (削除) 123 (削除ここまで) (削除) 138 (削除ここまで) (削除) 117 (削除ここまで) (削除) 99 (削除ここまで) 98 bytes

A named or unnamed function which returns an infinite iterable (such as a Python generator)

from random import*
def f(x=[],y=1):
 while y in x or.5<random():y+=1
 yield y;yield from f(x+[y])

• -10 bytes by putting the conditional in one line (Thanks, @Dennis)
• -4 bytes by initializing r at the beginning of the loop
• +15 bytes by remembering numbers can contain zeroes...
• -21 bytes by renaming randint, and moving the condition in the head of the inner loop
• -18 bytes by switching to a functional paradigm
• -1 bytes by moving from or ...>.5 to .5<random() (thanks, @JonathanAllan)

• Dennis: The entire if statement can go on a single line.
• L3viathan: @Mego Just switched to Python 3, I'm sure I can save characters elsewhere.
• L3viathan: @JonathanAllan I guess I did... It wasn't intentional, it happened while I made it a generator after having read your answer... My Aceto answer is then also inspired by your answer.
• Riker: That is a lot of golfing. nj

Answer 2

MATL, 10 bytes

`x1r/XktGm

Try it online!

Explanation

A candidate output, say n, is generated as ceil(1/r), where r is uniformly distributed on the interval (0,1). This ensures that every positive integer has a positive probability of being chosen as n (assuming infinite precision for r).

If n coincides with any of the previous numbers (taken as input) the process is repeated.

` % Do...while
 x % Delete. This deletes the candidate number from the preceding iteration.
 % In the first iteration it takes input implicitly and deletes it.
 1 % Push 1
 r % Push random number uniformly distributed on (0,1)
 / % Divide
 Xk % Round up (ceil). This is the candidate output. It will only be valid
 % if it's not present in the input
 t % Duplicate
 G % Push input: forbidden numbers
 m % Ismember. This will be used as loop condition
 % End (implicit). If condition is true, next iteration
 % Display (implicit)

Answer 3

Python 2, (削除) 93 (削除ここまで) 87 bytes

-3 bytes thanks to Uriel (move r=1 to beginning of the loop to avoid initialisation)

from random import*
a=[]
while 1:
 r=1
 while r in a or.5<random():r+=1
 a+=[r];print r

Try it online!

Keeps adding one while the number is either unavailable or a coin flip comes up heads.
Low numbers have much more probabilistic weight than high numbers.

• Uriel: you can cut 3 bytes by moving the r=1 to the beginning of the loop and deleting the third line

Answer 4

JavaScript, 62 bytes

A full program that picks a single random value in [0 .. 1] and expressed it as a continued fraction, omitting elements that have been encountered before. This would produce a really infinite sequence if the initial value had an infinite precision. In practice, we are limited to what can be expressed in IEEE-854 format.

for(x=Math.random(),o=[];;)o[n=1/x|0,x=1/x-n,n]||alert(o[n]=n)

Demo

Here is a demo limited to 50 values and writing to the console instead.

for(x=Math.random(),o=[],i=0;i<50;)o[n=1/x|0,x=1/x-n,n]||console.log(o[i++,n]=n)

• Jonathan Allan: Would this output a single value in finite time in the imagined scenario where we have infinite precision?
• Arnauld: @JonathanAllan Actually, I think so. A random real r with infinite precision must be an irrational number that maps to an infinite sequence of random integers An such that r = A0+1/(A1+1/(A2+1/...)), so any 'new' value of An can be picked in finite time.
• Jonathan Allan: That seems like you are suggesting that 0.5 is not a real number :/
• Arnauld: The infinite precision really is important here. It assumes that the PRNG can support infinite precision and can't possibly generate exactly 0.5. Does that make sense? (It's more like 0. followed by an infinite number of random digits.)
• Jonathan Allan: Yeah I think the premise of infinite precision makes the question impossible to specify clearly to be honest. If 0.5 has zero chance of being output then so does every other real number too.

Answer 5

Aceto, (削除) 29 (削除ここまで) 21 bytes

Writing to STDOUT, with a consistent, unambiguous separator between integers (such as a newline), with output prior to termination of the program

p<LL
 v`O
I?<\
0MLCnO

1. Push a zero, increment it and go in a random direction. Two of the directions lead back to the random direction field, one leads back to incrementation (so it is incremented a random amount of times).
2. When the fourth choice is made, we memorize and immediately load the value, then check whether it's contained in the stack already. If so, we jump to the origin and try again.
3. Otherwise, we load the value twice (once for printing, once for storage), print it and a newline and go back to the origin.

Massively favours low numbers, but there is a small chance for it to print any number at any point.

Answer 6

Bash, 23 bytes

yes \ |nl|xargs shuf -e

Try it online!

yes \ prints infinite spaces, nl numbers lines, suff -e shuffless lines without repetition.

Answer 7

Python 2, 39 bytes

f=lambda l,s:sum({1/s//1}-l)or f(l,s/2)

Try it online!

Takes a list l of previous outputs (as a set) and a seed s that's a random real from 0 to 1.

• Jonathan Allan: The seed should be an integer.
• xnor: @JonathanAllan I thought Mego OK'ed an infinite precision real in the comments. I'll confirm.
• Jonathan Allan: ...also I think l should be defaulted to an empty container of some description.
• Jonathan Allan: If they did it's a game changer.
• xnor: @JonathanAllan Reals are OK. I'm using the option that takes the previous integers as input.

Answer 8

Japt, 17 bytes

aA=(1/Mr)c)<0?A:ß

Try it online!

Answer 9

Java 8, 136 bytes

import java.util.*;()->{Set s=new HashSet();for(int n;;s.add(n))System.out.print(!s.contains(n=new Random().nextInt(-1>>>1))?n+";":"");}

Explanation:

Try it here. (Wait 60 seconds for the TIO to time-out to see the result.)

import java.util.*; // Required import for the Set, HashSet, and Random
()->{ // Method without parameters nor return-type
 Set s=new HashSet(); // Set to keep track of numbers we've already outputted
 for(int n;; // Loop infinitely
 s.add(n)) // And every time we output a random number, add it to the Set
 System.out.print( // Output:
 !s.contains( // If we haven't outputted it yet:
 n=new Random().nextInt(-1>>>1))?n+";"
 // A random number (range of int: 0 - 232)
 : // Else:
 ""); // Output nothing
} // End of method

Answer 10

Haskell, (削除) 60 (削除ここまで) (削除) 59 (削除ここまで) 56 bytes

((a:b)#h)(n:r)|n=a:((h++b)#[])r|q<-a:h=(b#q)r
[1..]#[]

Takes the seed as an infinite list of Bool.

Usage example: ([1..]#[]) [True,False,False,True,True,False,True,True,False,True,False,True,True,False,False,False,False,False,False,True....] -> [1,4,3,5,2,7,8,6,15,...].

Try it online!

Start with the list [1..]. If the next element from the seed is False, skip the next element of the list. If it's a True, output the current element, remove it from the list and start from the beginning. h keeps track of the skipped elements and is prepended (-> h++b) to the list of available numbers in the True case.

• clismique: What if the infinite list contains only 0's?
• nimi: @Qwerp-Derp: then there's no output. Some of the other answers run into the same problem if the random function returns the same number over and over again. I'm just using the seed itself as the random sequence.

Answer 11

Clojure, (削除) 112 (or 119) (削除ここまで) 114 bytes

Update, uses 1 / (rand) to get an "infinite" range of bigints:

#(filter pos?(map first(reductions(fn[[v p]r](if(p r)[0 p][r(conj p r)]))[0#{}](for[i(range)](bigint(/(rand)))))))

Original:

#(filter pos?(map first(reductions(fn[[v p]r](if(p r)[0 p][r(conj p r)]))[0 #{}](for[i(range)](rand-int 2e9)))))

I'm hoping to see an alternative approach. Anyway, this will generate integers between 1 and 2e9, Java's integers are signed to the "real" maximum is 2147483647, which is 7 bytes longer expression (Integer/MAX_VALUE is even longer). 0 is used as an indication of a duplicate values and are filtered from the output sequence.

• madstap: You can save a byte by using (repeatedly #(rand-int 2e9)) instead of (for[i(range)](rand-int 2e9)).
• madstap: Whoops, I overlooked the fact that you're already inside a function literal; can't nest those...
• clismique: I made an alternative approach! I'm not sure what the range is for the numbers supported, though...
• user45941: This is not valid. Only outputting integers between 1 and 2e9 generates a finite sequence.

Answer 12

Clojure, 100 bytes

(fn[](let[a(atom[])](filter #(if-not(some #{%}@a)(swap! a conj %))(repeatedly #(bigint(/(rand)))))))

This function returns an infinite sequence of integers. To get the nth number of this series:

(nth (fn[]...) n)

To get the first n terms of this series:

(take n (fn[]...))

EDIT: Golfed 11 bytes (Thanks @NikoNyrh!) and added 3 bytes (changed int to bigint, to improve accuracy).

• NikoNyrh: Nice option to hold the state, I got this approach down to 98 bytes by using if-not (dropping explicit false and true) and using unary version of /: #(int(/(rand))). Not sure if bigint would be more correct here as the result of that division might overflow int.

Answer 13

JavaScript ES6, repeating call, 50 Bytes

c={0:9};f=_=>c[~~_]|Math.random()<.9?f(-~_):c[_]=_

Answer 14

JavaScript REPL, 48 bytes

for(o=[];;)o[n=1/Math.random()|0]||alert(o[n]=n)

Answer 15

APL, 33 bytes

∇P
S←⍬
→2/⍨S∊⍨X←⌊÷1-?0
S,←⎕←X
→2∇

Answer 16

AWK, 62 bytes

{for(;x=rand()*1ドル;printf!b[a=int(x)]++?a"\n":X)gsub(/\./,X,x)}

Attempt This Online!

{for(;x=rand() # infinite loop
*1ドル; # seed from input
printf # format print
!b[a=int(x) # remove leading zeros
]++ # have we seen it before
?a"\n":X) # output
gsub(/\./,X,x)} # strips dot

Answer 17

Raku (Perl 6) (rakudo), 24 bytes

say (^2e9).pick for ^2e9

Attempt This Online!

So, technically this will work, but the pick method has to load all two billion numbers into memory before it can get working. You can test it with a smaller number:

say (^2e5).pick for ^2e5

I tried it with ∞ but Raku didn't like that.

• Shaggy: This has the possibility of duplicating numbers.

Answer 18

Japt, 12 bytes

I think this is valid, based on what other solutions are doing.

@øX}f@1/Mr)f

Try it

20 bytes

If not, this version ouputs infinitely.

ß[ON]mp@NøX}f@1/Mr)f

Try it

Answer 19

Uiua, 36 bytes

do(swfor&pjoigibelbacmemflo%rnd1)1[]

the same code formatted (20 chars, 42 bytes in utf-8):

⍢(⨬⊃&p⊂⋅∘◡ ̃∊⌊÷⚂1)1[]

• janMakoso: Uiua has a single-byte character encoding, so you do not have to use unformatted ASCII nor UTF-8 byte counts. Additionally, -2 by using reciprocal and pop instead of gap id. ⍢(⨬⊃&p⊂◌◡ ̃∊⌊⨪⚂)1[] (18 bytes)

Answer 20

Mathematica, 83 bytes

s=5;l={};t=1;While[t<30,If[l~FreeQ~s,Print@s];l~AppendTo~s;s=RandomInteger@100;t++]

starting with 5

Try it online!

• JungHwan Min: The second program does not meet the specifications.
• ZaMoC: I agree with you, but the specifications are problematic themselves.there should be a bound otherwise you could expect any integer of any length