Since the multiplication of $n$ consecutive integers is divided by $n!$, then $(n!)^n|(n^2)!$ with $n$ is a positive integer.

Are there any formula of the function $y=f(x)$ that shows the largest number $y$ in which $(x!)^{x+y}|(x^2)!$ with $x>1$. If so, for a positive integer $y$, are there infinitely many $x$ such that $(x!)^{x+y}|((x^2)!)$ (with $x, y, n$ are all positive integers) ?

If not, what are the conditions of $m$ so that there are infinitely many $x$ such that $(x!)^{x+m}|((x^2)!)$ ? (with $m$ is a positive integer and $m \leq y$) (For example, with $m=2015$, are there infinitely many $x$ such that $(x!)^{x+2015}|((x^2)!)$ ?

  • $\begingroup$ You could generate the first 50 terms or so with a computer, subtract one from each and use oeis.org $\endgroup$ – Martin Rubey Oct 21 '18 at 10:27
  • $\begingroup$ (sorry, subtracting one was nonsense) $\endgroup$ – Martin Rubey Oct 21 '18 at 12:19
  • $\begingroup$ "Computationally" the progression is oeis.org/A187279 $\endgroup$ – Xarles Oct 21 '18 at 16:22

$\newcommand{\eps}{\varepsilon}$It seems that for any $y$ the number of such $x$ is infinite.

First of all, let's fix a prime $p$ and compute $v_p(\frac{(x^2)!}{(x!)^x})$ -- the exponent of $p$ in the prime factorization of this ratio. For any natural number $n$ we have $v_p(n!)=\frac{n-S_p(n)}{p-1}$ where $S_p(n)$ is the sum of digits in the base p expansion of $n$. So, we get $$v_p(\frac{(x^2)!}{(x!)^x})=\frac{x^2-S_p(x^2)}{p-1}-x\frac{x-S_p(x)}{p-1}=\frac{xS_p(x)-S_p(x^2)}{p-1}$$

Thus, a number $y$ satisfies $(x!)^{x+y}|(x^2)!$ if and only if for every prime $p$ th inequality $y\frac{x-S_p(x)}{p-1}\leq \frac{xS_p(x)-S_p(x^2)}{p-1}$ holds. As was obvious from the beginning, $x!$ is only divisible by primes not greater than $x$ so let's assume $p\leq x$. We then get that the maximal $y$ such that $(x!)^{x+y}|(x^2)!$ is given by $\min\limits_{p\leq x}\frac{xS_p(x)-S_p(x^2)}{x-S_p(x)}$. The function $S_p(x)$ is hard to compute explicitely but, for sure, there is an estimate $S_p(x)\leq (p-1)(\log_p(x)+1)$. So, for a fixed $p$ as $x$ tends to $\infty$ the expression $\frac{xS_p(x)-S_p(x^2)}{x-S_p(x)}$ is asymptotically equivalent to $S_p(x)$. However, here as $x$ gets bigger we should take into account bigger and bigger primes.

Anyway, let's prove that $f_p(x):=\frac{xS_p(x)-S_p(x^2)}{x-S_p(x)}$ is not much smaller than $S_p(x)$ for every $p$ and then, using the prime number theorem we'll find infinitely many $x$ such that $S_p(x)$ is bigger than a fixed number $y$ for every $p$.

We have $f_p(x)=S_p(x)+\frac{S_p(x)^2-S_p(x^2)}{x-S_p(x)}$. Let's separately consider cases $p> \sqrt{x}$ and $p\leq\sqrt{x}$. In the first case we have $\frac{S_p(x)^2-S_p(x^2)}{x-S_p(x)}>-\frac{4(p-1)}{p-1}=-4$ because $x^2$ has at most $4$ digits. So $f_p(x)>S_p(x)-4$. If $p\leq \sqrt{x}$ then $x\geq p^2$. Pick number $k$ such that $p^k\leq x<p^k+1$. We have $\frac{f_p(x)}{S_p(x)}=1+\frac{S_p(x)-\frac{S_p(x^2)}{S_p(x)}}{x-S_p(x)}\geq 1+\frac{-(p-1)(2k+2)}{p^k-1}=1-\frac{2k+2}{p^{k-1}+..+p+1}\geq 1-\frac{2k+2}{p(k-1)}\geq 1-\frac{7}{p}$ because $k\geq 2$.

Thus, there exists a positive constant $\eps$ such that for big enough $x$ we have $f_p(x)>\eps S_p(x)$ for every prime $p\leq x$(strictly speaking, the inequality above shows this only for $p>7$ but any finite set of primes can be easily covered by the above remark about the asymptotics of $S_p(x)$).

Let's now fix number $y$ and denote by $\mathcal{B}_y(N)$ the number of integers in $[1, N]$ which have $S_p(-)$ less than $y$ for some number $p\leq N$. For a given prime $\#\{x|S_p(x)<y,x\leq N\}$ is smaller than $\binom{\log_pN+1+y}{y}y^y$ -- because such number $x$ has at most $\log_pN+1$ digits, at most $y$ of them are non-zero, and every non-zero digit is at most $y$(I've added $y$ to $\log_pN+1$ to account for the case when $log_p+1<y$ -- this is a very rough estimate, of course). By the prime number theorem, for big enough $N$ the number of primes smaller than $N$ is smaller than $\frac{3}{2}\frac{N}{\ln N}$ (of course, $\frac{3}{2}$ can be replaced by any number bigger than $1$). Combining these two observations get $$\mathcal{B}_y(N)<\sum\limits_{p<\sqrt{N}} \binom{\log_2 N+y+1}{y}y^y+\sum\limits_{N\geq p\geq \sqrt{N}}\binom{\log_{\sqrt{N}}N+y+1}{y}y^y<\frac{3}{2}\frac{\sqrt{N}}{\ln\sqrt{N}}\binom{\log_2 N+y+1}{y}y^y+\frac{3}{2}\frac{N}{\ln N}\binom{y+3}{3}y^y<C(y)(\frac{\sqrt{N}}{\ln\sqrt{N}}(\log_2 N+y+1)^y+\frac{N}{\ln N})$$ where $C(y)$ is a constant depending only on $y$.

Thus, $\lim \frac{\mathcal{B}_y(N)}{N}=0$ so, for a given $y$ the set of $x$ satisfying your condition even has density $1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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