# Probabilistic approach puzzle

A few hours earlier, I got this puzzle:

Suppose, you toss a coin n times, then what is the probability of getting m number of heads? ( where m belongs to the set of all prime numbers)

For instance, take n = 2, then
SS = { HH, HT, TH, TT }

So, output is 1/4 (for HH case)

Then, for n = 3,
SS = { HHH, HHT, HTH, THH, HTT, THT, TTH, TTT }

So, output is (1 + 3)/8 (for 3 H's case and 2 H's cases respectively)

Input: n ( an integer, 0 <= n <= 1000 )
Output: The probability (in any distinguishable form, i.e., decimal, exponential, fraction, etc)

This is a , so fewest bytes would win!

• When you say n<1000 you mean that we should get results or the code can run forever? Apr 25, 2019 at 14:11
• @J42161217, it depends on you. n < 1000 is just a range of input for n (0 <= n < 1000). Apr 25, 2019 at 16:45
• ...the wording "where m is the set of all prime numbers" is a bit confusing, since you can't exactly have a number of heads equal to the set of all prime numbers (unless you're using an encoding of natural numbers into sets, in which case you should probably supply it!). I assume you actually mean that m is any prime number, although that wording suggests that you can pick a single one--it would be clearest to just not name it as a variable at all, and ask "in n flips of a fair coin, how likely are you to get a prime number of heads?" Apr 25, 2019 at 18:17

# Wolfram Language (Mathematica), 33 bytes

Uses Binomial and outputs ,really fast, fractions

Tr@Binomial[#,Prime@Range@#]/2^#&


Try it online!

The original code according to my formula was

Tr@Binomial[#,Prime@Range@PrimePi@#]/2^#&


but, as @attinat commented, instead of searching all Primes < n we can
search the first n primes because every prime > n returns zero binomial.
In this way we save 8 bytes

Here is also the graph of the first 1000 cases which looks pretty cool

• 33 bytes: Binomial[n,k]==0 if n<k
– att
Apr 25, 2019 at 22:35
• @attinat very nice! I'll edit Apr 25, 2019 at 22:40

# Jelly, 7 bytes

cÆRSH⁸¡


Try it online!

### How?

cÆRSH⁸¡ - Link@ integer, n                   e.g. 20
ÆR     - primes to n                             [2,3,5,7,11,13,17,19]
c       - (n) choose (vectorises)                 [190,1140,15504,77520,167960,77520,1140,20]
S    - sum                                     340994
¡ - repeat...
⁸  - ...times: chain's left argument, n
H   - ...action: halve
-   (170497, 85248.5, ..., ~0.65, ~0.325) 0.3251972198486328

• oh how I wish there were an x/2^y atom that doesn't floor like æ» (actually this inspired me to make a pull request for one :))
– Lynn
Apr 25, 2019 at 22:14

# 05AB1E, 10 7 bytes

ÅPcOso/


Try it online!

Explanation

ÅP       # push a list of primes upto and including input
c      # push choose(input, prime) for each prime
O     # sum
so   # push 2^input
/  # divide


# Octave/MATLAB with Statistics Package/Toolbox, 32 bytes

@(n)sum(binopdf(primes(n),n,.5))


Try it online!

# Python 3, 198125 97 bytes

lambda n:f(n)/2**n
f=lambda n,h=0:h>1>sum(h%i<1for i in range(2,h))if n<1else f(n-1,h+1)+f(n-1,h)


Try it online!

To aid in understanding, I first generate all the of the possible combinations, then I get then total heads if that is prime, then I add the total number of primes. The second function, h generates the result from function f. Bellow is the original algorithm before minimizing it.

def f(n,h=""):
count = 0
if n==0:
hCount=h.count("h")
for i in range(2, hCount):
if hCount % i == 0:
return 0
if hCount < 2:
return 0
return 1
count += f(n-1,h+"h")
count += f(n-1,h+"t")
return count

def h(n):
return f(n), (2**n)

print(h(4))


Credits:

• 97 bytes: sum(1for i in ... if c(i))==sum(c(i)for i in ...), apply De Morgan's Law and combine inequalities
– att
Apr 25, 2019 at 23:23

# Excel Formula, 311 309 bytes

The following should be entered as an array formula (Ctrl+Shift+Enter):

=SUM(IFERROR(COMBIN(A1,SMALL(IF(MMULT(--(IF(ROW(INDIRECT("2:"&A1))>TRANSPOSE(ROW(INDIRECT("2:"&A1))),MOD(ROW(INDIRECT("2:"&A1)),(ROW(INDIRECT("2:"&A1))>TRANSPOSE(ROW(INDIRECT("2:"&A1))))*TRANSPOSE(ROW(INDIRECT("2:"&A1)))))=0),ROW(INDIRECT("2:"&A1)))=0,ROW(INDIRECT("2:"&A1))),ROW(INDIRECT("1:"&A1)))),0))/(2^A1)


Where A1 is the number to test.

Examples:

A1=15
Result: 0.34997558593750
A1=25
Result: 0.341329127550125


Credits

-2 thanks to Sophia Lechner!

• Good to see someone else using Excel! Save two bytes per use by replacing ROW(INDIRECT("1:"&A1)) with ROW(OFFSET(A1,,,A1)) Apr 25, 2019 at 21:00
• @SophiaLechner Nice! Thank you! Apr 29, 2019 at 15:29

# Pari/GP, 42 bytes

n->sum(i=0,n,binomial(n,i)*isprime(i))/2^n


Try it online!

# Gaia, 12 8 bytes

:ṅK¦Σ@z÷


Try it online!

:		| dup input n
ṅ		| push first n prime numbers, [2..k]
K¦		| push n choose k (0 if k > n)
Σ		| sum
@z		| push 2^n
÷	| divide


# Retina, 41 bytes

K
"$+"+%^$"H
*\Cm^(?!(..+)\1+$).. m^  Try it online! Output is as a ratio. Explanation: K "$+"+%^
$"H  Generate all the possible coin tosses of n coins, but keep only the heads. (T$"H would keep the tails as well.)

*\Cm^(?!(..+)\1+\$)..


Count how many are prime and print on a separate line.

m^


Count how many there are altogether.

# JavaScript (ES7), 71 bytes

n=>(s=1,g=i=>i<n&&(s*=(n-i)/++i)*(p=d=>i%--d?p(d):d==1)(i)+g(i))/2**n


Try it online!

# Jelly, 7 bytes

Ø.ṗ§ẒÆm


Try it online!

Different approach from Jonathan Allan's answer.

# Japt-x, 13 bytes

õÈj *UàX /2pU


Try it