0
$\begingroup$

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}$.)

$\endgroup$
8
  • $\begingroup$ Why is min(14) 16? I thought 11 is an upper bound. $\endgroup$ Dec 3, 2013 at 16:25
  • $\begingroup$ Unless I am missing something, it should be the smallest prime power larger than n/2, or near that. $\endgroup$ Dec 3, 2013 at 16:31
  • $\begingroup$ @TheMaskedAvenger : Thank you for pointing it out. I edited. I agree with your conjecture, but I'm interested in the 'near that'. For $N=2008$, $1005\cdot a_{1005}=1005$ is the min because $1005$ has a big prime number $67$. $\endgroup$
    – mathlove
    Dec 3, 2013 at 16:38
  • $\begingroup$ More precisely, let c be smallest such that c + n/2 is an integer with prime factor larger than square root of n. Then c + n/2 is an upper bound of min(n). $\endgroup$ Dec 3, 2013 at 16:42
  • $\begingroup$ You should look up distribution of smooth numbers. The answer here is likely next nonsmoothnumber after n/2. $\endgroup$ Dec 3, 2013 at 16:43

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Now consider the power of a prime dividing a central binomial coefficient. You should get an almost guaranteed upper bound of N/2 plus c logN for c less than 1. In fact plus c loglogN seems likely. $\endgroup$ Dec 4, 2013 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.