Math
Birthdays and collisions
People arrive on a ring of days until two share one: in a year of 365 that is the 23rd person, not the 183rd, on Mars the 32nd, in 65 536 hash buckets the 302nd - runs against the exact curve, the days swept by dragging from a year to 2³², the square-root rule read live, and a task on the Martian room.
What happens
A ring of days. People arrive one at a time and light the day they land on; the first time somebody lands on a lit day the ring flares and the run is over. In a year of 365 days that happens around the 23rd person - not the 183rd, because the question is not whether someone shares your birthday but whether any two of them share one, and there are 253 pairs among 23 people. The exact curve is 1 − (1 − 1/m)(1 − 2/m)…(1 − (n − 1)/m): 50.7 % at 23, 99 % at 57. Runs follow runs, and the chart fills the empirical fraction in over the curve. Drag across the ring and the number of days sweeps on a log scale: a Martian year of 687 days needs 32 people, a hash table of 65 536 buckets collides at the 302nd key, a 32-bit hash at about the 77 000th - the room that collides with a coin's chance follows √(2m ln 2), the square root of the days, not the days. That is why a hash must have far more buckets than keys, and why the birthday attack is the cheapest way to break a short signature.
Equations used in the module
Equations collision by n: P = 1 − (1 − 0/m)(1 − 1/m)…(1 − (n − 1)/m); 365 days: 22 people 47.6 %, 23 people 50.7 %, 57 people 99 %; the expected first collision is the 24.617th person the coin-flip room (smallest n with P ≥ ½): 365 → 23, Mars 687 → 32 (52.0 %; 31 gives 49.7 %), 65 536 buckets → 302, 2^32 → 77 164 the square-root rule: n ≈ √(2m ln 2) = 22.5, 30.9, 301.4, 77 162.7 - the room grows with the square root of the days, not the days runs: one draw per person, day = floor(r·m), through the shared xorshift; seed 1 in 365 days: the 40th person lands on day 200, taken by the 34th; seeds 1…1000: 518 collide by 23, mean first collision 24.05 hashes: the same arithmetic for keys into buckets - a 32-bit hash is expected to collide after about 77 000 keys
