Let $n=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t}$ be the prime factorisation of $n$. Define $\omega(n)=t$ and $\Omega(n)=a_1+a_2+\ldots+a_t$. Prove or disprove: For any fixed positive integer $k$ and positive reals $\alpha,\beta$, there exists a positive integer $n>1$ such that i) $\frac{\omega(n+k)}{\omega(n)}>\alpha$ ii) $\frac{\Omega(n+k)}{\Omega(n)}<\beta$.
Problem
Source: China Mathematical Olympiad 2014 Q4
Tags: induction, logarithms, algebra, number theory proposed, number theory, China
22.12.2013 17:34
Let $p_l$ represent the $l^{th}$ prime and consider $a_n = (2^c\cdot 3\cdot 5.... \cdot p_m)^n$. We will show that there exist $n$ such that $a_n + k$ has arbitrarily many distinct primes dividing it. We proceed by induction. Assume that $q_1,q_2,...,q_j$ divides $a_n + k$ for some $n$. We can assume that the $q_i$s are all $> p_m$ since only a bounded amount ( to be more precise their product is at most $k$) of those $< p_m$ can divide $a_n + k$ for large enough $n$. Let $v_{q_i}(a_n + k) = b_i$ and WLOG let max$(b_i) = b_1$. Consider $a_{n + \phi((q_1q_2...q_j)^{b_1+1})} + k$. It is easy to see that $v_{q_i}(a_{n + \phi((q_1q_2...q_j)^{b_1+1}}) + k = b_i$ for all $i$ and since $a_{n + \phi((q_1q_2...q_j)^{b_1+1})} + k > a_n + k$ we conclude that there exist another prime $q_{j+1}$ dividing it and thus our induction step is done. Now take $m = 2^e$ for some large $e$ and take $n$ such that $a_n + k$ has more than $\alpha m$ prime factors. Then condition (1) holds and suffices to show we can choose $c$ such that condition (2) holds. It suffices to note that $\omega(n+k)$ is at its max when its of the form $k*p_{m+1}^d$ for some integer $d$. Now $p_{m+1} > 2^e$ so $\log_{p_{m+1}}(a_n + k) < n\cdot(\log_{2^e}(2^c) + \log_{p_{m+1}}(3) ... + \log_{p_{m+1}}(p_m)) < n\cdot((m-1) + \frac{c}{e})$. Now take $c = m$ and observe that $\frac{\omega(n+k)}{\omega(n)} < \frac{(m-1)+\frac{m}{e}+\omega(k)}{m^2}$ which for large enough $m$ will be $< \beta$ and we are done.
22.12.2013 18:45
Just for the record, for $n=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t}$ the standard notations are $\omega(n)=t$ and $\Omega(n)=a_1+a_2+\cdots +a_t$.
22.12.2013 19:21
Thanks. edited.
24.12.2013 19:12
It is possible to take $n=2^{p_1p_2...p_m}+1$, where $p_i$ are primes bigger than $N$, and $m,N$ are picked to be arbitrarily large. (This is for $k=1$, since we can take $n\rightarrow kn$).
24.12.2013 19:22
First $\omega(kn)=\omega(n)+O(1)$ and the same for $\Omega$, so we may assume $k=1$. Next, choose $n=2^{m}$, we only need that: (1) $2^{m}+1$ has sufficiently many prime factors, and (2) each prime factor of $2^{m}+1$ is sufficiently large. Just choose $m=q!3^{q}$ for $q$ large.
17.03.2014 07:01
Problem (2) is bit easy by using cyclotomic polynomials when n is prime... Am I wrong? Also 2^3^n+1 has at least n distinct primes, so number (1) is easy either.
24.06.2015 11:04
In Cojocaru's text, the normal order of $\omega(\cdot)$ is investigated and they look at the sum $\sum_{p\le x}\omega(p-1)$. Replacing "$-1$" by "$k$" can prove (1). It's overkill for sure, but it works.
04.09.2015 04:44
Sorry, incorrect solution.
22.09.2019 14:29
misread the problem.
23.09.2019 19:29
I got the statement as i) and ii) hold simultaneously, i.e. could we for any $\alpha, \beta>0 $ and $k\in \mathbb{N}$ find such $n\in \mathbb{N}$ such that i) and ii) both hold?
25.12.2019 07:01
First, we assume $k>1$. Consider $n=k^{2^a\cdot p^b+1}$ where $a$ and $b$ are very large, and $p$ is an odd prime. Note that $\frac{\omega(n+k)}{\omega(n)}=\frac{\omega(k)+\omega\left(1+k^{2^ap^b}\right)}{\omega(k)}$. For any $x$, $1+x^{p^b}$ factors into $b+1$ terms, namely $(1+x)\left(1-x+x^2-\ldots+x^{p-1}\right)\left(1-x^p+x^{2p}-\ldots+x^{p^2-p}\right)\cdots$. However, $x+1$ leaves a remainder of $p$ into $1-x+x^2-\ldots+x^{p-1}$. So, if we choose $p$ such that $p\nmid 1+k^{2^a p^b}$ (easily accomplishable by choosing $p|k$ if $k$ is not a power of $2$, and $p|k-1$ otherwise) we have that all $b+1$ terms are relatively prime, so $\frac{\omega(n+k)}{\omega(n)}>1+\frac{b+1}{\omega(k)}>\alpha$ for large enough $b$. On the other hand, if $q\bigg |1+k^{2^ap^b}$ for some prime $q$, we must have $k^{2^{a+1}p^b}\equiv 1\pmod q$, $k^{2^ap^b}\equiv -1\pmod q$. This means that $\mathrm{ord}_q(k)$ is divisible by $2^{a+1}$, and $q$ must be at least $2^{a+1}+1$. Of course, we can choose $a$ large enough such that $2^{a+1}+1>r^{1/\beta}$, where $r$ is $k$'s largest prime factor. Then, $$\Omega(n+k)\approx \Omega\left(k^{2^ap^b}+1\right)<\log_{r^{1/\beta}}\left(k^{2^ap^b}+1\right)=\beta\log_r\left(k^{2^ap^b}+1\right)$$while $\Omega(n)>\log_r\left(k^{2^ap^b+1}\right)$. Thus, condition ii) is satisfied as well, and we have an $n$ which simultaneously satisfies both conditions. For $k=1$, choose $n=2^{2^ap^b}$, and our above logic still holds.
03.09.2021 13:40
Great! I put a sketch. Here's another construction of $n=2^{q_1q_2...q_m}.k$, where $q_i$ are big enough primes (say bigger than prime $p$) and $m$ is also big enough. To bound $\omega(n+k)$, just note that $3$ divides $(n+k)/k$, and $(2^{q_i} +1)/3$ are coprime divisors of $(n+k)/k$. To bound $\Omega(n+k)$, just note that again its $v_3$ is $1$ and that all divisors of $(n+k)/(3k)$ are bigger than $p$ (otherwise use FLT and orders to prove its impossible; ofc have in mind that $q_i>p$, and $q$, a prime divisor of $(n+k)/3k$, is smaller than $p$).
18.03.2022 19:58
Solution. The answer is yes. We use wishful thinking. Notice $\Omega(2^n)=n$ while $\omega(2^n)=1$. Therefore, we consider $n=2^M$ First, the second condition. If $\nu_p(2^M+k)$ where $p<2^{2/(\beta)}=C$ is bounded then $\Omega(2^M+k)<\log_{2^{2/ \beta}} (2^M+k)+O(1)=\frac{\beta}{2} \log_2(2^M+k)+O(1)< \beta \log_2(2^M)=\beta \Omega(2^M)$ (1) Now the first condition: since $\omega(2^M)=1$ we just need $n+k$ divisible by $\alpha$ primes. Claim: If $c,q,k>0$ is fixed then $cq^M+k$ is divisible by infinitely many primes as $M$ varies. Proof: Assume for contradiction that $cq^M+k$ is only divisible by primes $p_1,\cdots,p_t$. Consider $cq^M+k, cq^{M+1}+k, \cdots, cq^{M+t}+k$. Let $f(x)=\max_{1\le j\le t} p_j^{\nu_{p_j}(x)}$. Then note $f(cq^{M+l}+k)\ge (cq^{M+l}+k)^{\frac 1t}$. Two of these have $f(x)$ the prime of the same power. Say $p^u$ divides $cq^{M+a}+k$ and $cq^{M+b}+k$ and $p^u>(cq^{M+a}+k)^{\frac 1t}$. However, $p^u\mid cq^{M+b}-cq^{M+a}=q^{M+a}c(q^b-1)$ so $p^u<c(q^{b-a}-1)$. Setting $M$ large enough gives a contradiction since $b<t$ is bounded. Now we construct. Step 1: Find $M$ such that $\omega(n+k)\ge C$ where $C=\lceil \alpha+1 \rceil$. Set $c=1,q=2$. By our claim, there exists a very large prime $p>2^{2/\beta}$ such that $p\mid cq^{t_0}+k$. This means for all $t\equiv t_0 (\bmod\; p-1)$, $p\mid cq^{t_0}+k$. Thus, we are considering numbers of the form $cq^{t_0+(p-1)M}+k$. We replace $c$ with $c\cdot q^{t_0}$ and $q$ with $q^{p-1}$ and perform the procedure again until we have performed it $C$ times. This means for fixed $r,N$, and all integers $l$, $\omega(2^{r+Nl}+k)\ge C$ Step 2: We need to construct arbitrarily large $l$ such that $\nu_p(2^{r+Nl}+k)$ is bounded for $p<2^{1/ \beta}$. This is not hard. We know $\nu_p(2^r+k)$ is bounded. This means that if $\varphi(p^{\nu_p(2^r+k)+1})$ divides $l$ then $2^{r+Nl}+k \equiv 2^r+k (\bmod\; p^{\nu_p(2^r+k)+1})$ so $\nu_p(2^{r+Nl}+k)=\nu_p(2^r+k)$. The conclusion follows from (1).