When a shared birthday becomes likely
birthday is one function. Everything below came out of it during this
build, at parameters taken from the essays rather than invented for this page — so a figure
here is the same figure a reader meets in an essay, and if the generator changes, this page
changes with it.
With nothing chosen
The walk x² + 1 modulo 337, drawn as the letter ρ
How long x² + 1 runs before repeating, over 400 primes
Pollard's method splitting 8051
What Pollard's method costs, against the smaller prime
Nobody alone: a half at 3,064 people
What it checks while it draws
Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.
- the near-birthday chance at k = 0 is a distinct-birthday chance on a shorter year ×7
- 22 is still under a half ×1
- 23 is over it ×1
- a block is between 2 and 365 days ×1
- a group smaller than the calendar ×1
- a match within a day needs 14 ×1
- a seasonal swing is between nothing and the whole mean ×1
- a spike holds more than its fair share and less than everything ×1
- a tail and a cycle short enough to draw ×1
- a weekend day is thinned, not removed or boosted ×1
- an exact match needs 23 people ×1
- an uneven calendar has at most as many effective days as it has days ×1
- and its mean length is within ten per cent of √(πp/2) ×1
- and no calendar needs a bigger room than the even year ×1
- and the threshold only falls ×1
- and where it misses, the calendar needs one MORE person than its effective days predict, never one fewer ×1
- at the last step the two agree modulo the factor found ×1
- before the last step they agree modulo neither prime ×1
- between 4 and 24 slots, every one possible ×1
- evening the two days raises the chance that nobody matches ×1
- every product was split ×1
- n is a product of two primes ×1
- n is a whole number below a trillion ×1
- nobody is alone at 3,064 ×1
- nobody is alone in a room of 3,064, more likely than not ×1
- one person shares with nobody ×1
- somebody shares at 23 ×1
- the chance of a match only rises as the calendar grows more uneven ×1
- the curve bends downward ×1
- the curve is symmetric about the even split ×1
- the day-probabilities add to one ×1
- the effective number of days places the threshold within one person ×1
- the even year's threshold is 23 ×1
- the expected number of loners peaks when the room is as large as the year ×1
- the half-way point is 23 people ×1
- the highest point is the even split ×1
- the last new value leads back into the cycle ×1
- the modulus is a prime of at most 5000 ×1
- the pair count is k choose 2 ×1
- the sample holds the primes asked for ×1
- the search ends with a proper factor within forty steps ×1
- the second differences are constant, so the curve is a parabola ×1
- the simulation agrees with the exact walk ×1
- the simulation agrees with the formula ×1
- the steps grow as roughly the square root of the smaller prime ×1
- the sweep is seasonal or weekly ×1
- the sweep starts at the even year ×1
- the symmetric-polynomial count agrees with the product on an even year ×1
- the three thresholds come in this order ×1
- the threshold follows the square-root estimate to within a couple of people ×1
- the two pointers meet within tail plus cycle steps ×1
- the uneven calendar is never less likely to produce a match ×1
- the view is one of pairs, uneven, merge, sweep, effective, rho, rholength, pollard, cost, near, circle, spacing, nearscale, strong, loners, thresholds, smallyear ×1
- the walk's survival stays within ten points of the birthday curve everywhere ×1
- they meet at a multiple of the cycle length, once both are on the cycle ×1
- two different slots ×1
- what it returns divides n ×1
Where it is called
Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.
A collision that finds a factor
A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.
ProbabilityA room where nobody is alone
Twenty-three people probably include two who share a birthday. How many are needed before every single person shares a birthday with somebody else in the room? The answer is 3,064 — more than it takes for every day of the year to be somebody's birthday — and the reason is a count of loners, which rises as the room fills, peaks at 134 when the room is the size of the year, and then falls so slowly that the last loner lingers for thousands of arrivals.
ProbabilityAny unevenness brings the match sooner
Real birthdays are not spread evenly across the year, and every such departure pushes the famous twenty-three down rather than up. The proof is one move on two days at a time, and what it leaves behind is a single number — the one ecologists use to count species.
ProbabilityFourteen people within a day
Twenty-three people probably include two with the same birthday. Fourteen probably include two whose birthdays are at most a day apart, and seven, two within a week. The near miss has an exact formula, found by a trick that takes k days away after every birthday and turns the question back into the plain one on a shorter year, and the pattern behind every threshold is a single square root: a window of k days either side makes each pair 2k + 1 times as likely to collide.
ProbabilityHow long until every one turns up
Draw at random from six equally likely kinds until all six have appeared. The wait is not six draws, and it is not sixty; it is fourteen point seven, and the number is a harmonic sum wearing a hat.
ProbabilityNobody gets their own hat
Hand back a pile of hats at random and ask for the chance that not one person gets their own. The answer barely moves as the crowd grows — it is a third and a bit at four people, and a third and a bit at four thousand.
ProbabilityTwenty-three people
A room needs 253 people before someone probably shares a birthday with you. It needs 23 before two of them probably share one with each other. The gap between those numbers is the whole problem.