This is similar to the Birthday Problem. Given a group of n people, What is the probability that two share the same birthday1? It’s higher than you’d think.
In your case, what are the odds that randomly picking a number between 0 and 1,073,741,823 n times will give you a duplicate?
One approximation from the link above is 1-exp(-(n*n)/(2*d)). If n=40,000 that equates to about a 52.5% probability that a duplicate is chosen, so seeing duplicates after 40,000 picks on average seems reasonable.
1assuming that birthdays are uniformly distributed universally, which is not the case in reality but is “close enough” and makes the math easier