For all natural numbers $n$, define $f(n) = \tau (n!) - \tau ((n-1)!)$, where $\tau(a)$ denotes the number of positive divisors of $a$. Prove that there exist infinitely many composite $n$, such that for all naturals $m < n$, we have $f(m) < f(n)$.
Problem
Source: China Team Selection Test 3 Day 2 P3
Tags: number theory, function
26.03.2015 20:40
We show that $n = 2p$ works for all odd primes $p$. Lemma: $f(n) \le \tau(n!)/2$ for all positive integers $n>1$.
Define $A = (2p-1)!/p$ and let $A = 2^rs$ with $s$ odd. Then, $f(2p) = \tau(p^2s2^{r+1})-\tau(ps2^r)=(r+4)\tau(s) = \tau(8A)$. Let $m < 2p$. Then $f(m) \le \tau(m!)/2 $. For $m \le p$, $\tau(m!)/2 \le \tau((p-1)!) \le \tau(A)$. Otherwise, $\tau(m!)/2 = \tau(p)\tau(m!/p)/2 $ $=\tau(m!/p) $ $\le \tau(A) \le f(2p)$, and we are done. EDIT: I realised last night this is quite horribly wrong, as the next post points out, although I think the lemma is true.
27.03.2015 02:11
The map above appears not to be an injection.
27.03.2015 18:24
I hope to God there is an elementary proof using the injection idea, because what follows is entirely analytic. Throughout the solution, $p$ denotes primes. Proving the lemma for sufficiently large $n$ is enough to complete the problem. Since the case with $n$ prime is trivial, assume $n$ is composite. Note that \[ \frac{\tau(n!)}{\tau((n-1)!)} = \prod_{p|n} \frac{1+v_p(n!)}{1+v_p((n-1)!)} = \prod_{p|n} \left( 1+ \frac{v_p(n)}{1+v_p((n-1)!)} \right) \]Since $p|n$, the last multiple of $p$ before $n$ is $n-p$. Therefore, $v_p((n-1)!)+1 = v_p((n-p)!)+1 \ge n/p$. So, it is sufficient to show that \[ P = \prod_{p|n} \left( 1+ \frac{pv_p(n)}{n} \right) \le 2 \]Note that $pv_p(n) \le n$ $\forall p|n$ and also, $\sum_{p|n} pv_p(n) \le n$. We shall use the fact that $1+x \le e^x$ $\forall x \in \mathbb{R}$. Suppose first, that all prime factors of $n$ are $\le \sqrt{n}$. Then, we obtain \[P \le \text{exp} \left( \sum_{p|n} \frac{pv_p(n)}{n} \right) \le \text{exp} \left( \frac{1}{\sqrt{n}}\sum_{p|n}v_p(n) \right) \le \text{exp}\frac{\text{log}_2(n)}{\sqrt{n}} \le 2\]Otherwise, let $q|n$, such that $q > \sqrt{n}$. Now, $q^2 \nmid n$ and all other prime factors must be $\le \sqrt{n}$. Then, for large $n$, \[ P = \left( 1+\frac{q}{n} \right) \prod_{\substack {p|n \\ p \le \sqrt{n}}} \left( 1+\frac{pv_p(n)}{n} \right) \le \frac{3}{2} \text{exp}\frac{\text{log}_2(n)}{\sqrt{n}} \le 2\] Let $N$ be such that the lemma is true for all $n>N$. Take prime $p > N$. We show that $2p$ serves our purpose. Using the definitions from my previous post, if $m < p$, we have $f(m) < \tau(m!) \le \tau(A)$. Also, $f(p) = \tau((p-1)!) \le \tau(A)$. And for $p < m < 2p$, $f(m) \le \tau(m!)/2 $ $\le \tau(m!/p) $ $\le \tau(A)$. Since $\tau(A) < f(2p)$ we are done.
02.04.2015 09:23
Well,$f(n)$ is precisely the number of divisors of $n!$ which do not divide $(n-1)!$.Take any such divisor $d$ and note that $\frac{d}{(d,m)}$divides $(n-1)!$.Hence from this it is easy that $f(n) \le \frac{d(n!)}{2}.$ because at most half of the divisors of $n!$ can be such that it does not divide $(n-1)!$ from the above argument. And regarding the problem,there is a result which states $ \frac{d(n!)}{d((n-1)!)}=1+\frac{P(n)}{n}+O(\frac{1}{n^{\frac{1}{2}}})$ where $P(n)$ is the largest prime dividing $n$.Putting $n=2p$ gives $P(2p!) >\frac{3}{2}(d((2p-1)!)$ and hence $f(2p) >\frac{d((2p-1)!}{2} \ge \frac{d(m!)}{2} \ge f(m)$ for all $m<2p$ and hence the problem.
02.04.2015 12:21
Drunk or not, you need to show that there don't exist $a,b$ such that $a/(a,n) = b/(b,n)$.
02.04.2015 22:22
Here goes the link. https://math.dartmouth.edu/~carlp/factorial.pdf And I think it has everything needed. I have been stupid enough not to see that the very paper from which I gathered the result stated in my previous post also had the proposition that both $p$ and $2p$ are champs.(required kind of numbers)
05.04.2015 04:58
My first step is the same as dibyo_99. The trick is this: $ P= \prod_{p \mid n}^{ }(1+\frac{pv_{p}(n)}{n}) \leq \prod_{p \mid n}^{ }(1+\frac{p^{v_{p}(n)}}{n}) $. Let's say $ n=p_{1}^{e_{1}}p_{2}^{e_{2}}...p_{k}^{e_{k}} $. Then, $ P \leq \prod_{i=1}^{k}(1+\frac{p_{i}}{\prod_{i=1}^{k}p_{i}}) $. And we know that $ \frac{p_{1}...p_{k}}{p_{i}}\geq p_{1}...p_{k-1}+k-i\geq 2^{k-1}+k-i\geq 2k-i $ . So, $ P\leq \prod_{i=1}^{k}(1+\frac{1}{2k-i})=2 $ and the proof is complete.
16.04.2015 19:04
mathdebam wrote: Here goes the link. https://math.dartmouth.edu/~carlp/factorial.pdf And I think it has everything needed. I have been stupid enough not to see that the very paper from which I gathered the result stated in my previous post also had the proposition that both $p$ and $2p$ are champs.(required kind of numbers) I might be missing something, but the proof in this paper appears to be wrong. Although, the other facts proven in this paper imply the fact that both $p$ ad $2p$ are champs. It says that, if $d|m!$ and $d \nmid (m-1)!$, then $d/m|(m-1)!$, and counts that in the injection, however $d/m$ needn't be an integer.
24.02.2016 17:57
We prove $P \le 2$ differently. Set $n=\prod_{i=1}^k p^{e_i}_i$ with $p_1 \le p_2 \le \cdots \le p_k$. Assume $n$ is composite. As $p_i \ge 2$ for all $i$, we have $p_i \ge \sqrt[e_i-1]{e_i}$. This gives $$P= \prod_{i=1}^k \left(1+\frac{p_ie_i}{n}\right)\le \prod_{i=1}^k \left(1+\frac{p^{e_i}_i}{n}\right) = \prod_{i=1}^k \left(1+\frac{1}{\prod_{j\not= i} p^{e_j}_j}\right) \le \prod_{i=1}^k \left(1+ \frac{1}{\prod_{j\not= i} p_j} \right)$$ Assume that $k \ge 3$. Using $1+x \le e^x$, we find $$P \le \prod_{i=1}^k \left(1+ \frac{1}{\prod_{j\not= i} p_j} \right) \le \text{exp}\left(\sum_{i=1}^k \frac{1}{\prod_{j\not= i} p_j}\right) \le \text{exp}\left(\frac{1}{p_1p_2}+\frac{1}{p_2p_3}+\frac{1}{p_3p_1}\right) \le \text{exp}\left(\frac{1}{6}+\frac{1}{15}+\frac{1}{10}\right) = \sqrt[3]{e} < 2$$ Now we just need to verify $k=2$. This is easy, as $$P \le \left(1+\frac{1}{p_1}\right)\left(1+\frac{1}{p_2}\right) \le \left(1+\frac{1}{2}\right)\left(1+\frac{1}{3}\right) =2$$so we conclude - $P \le 2$ as required.
28.05.2016 15:05
My solution: It is easy to check that for every odd prime $p$ ,we have $f(x) < f(2p)$ for all $x$ that are smaller than $p$ and$f(q) < f(2p)$where $q$ is a prime integer smaller than $2p$ and let $M$ be the integer such that $f(m)$ is the largest one among $f(1), f(2),……,f(2p-1),f(2p)$ if there exist many numbers satisfying this ,choose $M$ to be the smallest one.According to our above discussion ,we know that $M$ is not a prime ,so clearly $M$ is what we want ,notice that we have infinite primes ,then we are down.
11.05.2020 00:46
Here's an elementary solution by Kassuno, rkm0959, and SyavAshbringer (who apparently doesn't have AoPS oops). Claim: For every odd prime $p,$ there exists a composite integer $k$ in the interval $(p,2p]$ such that $f(i)<f(k)$ for every $i<p.$ Proof: Pick $k$ such that $f(k)$ is the maximum of $f$ over the interval $[0,2p];$ in case of equality, choose the smallest $k.$ By definition $f(i)<f(k)$ for every $i<k,$ so we just need to show that $k$ is composite and in $(p,2p].$ Since $\nu_p((2p-1)!)=1$ and $\nu_p((2p)!)=2,$ we must have $\tau((2p)!)>\tfrac{3}{2}\tau((2p-1)!).$ Note that the inequality is strict because of the extra factor of $2,$ so \[f(2p) = \tau((2p)!) - \tau((2p-1)!) > \frac{3}{2}\tau((2p-1)!)-\tau((2p-1)!) = \frac{1}{2}\tau((2p-1)!).\]Next, let $q$ be an arbitrary prime. Since $\tau(q!)=2\tau((q-1)!),$ this means that $f(q)=\tau(q!)-\tau((q-1)!)=\tau((q-1)!),$ so if we additionally require that $q < 2p,$ then we have \[f(2p)=\tau((2p)!)-\tau((2p-1)!)>\frac{1}{2}\tau((2p-1)!)\ge\frac{1}{2}\tau(q!)=\tau((q-1)!)=f(q).\]This means $f(2p)>f(q),$ which implies that $f(k)$ has to be at least $f(2p),$ a composite number, whence $k$ is necessarily composite as well. Now, since $\sum_{i=0}^{p-1}f(i)=\tau((p-1)!)=f(p),$ we must have $f(i) < f(p)$ for every $i<p,$ so $k$ also has to be greater than $p,$ which means that $k$ satisfies all of our requirements. $\Box$ Back to the main problem: It now suffices to show that there are infinitely many disjoint intervals $(p,2p],$ but this is pretty obvious. In particular, since there are infinitely many primes, for any prime $p,$ we're guaranteed to be able to find another prime $q$ that is greater than $2p,$ so clearly $(p,2p]$ and $(q,2q]$ are disjoint, and we can repeat this process infinitely. $\blacksquare$
20.05.2020 15:01
Assume to the contrary that the problem is not true. Of course, for any prime $p$, we have $f(p)=\tau((p-1)!)$ and it is easy to show from here that $n<p$ implies $f(n)<f(p)$ (if a number $m$ has this said property, call $m$ to have property $P$). So, if the problem is not true, there exists a positive integer $N$ such that any integer $n>N$ has the property $P$ if and only if $n$ is prime. So, if $p_k$ denotes the $k^{th}$ prime, then for all sufficiently large $k$, we can see that the problem being false implies that for any integer $p_k<t<p_{k+1}$, $f(t) \leq \tau((p-1)!)$. However, it is easy to see that if $p$ is an odd prime, $f(2p)>\frac{\tau((2p-1)!)}{2}$. So, if we take a sufficiently large prime $p$ such that $2p-1$ isn't prime (there exist infinitely many such primes because it is easy to prove existence of infinitely many primes of the form $6k-1$) and then consider the positive integer $j$ with $p_j+1<2p<p_{j+1}$, we get $f(2p)>\frac{\tau((2p-1)!)}{2}>\frac{\tau(p!)}{2}=\tau{(p-1)!}$. This contradicts the earlier result we got, hence the problem cannot be false. So, it must be true. Proved
15.04.2021 14:49
19.08.2021 20:37
We claim that $N=2p$ works for all odd primes $p$ Firstly we will try to calculate $F(2p)=(2p)!-(2p-1)!$ Notice that if $(2p-1)!=px$ then $(2p)!=2 p^2 x$ and so by the chain of inequalities we get:- $F(2p)=(2p)!-(2p-1)!=\tau(2p^2 x)-\tau(px)=\tau(2p^2) \tau(x) -\tau(p) \tau(x)> 3 \tau(x)- 2 \tau(x)=\tau(x)$ (Since $\tau(2x) > \tau(x)$) Now we will show that for all $m \in [2,3,4,5,6.......,2p-1]$ we must have $f(m) \le \tau(x)$ Hence:-$F(m) \le \frac{\tau({m!})}{2} \le \frac{ \tau(2p-1)!}{2}= \frac{\tau(px)}{2}=\tau(x)$,as required.