2
$\begingroup$

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)!)$ ?

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .