Greatest common divisor of $n!$ and $ H_n n!$

159 Views Asked by At

Let $H_n$ be the $n$th harmonic number, ie. $H_n=1+\frac{1}{2}+\frac{1}{3}+ \cdots+\frac{1}{n} .$

I would like to get the value of $\gcd(n!,H_n n!)$, where $\gcd$ is the greatest common divisor, ie, the largest number that divides both $n!$ and $H_n n!$.

Now $H_n = \frac{\sum_{k=1}^n \frac{n!}{k}}{n!}.$ So $H_n n! = \sum_{k=1}^n \frac{n!}{k}.$ So the question becomes what is the $\gcd(n!,\sum_{k=1}^n \frac{n!}{k}).$

We know that $\omega(n!) = \pi(n)$, where $\omega(x)$ counts distinct prime factors of $x$ and $\pi(x)$ is the number of primes not exceeding $x$.

We also see that $\pi(\frac{n}{2})\le\omega(\sum_{k=1}^n \frac{n!}{k})$. This is because all the primes that are smaller than $n/2$ are found at least once in every fraction.

Assume that $n!$ has a factorization $p_1^{t_1}p_2^{t_2}\cdots p_{\pi(n)}^{t_{\pi(n)}}.$ If $p_m < n/2$, then $p_m | H_n n!$.

Every number between 2 and $n$ divisible by $p_m$ increments the exponent of $p_m$ by a number equal to the number of times the number is divisible by it. Assume that $l$ is the greatest multiple of $p_m$ between 1 and $n$. Then the exponent of $p_m$ in the factorization of $h_n n!$ is at least $m-l$, because every other number divided away removes less $p_m$ multiples than the one with exponent $l$.

Example: $9! = 2^7 3^4 5^1 7^1$. $H_9 9! = 2^4 3^2 7129^1$. The greatest multiple of $2$ between 2 and 9 is 3 from 8. In the latter this is divided away in one, thus reducing the number of times the whole is divisible by 2 by 3. Hence 2 has exponent 4 at the latter number.

What I am especially interested is the fact that the factorization of $H_n n!$ seems, according to computer experiments, to contain vast primes, far greater than $n$. Can we get some information about these?

Lastly it is obvious that $\gcd(n!,H_n n!)<n!,$ for $H_n$ is not an integer.

1

There are 1 best solutions below

1
On BEST ANSWER

As you noted: If $p\le \frac n2$ then $\frac {n!}k$ is a multiple of $p$ for all $k$ because at least two factors of $n!=1\cdot2\cdots n$ are multiples of $p$ and $k$ cancels at most one. More precisely, the exponent of $p$ in $n!$ is $e_n=\lfloor \frac np\rfloor+\lfloor\frac n{p^2}\rfloor +\ldots\approx \frac n{p-1}$ and the exponent of $p$ in $H_nn!$ (and therefore in the $\gcd$) is at least $e_n-\lfloor \log_pn\rfloor $ (from the highest prime power occuring as denominator), so the small primes occur in quite high powers if $n$ is big.

But if $\frac n2<p\le n$, then precisely the summands $\frac {n!}k$ with $k\ne p$ are multiples of $p$, whereas $\frac{n!}p$ is not. Therefore $\gcd(n!,H_nn!)$ is $\frac n2$-smooth and also a multiple of $\frac n2\#$. Consequently all remaining prime factors of $H_nn!$ must be $>n$. In fact, you can find these excess factors $$\frac{H_nn!}{\gcd(n!,H_nn!)} $$ as sequence A001008 in OEIS.