6
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ When you say n<1000 you mean that we should get results or the code can run forever? \$\endgroup\$
    – ZaMoC
    Apr 25, 2019 at 14:11
  • \$\begingroup\$ @J42161217, it depends on you. n < 1000 is just a range of input for n (0 <= n < 1000). \$\endgroup\$
    – vrintle
    Apr 25, 2019 at 16:45
  • 1
    \$\begingroup\$ ...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?" \$\endgroup\$ Apr 25, 2019 at 18:17

12 Answers 12

9
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

Uses Binomial and outputs ,really fast, fractions

enter image description here

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

enter image description here

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

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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 :)) \$\endgroup\$
    – Lynn
    Apr 25, 2019 at 22:14
4
\$\begingroup\$

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 
\$\endgroup\$
0
4
\$\begingroup\$

Octave/MATLAB with Statistics Package/Toolbox, 32 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3, 198 125 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:

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

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!

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

Pari/GP, 42 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 7 bytes

Ø.ṗ§ẒÆm

Try it online!

Different approach from Jonathan Allan's answer.

\$\endgroup\$
0
\$\begingroup\$

Japt -x, 13 bytes

õÈj *UàX /2pU

Try it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.