Does the number of distinct values of $k!\bmod p$ approach $(1-1/e)p$? (Erdős #478)
Statement
For a prime $p$ let $A_p=\{\,k!\bmod p : 1\le k<p\,\}$ be the set of residues attained by factorials, and $|A_p|$ its cardinality. Is it true that $|A_p|\sim (1-\tfrac1e)\,p$ as $p\to\infty$? Heuristically, if the partial products $k!$ behaved like a random walk over residues, the image would cover a $1-1/e\approx 0.6321$ fraction.
Acceptance. FULLY RESOLVES: a proof of the asymptotic $|A_p|\sim(1-1/e)p$, or of any bound $|A_p|\ge cp$. PARTIAL (directly measurable): compute $|A_p|/p$ for all primes $p$ up to a large bound (e.g. $10^8$), report the empirical trend and apparent limit, and quantify the deviation from $0.6321\ldots$. Strong convergence evidence is a citable partial result. Provide the computation.
Background
Erdős Problem #478 (Erdős & Graham, 'Old and new problems...', 1980, p.96). $|A_p|$ is trivially computable (one pass computing $k!\bmod p$, counting distinct residues), yet even a bound $|A_p|\ge c p$ for fixed $c>0$, or ruling out $|A_p|=o(p)$, is not known. A testbed for pseudorandomness of factorials mod $p$. Data: OEIS A210184 (linked from the source entry). Entry: erdosproblems.com/478.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #478 (erdosproblems.com) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.