Iranian Mathematical Olympiad

a) Denote by $t$ the number of golden prime numbers less than or equal to $1390^n$. We want to show that $t\ge n$. Suppose that $S$ is collection of all natural numbers less than or equal to $1390^n$ with prime factors from the set $\{q_1,q_2,\dots ,q_t\}$. Obviously each element of $S$ can be written in the form $a^{2}b$ where $a,b\in \mathbb{N}$ and $b$ is out of square. So $a\le \sqrt{1390^n}=1390^{\frac{n}{2}}$ and $b=q_1^{{\alpha }_1}{q}_2^{{\alpha }_2}\dots q_t^{{\alpha }_t}$ such that ${\alpha }_i\in \{0,1\}$. Therefore $a$ and $b$ have $1390^{\frac{n}{2}}$ and $2^t$ states respectively, and so $|S|\le 2^t\times 1390^{\frac{n}{2}}$.

On the other hand for each integer $1\le i\le k=1390^{\frac{2}{n}}$ we have $$a_i\le i^{1.5}\le k^{1.5}=1390^{\frac{2}{n}\times 1.5}=1390^n.$$ And all prime divisors of $a_i$ are in the set $\{q_1,q_2,\dots ,q_t\}$, so $a_i\in S$ ($1\le i\le 1390^{\frac{2}{n}}$). Therefore $S$ has at least $|k|$ elements. So $1390^{\frac{2}{n}}-1<|k|\le |S|\le 2^t\times 1390^{\frac{n}{2}}$, But it is easy to check that $2\times 1390^{\frac{1}{2}}\le 1390^{\frac{2}{n}}-1$ and this implies $t\ge n$, because $2^n\times 1390^{\frac{1}{2}}=(2\times 1390^2{)}^n\le (1390^3-1{)}^n\le 1390^{\frac{2}{n}}-1<2^t\times 1390^2$. $\square$

b) The proof of this part is very similar to part a. Denote by $t$ the number of golden prime numbers less than or equal to $1390^{2n}$. We want to show that $t\ge n$. Suppose that $S$ is collection of all natural numbers less than or equal to $1390^{2n}$ with prime factors from the set $\{q_1,q_2,\dots ,q_t\}$. Then every element of $S$ can be written in the form $a^4{b}^{2}c$ where $a,b,c\in \mathbb{N}$ and $b,c$ are out of square. (In part a writing $a$ as $x^{2}y$ where $x,y\in \mathbb{N}$ and $y$ is out of square implies this claim.) Now $a\le \sqrt[4]{1390^{2n}}=1390^{\frac{n}{4}}$, $b=q_1^{{\alpha }_1}{q}_2^{{\alpha }_2}\dots q_t^{{\alpha }_t}$ and $c=q_1^{{\beta }_1}{q}_2^{{\beta }_2}\dots q_t^{{\beta }_t}$ such that ${\alpha }_i,{\beta }_i\in \{0,1\}$. Thus we have $1390^{\frac{n}{2}},2^t$ and $2^t$ states for $a,b$ and $c$ respectively and so $|S|\le 2^{2t}\times 1390^{\frac{n}{2}}$.

In this case if $1\le i\le k=1390^6$ ($i\in \mathbb{N}$) then $a_i\le i^{2.4}\le k^{2.4}=1390^6$ ($i\times 2.4\le k\le i^{2.4}$). Although prime divisors of $a_i$ ($1\le i\le k$) are in the set $\{q_1,q_2,\dots ,q_t\}$ so $a_i\in S$, hence $1390^{\frac{5}{n}}-1<k\le |S|\le 2^{2t}\times 1390^{\frac{n}{2}}$. On the other hand $4\times 1390^2\le 1390^6-1$ and so $$2^{2n}\times 1390^2=(4\times 1390^2{)}^n\le (1390^6-1{)}^n\le 1390^6-1<2^{2t}\times 1390^2,$$ which implies $t\ge n$. $\square$