Suppose that $\alpha$ is a real number and $a_1<a_2<.....$ is a strictly increasing sequence of natural numbers such that for each natural number $n$ we have $a_n\le n^{\alpha}$. We call the prime number $q$ golden if there exists a natural number $m$ such that $q|a_m$. Suppose that $q_1<q_2<q_3<.....$ are all the golden prime numbers of the sequence $\{a_n\}$. a) Prove that if $\alpha=1.5$, then $q_n\le 1390^n$. Can you find a better bound for $q_n$? b) Prove that if $\alpha=2.4$, then $q_n\le 1390^{2n}$. Can you find a better bound for $q_n$? part a proposed by mahyar sefidgaran by an idea of this question that the $n$th prime number is less than $2^{2n-2}$ part b proposed by mostafa einollah zade
Problem
Source: Iran 3rd round 2011-final exam-p5
Tags: number theory, prime numbers
anonymouslonely
18.09.2011 20:59
can somebody post a solution? maybe the official one....
goodar2006
18.09.2011 21:02
I know that a good bound for part a is $q_n\le 28^n$. if nobody post a solution within a week, then I'll post mine.
dombeldor
04.10.2011 22:08
for part a you can write any number in the form a^2.b and for part b you can write any number in the form (c^2.d)^2.b and use erdush theoream .
amirreza_math
03.08.2012 18:20
I think for part b we can write each number in form a.b^3 then we reach to bound 729^n
da-rong_wae
28.06.2019 18:09
can someone post a full solution?
Superguy
27.06.2020 23:56
Here is my solution with latex help from ayan.nmath We are going to prove bound $q_n\leq 35^n$ for part (a). Let's assume for the sake of contradiction that there exists $n$ such that $q_n>35^n$, here suppose $n$ is minimal.Then suppose $r$ is the minimal index such that $q_n|a_r$ then $r>35^{{\frac{2}{3}}n} (\clubsuit).$ So all of $\{a_1,a_2,\cdots a_{r-1}\}$ have prime factors in set $\{q_1,q_2,\cdots q_{n-1}\}.$ Call this set of primes as $P.$ We clearly have $$\sum_{k=1}^{r-1} \frac{1}{a_{k}^{\frac{1}{3}}}\geq \sum_{k=1}^{r-1} \frac{1}{\sqrt{k}}\ \cdots ( 1)$$Clearly R.H.S in $(1)$ is greater than $2\sqrt{r}-2$ which can be shown using easy integration. Consider the following claim:
Claim.
$$\sum_{k=1}^{r-1} \frac{1}{a_{k}^{\frac{1}{3}}}\leq \prod_{p\in P}\Bigl[\sum_{m\ge 0}p^{-\frac{1}{3} m}\Bigr] \leq 5(3.27)^{n-2}$$where $|P|=n-1$.
Proof.
Note that all of $a_k$ are of the form $q_{1}^{k_1}\cdot q_{2}^{k_2}\cdots q_{n-1}^{k_{n-1}}$ where all $k_i$ are nonegative which gives the left side inequality. For right side we have that the sum$ \Bigl[\sum_{m\ge 0}p^{-\frac{1}{3} m}\Bigr]$ is maximum for $p=2$ and next greatest value is achieved by $p=3$ and the value of the sum for $p=2$ is less than $5$ and for $p=3$ the sum would be less than $3.27$
Now observe
$$\prod_{p\in P}\Bigl[\sum_{m\ge 0}p^{-\frac{1}{3} m}\Bigr] \leq 5(3.27)^{n-2}$$So we get the claim.$~\blacksquare$
$$\ln(2\cdot 35^{\frac{n}{3}})<\ln(2\cdot 35^{\frac{n}{3}}-2)+1$$for all natural $n$
, we get that we should have $$\ln(2)-1+\frac{n\cdot \ln(35)}{3}-\ln(5)-(n-2)(\ln(3.27))<0\ \cdots(2)$$Now we are going to prove the opposite inequality. Taking the function in $L.H.S$ as $f(n)$ we get that $f(n)$ is increasing.Hence we just need to check for $n=1$ which we get that $f(1)>0.$ Thus we have proved the opposite inequality and thus the contradiction for our initial assumption. For part b exact similar process can give a nice bound of some $q_n<300^n.~~\blacksquare$ Remark. Also note that i agree that this might not be the best solution but if one becomes more rigorous tighter bounds can be proven in this way.
ihategeo_1969
13.11.2024 06:32
I will only do first part, since second is isomorphic. We will prove that $q_n \leq 420^n$. Say $k$ be the minimal number for which $q_k>420^k$ and say $q_k \mid a_\ell$ such that $\ell$ is minimal. First of all this obviously means that \[420^k < q_k \leq a_\ell \leq \ell^{1.5} \left(\heartsuit \right)\]Now see that \[\sum_{n=1}^{\ell-1} \frac{1}{a_n^{\frac 13}} \geq \sum_{n=1}^{\ell-1} \frac1{n^\frac 12} \geq \int_1^\ell x^{-\frac 12} \; dx=2 \sqrt{\ell}-2 \left(\clubsuit \right)\]And since we have that \[\text{rad}(a_1 \dots a_{\ell-1}) \mid q_1\dots q_k\]Now we get that because of this \begin{align*} \sum_{n=1}^{\ell-1} \frac1{a_n^{\frac 13}} \leq \prod_{n=1}^{k-1} \left(1+\frac1{q_n^{\frac 13}}+\frac1{q_n^{\frac 23}}+\dots \right)=\prod_{n=1}^{k-1} \left(\frac{q_n^\frac13}{q_n^\frac13-1} \right) \leq \left(\frac{2^\frac13}{2^\frac13-1} \right)^{k-1} \leq 4.85^{k-1} \left(\spadesuit \right) \end{align*}Combining $\heartsuit$, $\clubsuit$ and $\spadesuit$ we get that \[\frac{1.5 \log \ell}{\log 420} \geq \frac{\log (2 \sqrt{\ell}-2)}{\log 4.85}+1 \implies \ell \in (1,2)\]And we get a contradiction.