Probabilistic approach puzzle

Question

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 code-golf, so fewest bytes would win!

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

ZaMoC · Accepted Answer · 2019-04-25 22:54:00Z

9

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

edited Apr 25, 2019 at 22:54

answered Apr 25, 2019 at 13:48

ZaMoC

24.4k2 gold badges29 silver badges79 bronze badges

\$\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

Add a comment |

Jonathan Allan · Accepted Answer · 2019-04-25 18:32:26Z

6

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

answered Apr 25, 2019 at 18:32

Jonathan Allan

104k7 gold badges62 silver badges270 bronze badges

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

Add a comment |

Emigna · Accepted Answer · 2019-04-25 14:54:06Z

4

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

edited Apr 25, 2019 at 14:54

answered Apr 25, 2019 at 13:59

Emigna

52.9k5 gold badges42 silver badges162 bronze badges

Add a comment |

Luis Mendo · Accepted Answer · 2019-04-25 17:05:32Z

4

Octave/MATLAB with Statistics Package/Toolbox, 32 bytes

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

Try it online!

answered Apr 25, 2019 at 17:05

Luis Mendo

104k9 gold badges132 silver badges365 bronze badges

Add a comment |

Neil · Accepted Answer · 2019-04-25 23:25:14Z

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:

From 125 to 97 bytes by attinat

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

i_saw_drones · Accepted Answer · 2019-04-29 15:27:47Z

2

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!

edited Apr 29, 2019 at 15:27

answered Apr 25, 2019 at 19:12

i_saw_drones

4532 silver badges7 bronze badges

\$\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\$
– Sophia Lechner
Apr 25, 2019 at 21:00
\$\begingroup\$ @SophiaLechner Nice! Thank you! \$\endgroup\$
– i_saw_drones
Apr 29, 2019 at 15:29

Add a comment |

Giuseppe · Accepted Answer · 2019-04-25 16:49:57Z

1

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

edited Apr 25, 2019 at 16:49

answered Apr 25, 2019 at 13:28

Giuseppe

28.1k3 gold badges30 silver badges101 bronze badges

Add a comment |

Neil · Accepted Answer · 2019-04-25 19:05:11Z

1

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.

answered Apr 25, 2019 at 19:05

Neil

166k12 gold badges69 silver badges273 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 25, 2019 at 21:50

Arnauld

189k20 gold badges171 silver badges631 bronze badges

Add a comment |

Erik the Outgolfer · Accepted Answer · 2019-04-26 12:15:07Z

1

Jelly, 7 bytes

Ø.ṗ§ẒÆm

Try it online!

Different approach from Jonathan Allan's answer.

answered Apr 26, 2019 at 12:15

Erik the Outgolfer

40.5k5 gold badges41 silver badges121 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2023-08-09 12:05:15Z

1

Pari/GP, 35 bytes

n->binomial(n)*isprime([0..n])~/2^n

Try it online!

edited Aug 9 at 12:05

answered Apr 25, 2019 at 14:14

alephalpha

46.6k7 gold badges61 silver badges172 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Japt `-x`, 13 bytes

õÈj *UàX /2pU

Try it

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 25, 2019 at 19:07

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Stack Exchange Network

Probabilistic approach puzzle

12 Answers 12

Wolfram Language (Mathematica), 33 bytes

Jelly, 7 bytes

How?

05AB1E, 10 7 bytes

Octave/MATLAB with Statistics Package/Toolbox, 32 bytes

Python 3, 198 125 97 bytes

Excel Formula, 311 309 bytes

Gaia, 12 8 bytes

Retina, 41 bytes

JavaScript (ES7), 71 bytes

Jelly, 7 bytes

Pari/GP, 35 bytes

Japt `-x`, 13 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
arithmetic
probability-theory
or ask your own question.

Hot Network Questions

Probabilistic approach puzzle

12 Answers 12

Wolfram Language (Mathematica), 33 bytes

Jelly, 7 bytes

How?

05AB1E, 10 7 bytes

Octave/MATLAB with Statistics Package/Toolbox, 32 bytes

Python 3, 198 125 97 bytes

Excel Formula, 311 309 bytes

Gaia, 12 8 bytes

Retina, 41 bytes

JavaScript (ES7), 71 bytes

Jelly, 7 bytes

Pari/GP, 35 bytes

Japt -x, 13 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Japt `-x`, 13 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
arithmetic
probability-theory
or ask your own question.