[Question]
  [
**Task** 
Given a positive integer `n` less than `2^30` specified as input in any way you choose, your code should output a random integer between `0` and `n`, inclusive. The number you generate should be chosen *uniformly at random*. That is each value from `0` to `n` must occur with equal probability (see Rules and Caveats).
**Rules and Caveats**
Your code can assume that any random number generator built into your language or standard library that claims to be uniformly random is in fact uniform. That is you don't have to worry about the quality of the random source you are using. However,
* You do have to establish that if the random source you are using is uniform then your code correctly outputs a uniform random integer from `0` to `n`.
* **Any arguments when calling a built in or library random function must be constant. That is they must be completely independent of the input value.**
* Your code may terminate [with probability 1](https://en.wikipedia.org/wiki/Almost_surely) rather than being guaranteed to terminate.
**Notes**
* `randInt(0,n)` is not valid as it takes the input as an argument to a builtin or library function.
* `rand()%n` will **not** give a uniform random number in general. As an example given by betseg, if `intmax == 15` and `n = 10`, then you will be much more likely to get `0-5` than `6-10`.
* `floor(randomfloat()*(n+1))` will also not give a uniform random number in general due to the finite number of different possible floating point values between 0 and 1.
  
[Answer]
## x86 machines with `rdrand` instruction, 10 bytes
```
BITS 64
_try_again:
 rdrand eax
jnc _try_again
 cmp eax, edi
ja _try_again
 ret
```
machine code
```
0FC7F0 73FB 39F8 77F7 C3
```
---
The input is in the register `rdi` and the output in `rax`.  
This respects the [SYS V AMD64 ABI](https://software.intel.com/sites/default/files/article/402129/mpx-linux64-abi.pdf) so the code effectively implement a C function 
```
unsigned int foo(unsigned int max); 
```
with 32-bit ints.
The instruction `rdrand` is described by Intel
> 
> `RDRAND` returns random numbers that are supplied by a cryptographically secure, deterministic random bit generator DRBG. The DRBG is designed to meet the [NIST SP 800-90A](http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf) standard.
> 
> 
> 
Dealing with CSRNG it is implicit that the distribution is uniform, anyway, quoting the NIST SP 800-90A:
> 
> A random number is an instance of an unbiased random variable,
>  that is, the output produced by a **uniformly** distributed random process.
> 
> 
> 
---
The procedure generates a random number and if it is non-strictly greater than the input it is returned.  
Otherwise, the process is reiterated. 
Since `eax` is 32-bit, `rdrand` returns a number between 0 and 232-1, so for every *n* in [0, 232-1] the number of expected iterations is 232/(n+1) which is defined for all *n* in [0, 230). 
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~7~~ 6 bytes
```
⁴!!X%‘
```
*Thanks to @JonathanAllan for golfing off 1 byte!*
Cannot be run on TIO because **(16!)!** is a *huge* number.
### How it works
```
⁴!!X%‘  Main link. Argument: n
⁴       Set the return value to 16.
 !!     Compute (16!)!.
   X    Pseudo-randomly choose an integer between 1 and (16!)!.
        Since (16!)! is evenly divisible by any k ≤ 2**30, it is evenly divisible
        by n+1.
    %‘  Take the result modulo n+1.
```
[Answer]
## Mathematica, 29 bytes
*Based on [Dennis's Jelly answer](https://codegolf.stackexchange.com/a/111656/8478).*
```
RandomInteger[2*^9!-1]~Mod~#&
```
I wouldn't recommend actually running this. `2e9!` is a pretty big number...
It turns out to be shortest to generate a huge number that is divisible by all possible inputs and the map the result to the required range with a simple modulo.
### Rejection Sampling, 34 bytes
My old approach that led to somewhat more interesting code:
```
13!//.x_/;x>#:>RandomInteger[13!]&
```
Basic rejection sampling. We initialise the output to **13!** (which is larger than the maximum input **230**) and then repeatedly replace it with a random integer between **0** and **13!** as long as the value is bigger than the input.
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 9 bytes
```
≥.∧13ḟṙ|↰
```
[Try it online!](https://tio.run/nexus/brachylog2#@/@oc6neo47lhsYPd8x/uHNmzaO2Df//GxqAwf8oAA "Brachylog – TIO Nexus")
This uses `13!` like in Martin Ender's answer (`13ḟ` is one byte less than `2^₃₀`).
`ṙ` is implemented using [`random_between/3`](http://www.swi-prolog.org/pldoc/doc_for?object=random_between/3), which, when digging its source, uses [`random_float/0`](http://www.swi-prolog.org/pldoc/doc_for?object=f(random_float/0)) which is linked to [`random/1`](http://www.swi-prolog.org/pldoc/man?function=random/1) which uses the Mersenne Twister algorithm which is uniform for our purposes.
### Explanation
```
≥.           Input ≥ Output
  ∧          And
   13ḟṙ      Output = rand(0, 13!)
       |     Else
        ↰    Call recursively with the same input
```
[Answer]
# [Prolog (SWI)](http://www.swi-prolog.org/), 38 bytes
```
X*Y:-Z is 2^31,random(0,Z,Y),Y=<X;X*Y.
```
Works by rejection sampling.
Generate a random number between *0* and *2^31-1* = *2147483647* until one less than or equal to the input has been found.
I feel as if I should be able to use a cut instead of the else, but I can't see how.
[Answer]
## [Labyrinth](https://github.com/m-ender/labyrinth), 63 bytes
```
 ?
 #00}__""*_
 ;    #"  _
{-{=  } "><)
!{ : ;"({ +
@  }}:  >`#
```
*(Thanks to @MartinEnder for help with some heavy golfing here.)*
Labyrinth is a 2D language, and its only source of randomness is in a situation like the following:
```
   x
  "<)
 " "
 " "
```
Assume the instruction pointer is on the `x` and moving downwards. It next lands on the `<`, which if the top of stack is 0 (which is always the case in the actual program above) shifts the current row left by 1:
```
   "
 "<)
 " "
 " "
```
The instruction pointer is now on the `<` moving downwards. At a junction, Labyrinth turns based on the top of stack - negative is turn left, positive is turn right and zero is move forward. If the top of stack is still zero at this point, we can't move forward or backward since there's no path, so Labyrinth will randomise between turning left or turning right with equal probability.
Essentially what the program above does is use the randomness feature to generate 100-bit numbers (100 specified by `#00` here) and continue looping until it generates a number `<= n`.
For testing, it'll probably help to use `#0"` instead for 10-bit numbers, with the `"` being a no-op path. [Try it online!](https://tio.run/nexus/labyrinth#@69gz6WgbKBUGx@vpKQVz6VgrQAEykoKCvFc1brVtgoKtQpKdjaaXIrVClYK1koa1QraXA5A0VorBQW7BOX//02/5uXrJicmZ6QCAA)
Rough explanation:
```
 ?            <--- ? is input and starting point
 #0"}__""*_   <--- * here: first run is *0, after that is *2 to double
 ;    #"  _
{-{=  } "><)  <--- Randomness section, +0 or +1 depending on path.
!{ : ;"({ +        After <, the >s reset the row for the next inner loop.
@  }}:  >`#
 ^    ^
 |    |
 |    The " junction in this column checks whether the
 |    100-bit number has been generated, and if not then
 |    continue by turning right into }.
 |
 Minus sign junction here checks whether the generated number <= n.
 If so, head into the output area (! is output as num, @ is terminate).
 Otherwise, head up and do the outer loop all over again.
```
[Answer]
# Python, 61 bytes
```
from random import*
lambda n,x=2.**30:int(randrange(x)*-~n/x)
```
Edit:
Updated to avoid forbidden form
Edit2:
Saved 2 bytes, thanks @[JonathanAllan](https://codegolf.stackexchange.com/users/53748/jonathan-allan)
Edit3:
Paid 2 bytes for a fully functional solution - thanks again @JonathanAllan
Edit4:
Removed `f=`, saving 2 bytes
Edit5:
Saved 1 more byte thanks to @[JonathanAllan](https://codegolf.stackexchange.com/users/53748/jonathan-allan)
Edit6:
Saved 2 more bytes thanks to @[JonathanAllan](https://codegolf.stackexchange.com/users/53748/jonathan-allan)
By now, git blame would point at me for the bad things, and JonathanAllan for the stuff that helps. 
Edit7: 
When it rains, it pours - another 2 bytes
Edit8: 
And another 2 bytes
[Answer]
# [Python 2](https://docs.python.org/2/), 61 bytes
```
from random import*
lambda n:map(randrange,range(1,2**31))[n]
```
Pseudo-randomly chooses integers between **0** and **k** for all values of **k** between **0** and **231 - 2**, then takes the integer corresponding to **k = n**.
[Answer]
## Batch, 64 bytes
```
@set/ar=%random%*32768+%random%
@if %r% gtr %1 %0 %1
@echo %r%
```
`%random%` only gives 15 bits of randomness, so I have to combine two random numbers. Loops until the random value lies within the desired range, so slow for low `n`; 98 bytes for a faster version:
```
@set/a"n=%1+1,m=~(3<<30)/n*n,r=%random%*32768+%random%
@if %r% geq %m% %0 %1
@cmd/cset/a%r%%%%n%
```
[Answer]
# Bash (+coreutils), 44 bytes
[/dev/urandom](https://linux.die.net/man/4/urandom) based solution
```
od -w4 -vtu4</d*/ur*|awk '($0=$2)<='$1|sed q
```
Will read unsigned 32 bit integers from `/dev/urandom`, and filter them out with `awk` until it finds one within a given range, then `sed q` will abort the pipe.
[Answer]
# [MATL](https://github.com/lmendo/MATL), 12 bytes
*Thanks to [@AdmBorkBork](https://codegolf.stackexchange.com/users/42963/admborkbork) and to [@Suever](https://codegolf.stackexchange.com/users/51939/suever) for telling me how to disable TIO cache.*
```
`30WYrqG>}2M
```
[Try it online!](https://tio.run/nexus/matl#@59gbBAeWVTobldr5Pv/v6EBFHzNy9dNTkzOSAUA).
This uses a [rejection method](https://en.wikipedia.org/wiki/Rejection_sampling): generate a random integer from `0` to `2^30-1`, and repeat while it exceeds the input `n`. This is guaranteed to terminate with probability `1`, but the average number of iterations is `2^30/n`, and so it takes very long for `n` significantly smaller than `2^30`.
```
`         % Do...while
  30W     %   Push 2^30
  Yr      %   Random integer from 1 to 2^30
  q       %   Subtract 1
  G>      %   Does it exceed the input? If so: next iteration. Else: exit
}         % Finally (execute right before exiting the loop)
  2M      %   Push the last generated integer
          % End (implicit). Display (implicit)
```
[Answer]
# [PowerShell](https://github.com/PowerShell/PowerShell), 35 bytes
```
for(;($a=Random 1gb)-gt"$args"){}$a
```
[Try it online!](https://tio.run/nexus/powershell#@5@WX6RhraGSaBuUmJeSn6tgmJ6kqZteoqSSWJRerKRZXauS@P//f1MDg9ykr3n5usmJyRmpAA "PowerShell – TIO Nexus")
Another rejection sampling method. This is an infinite `for` loop, setting the value of `$a` to be a `Random` integer between `0` and `1gb` (`= 1073741824 = 2^30`), and keeps looping so long as that integer is `-g`reater`t`han the input `$args`. Once the loop is complete, we just put `$a` on the pipeline and output is implicit.
Note: This will take a ***long*** time if the input is a small number.
[Answer]
## JavaScript (ES6), ~~55~~ 54 bytes
```
f=(n,m=1)=>m>n?(x=Math.random()*m|0)>n?f(n):x:f(n,m*2)
```
Generates integers in the range **[0 ... 2k - 1]**, where **k** is the smallest integer such that **2k** is greater than **n**. Repeats until the result falls into **[0 ... n]**.
### Why?
This is based on the following assumptions:
* Internally, the pseudo-random integer values generated by the JS engine to feed `Math.random()` are uniform over any interval **[0 ... 2k-1]** (with **k < 32**).
* Once multiplied by an exact power of 2, the IEEE 754 float values returned by `Math.random()` are still uniform over such intervals.
If anyone can confirm or refute these hypotheses, please let me know in the comments.
### Demo
Generates 1 million values in **[0 ... 2]** and displays the outcome statistics.
```
f=(n,m=1)=>m>n?(x=Math.random()*m|0)>n?f(n):x:f(n,m*2)
for(i = 0, stat = []; i < 1000000; i++) {
  r = f(2);
  stat[r] = (stat[r] || 0) + 1;
}
console.log(stat.join` `)
```
[Answer]
# Haskell, 70 bytes
```
import System.Random
g n=head.filter(<=n).randomRs(0,2^30)<$>getStdGen
```
Not a very efficient algorithm but it works. It generates an infinite list of integers (or floats if needed, because of Haskell's type system) bounded by [0,2^30] and takes the first one less than or equal to n. For small n this can take a long time. The random numbers should be uniformly distributed, as specified in the documentation for [randomR](https://www.stackage.org/haddock/lts-8.3/random-1.1/System-Random.html#v:randomR) so all numbers in the interval [0,2^30] should have the same probability (1/(2^30+1)) therefore all the numbers in [0,n] have the same probability.
Alternate Version:
```
import System.Random
g n=head.filter(<=n).map abs.randoms<$>getStdGen
```
This version is terrible but it saves a whole byte. `randoms` uses an arbitrary range defined by the type to generate an infinite list of numbers. This may include negatives so we need to map it with `abs` to force them positive (or zero). This is extremely slow for any values of n that aren't absurdly large. **EDIT**: I realized later that this version isn't uniformly distributed because the probability of getting 0 is worse than the other numbers due to the use of `abs`. To produce some number `m` the generator could produce `m` or `-m` but in the case of 0 only 0 itself will work, therefore its probability is half of the other numbers.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
⁴!Ẋ’>Ðḟ⁸Ṫ
```
**[Try it online!](https://tio.run/nexus/jelly#AS0A0v//MTDhuorigJk@w5DhuJ/igbjhuar/wrPDhzvCtTMwwqH//zP1bm8tY2FjaGU)** - code above wont run on TIO since a range of size 16! must be built first (not to mention the fact that they then need to be shuffled and then filtered!), so this is the same thing on a much smaller scale, repeated 30 times for an input of 3 with a bound of 10.
### How?
```
⁴!Ẋ’>Ðḟ⁸Ṫ - Main link: n
⁴         - 16
 !        - factorial: 20922789888000
  Ẋ       - shuffle random: builds a list of the integers 1 through to 16! inclusive and
          - returns a random permutation via Python's random.shuffle (pretty resource hungry)
   ’      - decrement (vectorises - a whole pass of this huge list!)
     Ðḟ   - filter out if: (yep, yet another pass of this huge list!)
    >     -     greater than
       ⁸  -     left argument, n
        Ṫ - tail: return the rightmost remaining entry.
```
*Note:* it would be over a thousand time more efficient for the same byte-count if `ȷ⁵` would do what one would naively expect and return ten to the ten, but that is not the case since the `⁵` is not evaluated as a literal ten to be used by the number literal `ȷ...` but rather two separate literals are parsed, `ȷ` with it's default exponent of three yielding one thousand, and `⁵` yielding ten.
[Answer]
# JDK 9 on jshell, ~~75~~ 59 bytes
```
n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny()
```
### Usage
```
((IntFunction)(n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny())).apply(<n>)
```
* -16 bytes: Thanks Jakob!
* Assumes that we consider jshell to be a valid runtime environment.
* jshell itself, as a runtime environment, doesn't require explicit imports for core libraries and doesn't require semicolons.
* Returns an `OptionalInt`. Rules don't specify that return type must be a primitive and I'm considering an `OptionalInt` to be a valid representation of the result.
[Answer]
# PHP, 30 bytes
```
    while($argn<$n=rand());echo$n;
```
Run with `echo <N> | php -Rn '<code>'`.
picks a random number between 0 and [`getrandmax()`](http://php.net/getrandmax) (2\*\*31-1 on my 64 bit machine);  
repeats while that is larger than the input.
This *may* take a while ... my AMD C-50 (1 GHz) needed between 0.3 and 130 seconds for `N=15`.
A faster way for average `N` (**46 bytes**):
```
for(;++$i<$x=1+$argn;)$n+=rand()%$x;echo$n%$x;
```
or
```
for(;++$i<$x=1+$argn;$n%=$x)$n+=rand();echo$n;
```
takes `N+1` random integers, sums them up and takes the modulo with `N+1`.  
The C-50 needs approx. 8 seconds for 1 million runs.
An invalid solution for **19 bytes**:
```
echo rand(0,$argn);
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~72~~ 69 bytes
-3 bytes thanks to xnor (override the `id` built-in as a variable)
```
from random import*
n=input()
while id>n:id=randrange(2**30)
print id
```
**[Try it online!](https://tio.run/nexus/python2#@59WlJ@rUJSYlwKkMnML8otKtLjybDPzCkpLNDS5yjMyc1IVMlPs8qwyU2xByoA4PVXDSEvL2ECTq6AoM68EKP3/v6GBgcHXvHzd5MTkjFQA)**
`randrange(2**30)` produces a pseudo-uniformly distributed number (Mersenne Twister **219937-1**) from the range **[0,230)**. Since `n` is guaranteed to be below **230** this can simply be called repeatedly until it is not greater than the input. It will take a long expected time for very low values of `n`, but usually works within the a minute even for inputs as low as 50.
[Answer]
# Java 8, ~~84~~ ~~83~~ ~~80~~ ~~71~~ 62 bytes
```
n->{int r;for(;(r=(int)(Math.random()*(1<<30)))>n;);return r;}
```
-1 byte thanks to *@OliverGrégoire*.  
-3 bytes thanks to *@Jakob*.  
-9 bytes converting Java 7 to Java 8.  
-9 bytes by changing `java.util.Random().nextInt(1<<30)` to `(int)(Math.random()*(1<<30))`.
**Explanation:**
[Try it here.](https://tio.run/##NY7NCsJADITvPkWOiWCpeFz1DfTiUUTidtXVNlu2qSDSZ6@7/hwykMlk@G784Flondyq@2hr7jrYsJfXBMCLunhm62Cb148BFrMKmeQMkySdsnoLWxBYwSiz9SsHojmHiAbjKucJN6zXIrJUoUGa4ny5XJREtBZDJjrto6SXYTS5se1PdWr8FT@Cr6BJSLjT6OWyPwDTl2f37NQ1Rei1aNNJa0EpLM6PZVn@h36kw/gG)
```
n->{        // Method with integer parameter and integer return-type
  int r;    //  Result-integer
  for(;(r=(int)(Math.random()*(1<<30)))>n;);
            //  Loop as long as the random integer is larger than the input
            //  (the random integer is in the range of 0 - 1,073,741,824 (2^30))
  return r; //  Return the random integer that is within specified range
}           // End method
```
NOTE: May obviously take very long for small inputs.
**Example output:**
```
407594936
```
[Answer]
# Python 3, 51 bytes
Here is a python solution with an unorthodox random source.
```
print(list(set(map(str,range(int(input())+1))))[0])
```
[Try it online!](https://tio.run/##K6gsycjPM/7/v6AoM69EIyezuESjOLVEIzexQKO4pEinKDEvPVUDJJWZV1BaoqGpqW2oCQTRBrGa//8bGhgAAA "Python 3 – Try It Online")
So to break this down.
```
int(input())+1
```
Gets the input number, and adds `1` to it.
```
set(range(...))
```
Creates the set `{0, 1, 2, 3, 4, ... n}` for all possible results.
```
print(list(...)[0])
```
Takes the set, converts it to list, and grabs the first item.
This works because in Python 3, the order of `set()` is established by [PYTHONHASHSEED](https://docs.python.org/3/using/cmdline.html#envvar-PYTHONHASHSEED) ([can't be obtained](https://stackoverflow.com/q/32538764/) but is established on script execution).
Admittedly, I am guessing that this is a uniform distribution, as the `hash()` value is randomly assigned and I am looking at randomly picking the value with a specific `hash()`, rather then just returning the `hash(input())` itself.
If anyone knows whether this is a uniform distribution, or how I could test that, please comment.
[Answer]
# [Perl 6](https://perl6.org), 29 bytes
```
{first 0..$_,^2**30 .roll(*)}
```
Inspired by [Martin Ender's Mathematica solution](https://codegolf.stackexchange.com/a/111615/14880). 
Generates a lazy infinite sequence of random integers between 0 and 2^30-1, and takes the first one that is between 0 and the input.
[Try it online!](https://tio.run/nexus/perl6#y61UUEtTsP1fnZZZVFyiYKCnpxKvE2ekpWVsoKBXlJ@To6GlWfu/OLFSIU3B0MAg3sDAwJqLFO5/AA "Perl 6 – TIO Nexus")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 11 bytes
```
žIÝ.rDI›_Ï¤
```
[Try it online!](https://tio.run/nexus/05ab1e#@292aMPhuXpFLp6PGnbFH@4/tOT/f0MjYxNTs695@brJickZqQA)
**Explanation**
```
žIÝ          # push the inclusive range [0 ... 2^31]
   .r        # get a random permutation (pythons random.shuffle)
     D       # duplicate this list
      I      # push input
       ›_Ï   # keep only elements from the list not greater than input
          ¤  # take the last one
```
As the list `[0 ... 2147483648]` is too large for TIO, the link uses `1.000.000` instead.
**Alternate (on average) much faster 11 byte solution**
```
[žIÝ.RD¹›_#
```
[Try it online](https://tio.run/nexus/05ab1e#@x9tdmjD4bl6QS6Hdj5q2BWv/P@/oZGxianZ17x83eTE5IxUAA)
**Explanation**
```
[             # start loop
 žIÝ          # push the inclusive range [0 ... 2^31]
    .R        # pick a random integer (pythons random.chiose)
      D       # duplicate
       ¹      # push input
        ›_#   # break if random number is not greater than input
              # implicitly output top of stack (the random number)
```
[Answer]
# Python 2, 89 bytes
```
l=range(2**31)
import random
random.shuffle(l)
n=input()
print filter(lambda x:x<=n,l)[0]
```
## Explanation
```
L=range(2**31)      # Create a list from 0 to 2^31 exclusive. Call it <L>.
import random       # Import the module <random>.
random.shuffle(L)   # Use 'shuffle' function from <random> module,
                    # to shuffle the list <L>.
n=input()           # Take the input -> <n>.
print
    filter(         # Create a new sequence,
    lambda x:x<=n   # where each element is less than or equal to <n>.
    ,L)             # from the list <L>.
    [0]             # Take the first element.
```
This is *very* inefficient, as it creates **2^31** integers, shuffles and filters them.
I see no point in sharing a TIO link, where it's creating such large lists, so here is a TIO link for `n` = 100.
[Try it online!](https://tio.run/nexus/python2#JcgxCoAgFADQ3VM4KlToGnmSaLDUFL5fMYUu3mxB2@P1EHMqlRaNJkUC6sNpmRSSk/@myzfnwDLgBFXA3CrjJJeAlboA1RYGOu5G03u@F4UD8FVsvUshHkzjoQ9vXw)
[Answer]
# [R](https://www.r-project.org/), 37 bytes
```
which.min(sample(2^30)[0:scan()+1])-1
```
Takes `n` from stdin. First it generates a random sample of all the integers in the range, then selects the first `n+1` values, finds the index of the minimum, and then subtracts one, to generate a number between `0` and `n`, inclusive. It won't run on TIO because it can't allocate an array of size `2^30` to sample from.
I'm fairly confident this is uniformly random.
[Try it online!](https://tio.run/##K/r/vzwjMzlDLzczT6M4MbcgJ1XDKM7YQDPawKo4OTFPQ1PbMFZT1/C/4X8A "R – Try It Online")
[Answer]
# [Python 3](https://docs.python.org/3/), 51 bytes
```
lambda n:randrange(1<<31)*n>>31;from random import*
```
[Attempt this online!](https://ato.pxeger.com/run?0=ZVI9T8MwEJUYw584YCCpWpRQPqoWWJjYGZEq1760Fo4d7AuImV_BxgJ_hxl-DRcnopFqyb7hvXfP7-z3r_qVNs5-lnAND58NlZPZz9SIaqUE2LkXVvFeY1pcXU2LbGRvbqbFovSughbjoqvaeRp10t-9_YgFEqQDaRl6HOpACp-TiEpnDErSzv7Dt66xhD5JjoAwEKBaI0gRMKm9tpT2eFqmRQal87AEbaG_Wp5lWZIoLKM2NbrSNAbNfBFNsnkCvLpOu2gEJeffmkTSjtFAw36t6gjuN5pDBBDGwB14rLBaoYeYs3odDgJVI6P6hInK2WOCR-teYMObHIc1sjGCEATUk2dhGuwtGAyRtBHEB4Lijl6vmrZZ610K7RdQIhr2RWwFQqmOr-3BIPzh9xtcH47710jlSfQJaTvAAatCEhNu9dSglRrDnCVKy-0zDIU8ijj24nR6dn5xORtDkefLPM-z7k98dOUP) Includes a test suite.
Here is a proof that this is fair: <https://arxiv.org/abs/1805.10941>. It's also much faster than a typical modulo reduction because it's just a multiplication and a shift. (although this isn't as noticeable in Python...)
Uses an interesting approach, is O(1), and is the shortest Python answer yet!
[Answer]
# C#, 57 bytes
```
n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};
```
Anonymous function which returns an integer between 0 and n inclusive.
The smaller the input number, the longer the time to return a random value.
Full program:
```
using System;
class RandomNumber
{
    static void Main()
    {
        Func<int, int> f =
        n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};
        // example
        Console.WriteLine(f(100000));
    }
}
```
[Answer]
# SmileBASIC, 38 bytes
```
INPUT N@L
R=RND(1<<30)ON N<=R GOTO@L?R
```
Generates random numbers until it gets one that is smaller than the input.
[Answer]
## Ruby, ~~23 15 23 32~~ 29 bytes
```
->n{1while n<q=rand(2**30);q}
```
### How it works:
* `1while [...];` executes the statement at least once: `1` before `while` acts as a nop
* Get a random number in the range 0..2^30-1 (*lower than 2^30*, as specified)
* Repeat if the number is higher than the input parameter (Could take some time when n is small)
[Answer]
# Ohm, 26 bytes
```
IΩ
D31º#╬D0[>?D-+∞;,
```
Explanation:
```
IΩ                 ■Main wire
IΩ                 ■Call wire below
D31º#╬D0[>?D-+∞;,  ■"Real main" wire
D                  ■Duplicate input
 31º#╬D            ■Push random_int in [0..2^31] twice
       0[          ■Push input again
         >?    ;   ■If(random_int > input){
           D-+     ■  remove the random_int
              ∞    ■  recursion
               ;   ■}
                ,  ■Print random_int
```
[Answer]
# Go, ~~63~~ 61 bytes
```
import."math/rand"
var n=0;func R(){q:=n;for;q<n+1;n=Int(){}}
```
Use it like this:
```
func main() {
    n = 5000
    R()
    print(n)
}
```
[Test it live at the go playground](https://play.golang.org/p/_T9OreOzcE)
]