Median factor of factorials

88 Views Asked by At

What is the order of $m(N)$, the median prime in the prime factorization of $N!$, as $N\to\infty$? For example, $m(6)=2$ because $6!=2^4\times3^2\times5$ and the median of $\{2,2,2,2,3,3,5\}$ is $2$.

For clarification, when the median is ambiguous, I take the arithmetic mean of the two most central terms.

I’m unsure as to how to attack this problem directly, given my uncertainty with statistics and its intersection with factorials and working with finding the order of almost anything (I have so far not learned Big O notation or anything I perceive to be relevant to something like this in school).

However, I did produce a Desmos graph showing the first $32$ cases: https://www.desmos.com/calculator/gew0pvjlfz

It seems to me to indicate that the median factor does likely increase to some degree as $N$ increases in general, though it is clearly not monotonic.

1

There are 1 best solutions below

0
On BEST ANSWER

For any prime $p\le N$, the multiplicity with which $p$ divides $N$ equals $$ \biggl\lfloor \frac Np \biggr\rfloor + \biggl\lfloor \frac N{p^2} \biggr\rfloor + \biggl\lfloor \frac N{p^3} \biggr\rfloor + \cdots = \frac N{p-1} + O\biggl( \frac{\log N}{\log p} \biggr). $$ Therefore the total number of prime factors of $N!$ equals $$ \sum_{p\le N} \biggl( \frac N{p-1} + O\biggl( \frac{\log N}{\log p} \biggr) \biggr) = N \log\log N + O(N) $$ by Mertens' formula for $\sum_{p\le x} \frac1p$ (and skipping some simplifying steps).

To find the median prime factor $M$, we need to find $M$ such that $$ \sum_{p\le M} \biggl( \frac N{p-1} + O\biggl( \frac{\log N}{\log p} \biggr) \biggr) \sim N \frac{\log\log N}2; $$ the answer (easier to check than to find) is $M \approx e^{\sqrt{\log N}}$. This is a slower rate of increase than any power of $N$, but a faster rate of increase than any power of $\log N$.

My guess, from what you said in your OP, is that a lot of this is math you haven't encountered yet. Don't be discouraged—you have a lifetime to keep learning! You might use this answer as an excuse to read up on some analytic number theory (perhaps in Apostol's book).