Finding the min of a sequence related with factorials

Question

Let $N,n$ be natural numbers.

Let us define $a_n=m$ when $N!$ can be divided by $(n!)^m$ and it cannot be divided by $(n!)^{m+1}$.

For a given $N(\ge 2)$, let $\min(N)$ be the min of $na_n\ (2\le n\le N)$.

Then, here is my question.

Question : What is $\min(N)$?

Example :

$$\min(2)=2,\min(3)=2,\min(4)=3,\min(5)=3,\min(28)=16,\min(2008)=1005.$$

Remark : This question has been asked previously on math.SE without receiving any answers.

Motivation : I've known a question to find $\min(2008)$. Then, I got interested in its generalization. However, I cannot find any good way to find $\min(N)$ in general. I'm afraid that this question might be solved only by brute-force computer search.

Note that it is not true that $\min(2k)=k+1$. See the above $k=14$ case.

By the way, we can lead $na_n\approx N$, which shows the meaningfulness to treat $na_n$.

The exponent of a prime $p$ of $N!$ can be represented as $$\sum_{k=1}^{\infty} \left\lfloor{\frac{N}{p^k}}\right\rfloor\approx \sum_{k=1}^{\infty} \frac{N}{p^k}=\frac{N/p}{1-1/p}=\frac{N}{p-1}.$$ On the other hand, the exponet of a prime $p$ of $n!$ can be represented as $$\sum_{k=1}^{\infty} \left\lfloor{\frac{n}{p^k}}\right\rfloor\approx \cdots =\frac{n}{p-1}.$$ Hence, by considering these ratio, we get $a_n\approx\frac{N}{n}$, namely, $na_n\approx N$.

The followings are the examples of the $N=2008$ case.

$$8\cdot a_8=2280, 9\cdot a_9=2250, 10\cdot a_{10}=2500, 11\cdot a_{11}=2189,12\cdot a_{12}=2388,$$ $$13\cdot a_{13}=2145, 14\cdot a_{14}=2310, 15\cdot a_{15}=2475, 16\cdot a_{16}=2128,17\cdot a_{17}=2108,$$ $$18\cdot a_{18}=2232, 19\cdot a_{19}=2090, 20\cdot a_{20}=2200, 21\cdot a_{21}=2310,22\cdot a_{22}=2178,$$ $$23\cdot a_{23}=2070, 24\cdot a_{24}=2160.$$

(By the way, we can prove that the max of $na_n\ (8\le n\le 2008)$ for the $N=2008$ case is $2500=10\cdot a_{10}$.)

Answer 1

Lemma: Let $n,a$, be positive integers with $r = n \bmod a$, the remainder after dividing $n$ by $a$. Using Iverson notation [statement] is $1$ if true, $0$ otherwise, $\lfloor 2n/a \rfloor = 2\lfloor n/a \rfloor + [2r \geq a]$.

From this, one shows that the exponent of a prime $p$ in a prime factorization of $C_n={n \choose {\lfloor n/2 \rfloor}}$ is at most $\log_p n$, and is more likely to be about half of that if it is nonzero, by looking at the base $p$ expansion of $n$.

Now suppose $n = c + \lfloor N/2 \rfloor$ and $a_n \gt 1$. Then $P= n!/(n-c)!$ is such that $P^2$ divides $C_N$. For large $N$, $c$ should be bounded by $\min_{p^2 \leq N} pe_p/2$ where $e_p$ is the largest power of $p$ dividing $C_n$. An upper bound that should be tight in general is to look at $p=2,3$ and $5$ and use the minimum based on those. For other bounds, find a prime $q$ with $q^2 \gt N$ and $N/2 \bmod q$ close to $q$: the next multiple of $q$ after $N/2$ is also an upper bound. I do not know how to find $\min(N)$ algebraically, but it is clear one does not have to look far from $N/2$.

There are similar problems depending on sequences of smooth numbers as well as divisibility by small primes. In addition to one-complexity of an integer, my MathOverflow favorite can be found at Factorials in Pascals Triangle. Perhaps a compilation of these can be solved with an appropriate literature search.

Gerhard "Ask Me About Small Factors" Paseman, 2013.12.04

Answer 2

I've just found that we can easily get $\min(N)$ in the following way, but a more direct answer is welcome. Thanks to The Masked Avenger's comment above, I've just got the following :

$\min(N)=M$ where $M$ is the minimum number which satisfies $$a_M=1,\ \ \left\lfloor\frac{N}{2}\right\rfloor +1\le M\le N^{\prime}.$$ Here, $N^{\prime}$ is the minimum number in the form of $p^k\ (k\ge 0\in\mathbb Z)$ where $p$ is a prime number.

Proof : Let $h(n)=na_n$. We can see if $\{(kn)!\}^{a_{kn}}$ can divide $N!$, then $(n!)^{ka_{kn}}$ can also divide $N!$ because for $k\in\mathbb N$, $$\{(kn)!\}^{a_{kn}}=\left(\binom{kn}{n}\cdot\binom{(k-1)n}{n}\cdots\binom{n}{n}\right)^{a_{kn}}\times (n!)^{ka_{kn}}$$ holds. Hence, we get $a_n\ge ka_{kn}.$ Multiplying the both sides by $n$ gives us $h(n)\ge h(kn).$

Thus, letting $M$ be the minimum number such that $a_M=1$, we get the followings :

$(1)$ For $n$ such that $n\le M-1$, since we know that for each $n$ there exists $k\in\mathbb N$ such that $M\le kn\lt N$, we get $h(n)\ge h(kn)=kna_{kn}\ge kn\ge M$.

$(2)$ For $n=M$, $h(n)=h(M)=Ma_M=M\times 1=M.$ (Note that $a_n$ is a monotone decreasing sequence.)

$(3)$ For $n$ such that $M\lt n\le N$, since $a_n=1$, we get $h(n)=na_n=n\gt M.$

Hence, we lead that $\min(N)=M$.

In addition to this, noting that

$$\frac{(2m)!}{m!m!}\in\mathbb N, \frac{(2m-1)!}{(m-1)!(m-1)!}\in\mathbb N,$$ we can see that $M\ge m+1$ for $N=2m$, and that $M\ge m$ for $N=2m-1$. These can be represented as $\left\lfloor\frac{N}{2}\right\rfloor +1\le M.$ On the other hand, $M\le N^{\prime}$ is obvious where $N^{\prime}$ is the minimum number in the form of $p^k\ (k\ge 0\in\mathbb Z)$ where $p$ is a prime number. Q.E.D.

As I mentioned at the top of this answer, a more direct answer is welcome; especially I would like to see a better pair $(a,b)$ to estimate $M$ such that $a\le M\le b$.