|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``Re: How many needed''
by Algeboy on 2006-08-12 11:42:45 |
|
| Given N possibilities, you need at random \sqrt{N} samples to have a probability of 1/2 of any duplicate. In the birthday problem the N is the number of days in a year, so 365. So you need \sqrt{365}=19 to have a 50% chance of a duplicate.
This is the same trick used in the Pollard -\rho tests for factorization. It is neat to see such an elementary result used on such a hard problem with positive outcomes.
Hope that answered your question.
James
|
| | [ reply | up | top ] | |
|
|
|
|
|
|
|
