# This will eventually stop…

Given an input string S, print S followed by a non-empty separator in the following way:

• Step 1: S has a 1/2 chance of being printed, and a 1/2 chance for the program to terminate.

• Step 2: S has a 2/3 chance of being printed, and a 1/3 chance for the program to terminate.

• Step 3: S has a 3/4 chance of being printed, and a 1/4 chance for the program to terminate.

• Step n: S has a n/(n+1) chance of being printed, and a 1/(n+1) chance for the program to terminate.

### Notes

• The input string will only consist of characters that are acceptable in your language's string type.

• Any non-empty separator can be used, as long as it is always the same. It is expected that the separator is printed after the last print of S before the program terminates.

• The program has a 1/2 chance of terminating before printing anything.

• A trailing new line is acceptable.

• Your answer must make a genuine attempt at respecting the probabilities described. Obviously, when n is big this will be less and less true. A proper explanation of how probabilities are computed in your answer (and why they respect the specs, disregarding pseudo-randomness and big numbers problems) is sufficient.

### Scoring

This is , so the shortest answer in bytes wins.

• Can the separator be an empty string? – rturnbull Jun 12 '17 at 7:13
• @rturnbull Well no, because in that case there is no separator. – Fatalize Jun 12 '17 at 7:18
• Do we have to print these one after the other, or can we just print all of them when the program terminates? – Dennis Jun 12 '17 at 18:21
• @Dennis One after the other. – Fatalize Jun 13 '17 at 6:42

# Pyth, 7 bytes

WOh=hZQ


Try it online!

## How it works

Pseudocode:

while rand_int_below(1 + (Z += 1)):
print(input)

• Pyth beats 05AB1E again doesn't it? – Erik the Outgolfer Jun 12 '17 at 8:47
• Doesn't the print statement need it's own probability along with the termination probability? – tuskiomi Jun 14 '17 at 15:13
• @tuskiomi Nah, n/(n+1) is just 1-1/(n+1), or 1 - (probabilty of termination). – Adowrath Jun 14 '17 at 21:41

# C#, 94 85 bytes

using System;s=>{var r=new Random();for(var i=2;r.Next(i++)>0;)Console.Write(s+" ");}


Previous attempt (I liked that goto):

using System;s=>{var i=2;var r=new Random();a:if(r.Next(i++)>0){Console.Write(s+" ");goto a;}}


Ungolfed:

using System;
class P
{
static void Main()
{
Action<string> f = s =>
{
var r = new Random();
for (var i = 2; r.Next(i++) > 0;) Console.Write(s + " ");
};

f("test");

}
}


Note: in C# the Random.Next(N) method returns a nonnegative integer in the [0, N-1] range, so we can just check that the number returned is greater than 0.

• You need to include using System; into your byte count. You can declare r inline, no need to set it to a variable: new Random().Next(i++). You don't need the trailing semicolon on the golfed func. – TheLethalCoder Jun 12 '17 at 8:25
• Oh and nice first answer! Would have been shorter than my attempt :) – TheLethalCoder Jun 12 '17 at 8:27
• @TheLethalCoder thank you for your comments! I tried to use new Random().Next(i++) but when I tried to execute that, the result was always either the program stops without printing anything, or the program never stops. When I declare r=new Random() and use the r variable, the program stops more randomly as the OP asks. – Charlie Jun 12 '17 at 8:34
• Ahhh probs because the loop is so tight. – TheLethalCoder Jun 12 '17 at 8:36
• @TheLethalCoder - Yes, thight loop means a chance that the seed of the generator will be the same. See: msdn.microsoft.com/en-us/library/system.random.aspx#Instantiate – Erno Jun 14 '17 at 6:04

# R, 4746 43 bytes

43 bytes due to Robin Ryder in the comments.

s=scan(,"")
while(sample(T<-T+1)-1)print(s)


Try it online!

### Explanation

s=scan(,"")  # Takes input from stdin.
T<-T+1    # T is 1 by default, so this
# evaluates to 2, and will increment
# at each step.
sample(T<-T+1)   # Take a sample of size 2, i.e. generate
# a list of integers from 1 to 2 in random order
sample(T<-T+1)-1 # Subtract one from every element of this list.
while(sample(T<-T+1)-1)# while() will treat the first value in this list
# as a logical value, i.e. FALSE for zero and TRUE
# for nonzero values. The other elements of the list
# are ignored, triggering a warning.
print(s) # print s

• Does this ever terminate? – mfloren Jun 13 '17 at 4:53
• @mfloren Yes, like all the other answers here, it's stochastic, with termination chance decreasing as it progresses, but it will eventually terminate. There's a .5 chance it will print nothing! Try running it several times and compare the outputs. – rturnbull Jun 13 '17 at 7:59
• function(s) is shorter than s=scan(,''); – JAD Jun 13 '17 at 13:55
• And pryr::f(while(runif(1)<T/(T<-T+1))print(s)) is even shorter. – JAD Jun 13 '17 at 13:59
• @JarkoDubbeldam Unfortunately you can't (ab)use T and F with anonymous functions, as it modifies a global variable and means that the function can only be called once. See here: "the solution function performs consistently regardless of how many times it has been called previously". – rturnbull Jun 14 '17 at 8:36

# 05AB1E, 8 bytes

[NÌL.R#,


Try it online!

Explanation

[         # start loop
NÌL      # push range [1 ... current_iteration+2]
.R    # pick a random number
#   # if true (1), exit loop
,  # print input

• @Fatalize: It does for me. Try running it a few times. It has a 50% chance of not outputting anything so you may have been "unlucky". – Emigna Jun 12 '17 at 8:08
• The inherit problem of random tasks. Sometimes all odds are against you. – J_F_B_M Jun 12 '17 at 8:34
• @J_F_B_M inherent? – Leaky Nun Jun 12 '17 at 14:55
• @LeakyNun No, it's the "Inherit Problem" (the probability of events is not inherited from previous events). J_F_B_M was clearly referring to the Gambler's Fallacy. – aebabis Jun 12 '17 at 19:52

## Javascript, 6058 54 bytes

f=(s,n=1)=>Math.random()<n/++n?console.log(s)+f(s,n):0


Will output string s. The seperator which is printed if the program terminates is NaN or 0.

f=(s,n=1)=>Math.random()<n/++n?console.log(s)+f(s,n):0

f('test')

Math.random() returns a value between 0 and 1. If that value is under n/(n+1), then s will be pritned.

4 bytes saved thanks to @Neil

• Why not use n/++n? – Neil Jun 12 '17 at 9:00
• @Neil thanks, saved 4 bytes! – Thomas W Jun 12 '17 at 9:03
• If your environment was a browser you could use alert instead of console.log to save 6 bytes - the snippet could set alert = console.log to show non obtrusive output if desired (if allowed - doesn't save bytes, just helps keep one sane) – Craig Ayre Jun 12 '17 at 13:45

# Java 8, 7262 61 bytes

s->{for(int n=2;Math.random()<1f/n++;System.out.println(s));}


-10 bytes thanks to @cliffroot.
-1 byte thanks to @JollyJoker.

Delimiter is a new-line.

Explanation:

Try it here.

s->{                          // Method with String parameter and no return-type
for(                        //  Loop
int n=2;                  //   Start n on 2
Math.random()<1f/n++;     //   Continue loop as long as a random decimal (0.0-1.0)
//   is smaller than 1/n (and increase n by 1 afterwards)
System.out.println(s)     //   Print the input-String
);                          //  End of loop
}                             // End of method

• i am unable to check in the moment but why not put if condition inside for condition block? – cliffroot Jun 12 '17 at 8:01
• @cliffroot It is in the for loop. – Okx Jun 12 '17 at 8:54
• @Okx I meant condition when for loop should end so that it does not need explicit return. The second expression inside for statement. – cliffroot Jun 12 '17 at 9:01
• @cliffroot Ah, I understand. – Okx Jun 12 '17 at 9:07
• Would int n=2 and 1f/n++ work? – JollyJoker Jun 13 '17 at 11:42

# Mathematica, 43 bytes

(n=1;While[RandomInteger@n>0,Print@#;n++])&


JungHwan Min saved 1 byte (above) and suggested something better (below)

# Mathematica, 37 bytes

For[n=1,RandomInteger@n++>0,Print@#]&

• RandomInteger@n!=0 is the same as RandomInteger@n<1 in this case, and n++ can be merged with RandomInteger@n. Also, For is (almost always) shorter than While: -5 bytes For[n=1,RandomInteger@n++>0,Print@#]& – JungHwan Min Jun 12 '17 at 7:30
• "For" wins! I posted your answer too – J42161217 Jun 12 '17 at 7:39
• For[n=1,!n∣Hash[# n++],Print@#]& would also work at 34 bytes, assuming the hash is fairly random. The randomness depends on the input, however. For example try % /@ Alphabet[] – Kelly Lowder Jun 13 '17 at 6:57

## Clojure, 61 56 bytes

Oh why didn't I go with a for in the first place? But actually to be pedantic doseq has to be used as for is evaluated lazily.

#(doseq[n(range):while(>(rand-int(+ n 2))0)](println %))


Original:

#(loop[n 2](if(>(rand-int n)0)(do(println %)(recur(inc n)))))

• isn't (>(+(rand-int n)2)0) always true? – cliffroot Jun 12 '17 at 8:47
• Ah good catch, I meant to increment n! – NikoNyrh Jun 12 '17 at 8:56

## ><>, 124 112 bytes

i:0( ?v
&5a ~/
&p0[^ >"\_\^x0!>"0&1+:&p1&:&p2&:&p3&:&p4&:&p0&1+:&p3&:&p4&:
=?v[/!}l]:?!;1
{:   ?^  >
:o>_ {:?!^


Try it online! (You can also watch it at the fish playground, but due to some bugs you have to add a } after the l in the fourth line and add a bunch of newlines after the code to make it work properly.)

Randomness is tricky in ><>. The only random instruction is x, which picks the fish's direction randomly from four choices (left, right, up and down), so turning that into something with probability 1/n is not straightforward.

The way this code does it is by using ><>'s self-modifying capabilities to build a Tower of Randomness below the code, so at the fourth stage, for example, the code looks like:

i:0( ?v
&5a ~/
&p0[^ >"\_\^x0!>"0&1+:&p1&:&p2&:&p3&:&p4&:&p0&1+:&p3&:&p4&:
=?v[/!}l]:?!;1
{:   ?^  >
:o>_ {:?!^
>!0x^
\  _\
>!0x^
\  _\
>!0x^
\  _\
>!0x^
\  _\


The fish starts at the bottom of the tower. At each level of the tower, the x is trapped between two mirrors, so the fish can only escape by going left or right. Either of these directions sends the fish up to the next level of the tower, but going left also pushes a 0 to the stack. By the time the fish gets to the top of the tower, the stack contains some number of 0s, and this number follows a binomial distribution with n trials and p = 1/2.

If the length of the stack is 0 (which has probability 1/2n), the program halts. If the length is 1 (with probability n/2n), the fish prints the input and a newline and builds another level of the tower. If the length is anything else, the fish discards the stack and goes back to the bottom of the tower. In effect, out of the possibilities that actually do something, n of them print the input string and one of them halts the program, giving the required probabilities.

# Python 3, 7269 66 bytes

• Saved 3 bytes thanks to Jonathan Allan: Import shorthand and start count from 2.
• Saved 3 bytes thanks to L3viathan : Pointed randint() was inclusive and also shortened while condition.
from random import*
s=input();i=1
while randint(0,i):print(s);i+=1


Try it online!

• There's a setting to turn off the output cache - like so – Jonathan Allan Jun 12 '17 at 7:21
• I think it's acceptable to be "off" for large n (I can't get English brain in gear, "...(and why they respect the specs, disregarding pseudo-randomness and big numbers problems)..." disregarding - right?) If so then you can do random()<1/i. – Jonathan Allan Jun 12 '17 at 7:34
• Doesn't this start with probability ⅓? randint is inclusive. You could then shorten that line to while randint(0,i):print(s);i+=1 – L3viathan Jun 12 '17 at 8:22
• I just came up with the same solution. – Esolanging Fruit Jun 12 '17 at 17:52
• Updated TIO link. Now the byte count is the same as the floating point version too. – Jonathan Allan Jun 12 '17 at 22:31

# QBIC, 19 17 bytes

Dropped =1, switched conditionals, saved 2 bytes

{p=p+1~_rp||?;\_X


## Explanation

{       Infinitely DO
p=p+1   Add 1 to p (p starts as 0, so on first loop is set to 1, then 2 etc...)
~       IF
_rp|| a random number between 0 and p
(implicitly: is anything but 0)
?;      THEN print A$(which gets read from the cmd line) \_X ELSE QUIT END IF and LOOP are auto-added at EOF  # Braingolf, 23 bytes #|V12[R!&@v!r?<1+>1+]|;  Try it online! Generates random number x where 0 <= x < n+1, terminates if x is 0, otherwise increments n and loops. Separator is | ## Explanation: #|V12[R!&@v!r?<1+>1+]|; Implicit input of commandline args to stack #| Push | V Create stack2 and switch to it 12 Push 1, then 2 [..............] Do-While loop, will run indefinitely unless conditional skips Closing bracket R Return to stack1 !&@ Print entire stack without popping v Switch to stack2 !r Generate random number 0 <= x < n where n is last item on stack ? If last item is greater than 0.. < ..Move first item to end of stack 1+ ..and increment, this is the loop counter number > ..Move back 1+ ..and increment, this is the upper range of the RNG ] ..end loop | Endif ; Suppress implicit output  ## Alice, 18 bytes /?!\v \iO/>]qhUn$@


Try it online!

### Explanation

/     Reflect to SE. Switch to Ordinal.
i     Read all input as a string and push it to the stack.
!     Store the string on the tape.
/     Reflect to E. Switch to Cardinal.
>     Ensure that the IP moves east. This begins the main loop.

]   Move the tape head to the right. We'll be using the tape head's
position as a counter variable. Note that this tape head is independent
of the one used in Ordinal mode to point at the input string.
q   Push the tape head's position to the stack.
h   Increment it (so that it's 2 initially).
U   Get a uniformly random number in [0,n).
n   Logical NOT. Gives 1 with probability 1/n and 0 otherwise.
$@ Terminate the program if we got a 1. \ Reflect to NE. Switch to Ordinal. ? Retrieve the input from the tape. O Print it with a trailing linefeed. \ Reflect to E. Switch to Cardinal. v Send the IP south where it runs into the > to start the next loop iteration.  # PHP, 31 bytes for(;rand()%~++$c;)echo$argn._;  Try it online! ## Perl, 26 bytes 24 bytes code + 2 for -nl. print while rand++$i+1|0


Try it online!

# Charcoal, 14 bytes

Ａ²γＷ‽γ«θ_Ａ⁺γ¹γ


Try it online! Link is to verbose version of code. Uses _ as the separator. Note: output caching is disabled, so please don't hammer Dennis's server!

# MATL, 9 bytes

G@QYrq]x


Try it online!

### Explanation

        % Do...while
G      %   Push input
@      %   Push iteration index k, starting at 1
QYrq   %   Random integer uniformly distributed in {0, 1, ..., k}. This is the
%   loop condition. If non-zero (which occurs with probability k/(1+k))
%   proceed with next iteration; else exit loop
]        % End
x        % Delete, as there are one too many strings. Implicitly display the stack


# Perl 6,  50 41 38 36  26 bytes

{put $_//last for (($,$_),*⊎$_...*).map(*.pick)}


Try it

{eager ->{(++$).rand>.5??.put!!last}...*}  Try it {eager ->{(++$).rand>.5??.put!!0}...0}


Try it

{eager ->{(++$).rand>.5&&.put}...!*}  Try it .put while (++$/).rand>.5


(with -n commandline argument)

Try it

## Python 3, 55 bytes

v=s=input();i=2
while hash(v)%i:print(s);i+=1;v=hash(v)


## Explanation

To save having to import random, I've exploited the fact that the hash built-in is randomly seeded each time a python process is fired up (at least in MacOS). Each hash of the last hash should generate a series of pseudo-random integers.

If the hash is pseudo-random enough, the modulo with i is zero with probability 1/i.

## Notes

I'm a little bothered by the redundant hash, but without a do-while, or in-condition assignment in Python, I'm a little stuck.

• Do you know whether iterated hashing is always going to cover the full space of random numbers, or can it potentially get stuck in a cycle? Most programming languages use randomized hash algorithms nowadays in order to avoid people intentionally causing hash collisions, but I'm not sure how the randomness guarantees of the hash algorithms compare to those of a PRNG. – user62131 Jun 13 '17 at 3:30
• It's a fair point. And I'm not sure, it would take some analysis of the Python hash implementation to check (without a more exhaustive check). I thought it was a fun solution, even if there's a chance it might not be 100% pseudo-random =p – Kit Ham Jun 13 '17 at 3:38
• I'm a little bothered... recursion? – Felipe Nardi Batista Jun 13 '17 at 12:00

# C#

This is same length as the top C# answer, but:

using System;s=>{var x=(1<<31)/new Random().Next();for(;++x>0;)Console.Write(s+" ");}


Just wanted to point out that some math can produce the correct probability.

int.MaxValue/new Random().Next()-1


Is equivalent to

(int)(1 / new Random().NextDouble()) - 1;


And the function f(x)=1/x-1 is:

f(1) = 0

f(1/2) = 1

f(1/3) = 2

f(1/4) = 3

So 1/2 a chance to be rounded down to 0, 1/6 a chance to be rounded down to 1, and 1/(n+1)(n+2) a chance to be rounded down to n.

Maybe some other language could capitalize on this.

EDIT: Fixed my mistake

I thought of something to make it smaller.

EDIT EDIT: I am just all kinds of wrong. Pulled the Random out of the loop because if it's evaluated multiple times, it won't work.

EDIT EDIT EDIT: I got rid of the variable i. I'm going to stop trying to shrink it now. Nope, lied. Got rid of another byte.

# Charcoal, 17 bytes

ＳαＡ²βＷ‽β«⁺α¶Ａ⁺β¹β


Try it online! Verbose code included. Respects specs because it uses a random range from 0 to n.

# C, 41 bytes

n;f(char*s){for(n=1;rand()%++n;puts(s));}


Assumes rand is seeded. Try it online!

• "Assumes rand is seeded." -- Is that a valid assumption to make? rand is required by the standard to have a fixed seed value of 1 by default and all implementations I know of do just that. If this function only does what the challenge asks when combined with other code, I think that other code needs to be included in the answer and in the byte count. – hvd Jun 13 '17 at 10:36

# braingasm, 22 bytes

edit: Same byte count, but I realized I could sneak in the new tape Limit feature.

,[>,]>L+[+$rzQ>[.>]:>]  Uses 0 as separator. Works like this: ,[>,] Read a byte and move to next cell until end of input. > After the loop we're in an empty cell; Leave it empty and move to the next. L Set tape limit here: The tape will then wrap around if we move further. + Increase current cell by one. This cell will be our counter. [ ] Loop until the counter is zero. That won't happen, so it's an infinite loop. + Increase again, so the first time the counter is 2.$r            Get a random number, 0 <= r > current cell
zQ          Quit the program if that random number was 0
>         Wrap around to the start of the tape.
[.>]     Print the input stored on the tape
The loop will stop at the blank cell.
:    Print the blank cell as a number ("0")
>   Go to the next (last) cell


# Python, 54 bytes

lambda s:int(1/random()-1)*(s+'|')
from random import*


Try it online!

Generated the number of copies as floor(1/p)-1 with p uniformly chosen from the unit interval. The number of copies is n when 1/p-1 falls between n and n+1, which happens when 1/(n+2) < p < 1/(n+1). This happens with probability 1/(n+1)-1/(n+2) or 1/((n+1)*(n+2). This is the desired probability of outputting n copies: 1/2 prob of 0, 1/6 prob of 1, 1/12 prob of 2,...

• Why is form random import* at the bottom? – CalculatorFeline Jun 12 '17 at 17:25
• @CalculatorFeline The order doesn't matter. The function definition works either way. – xnor Jun 12 '17 at 19:48
• @CalculatorFeline In order to drop to bytes by not writing f= and placing it in the TIO Header – Mr. Xcoder Jun 14 '17 at 19:39
• That makes sense. – CalculatorFeline Jun 16 '17 at 19:47

# C++, 9796 57 bytes

Here my first try on codegolf :)

#include<iostream>
int main(){std::string S;std::cin>>S;int i=1;while(rand()%++i)puts(S.data());}


I saved one byte by using for

#include<iostream>
int main(){std::string S;std::cin>>S;for(int i=1;rand()%++i;)puts(S.data());}


Saved 39 bytes since nobody seems to count the includes

void p(string S){for(int i=1;rand()%++i;)puts(S.data());}


ungolfed

#include <iostream>
int main()
{
// Create and read string from inputstream
std::string S;
std::cin >> S;

// rand % i: create random int in range [0, i-1]
// Zero is seen as false and all positive int as true
int i = 1;
while (rand() % ++i)
puts(S.data());
}

• You may take the string as an argument from the command line – Maliafo Jun 12 '17 at 21:43
• Includes are counted, unless you find a compiler that includes them by default – Felipe Nardi Batista Jun 13 '17 at 12:24

# F#, 161 bytes

Definitely not the best language to golf, but I decided to give it a try (besides, I do not know anything about F#, so any tips on how to improve my answer will be welcome).

let f s=
let r,z=System.Random(),(<>)0
let p _=printfn"%s"s
seq {for i in 2|>Seq.unfold(fun i->Some(i,i+1))do yield r.Next(i)}|>Seq.takeWhile z|>Seq.iter p


Execute with:

[<EntryPoint>]
let main argv =
"test" |> f
0


Writes a new line as separator.

# Ruby, 29+1 = 30 bytes

Uses the -n flag.

i=1;puts$_ while i>rand(i+=1)  Try it online! • Since you're taking exactly one line of input, you can use the$. special variable instead of i. Arguably you can also replace puts$_ with print but it's not clear the rules support that. – histocrat Oct 8 at 16:30 # JS (ES6), 47 bytes x=>{for(i=1;Math.random()<i/(i+1);i++)alert(x)}  Unlike the other ES6 answer, this uses a for loop and alert bombs instead of recursion. The seperator that is printed when the program stops is undefined. ## PowerShell, 31 bytes for($i=2;random($i++)){"$args"}


Get-Random $i outputs an n where 0 <= n <$i, separator is implicit newline.

# Python, 75 bytes

The other Python answer is shorter, but I wanted to try it a different way:

from random import*
f=lambda d=1,s=input():randint(0,d)and s+'!'+f(d+1)or''