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^2b$ 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^4b^2c$ where $a, b, c \in \mathbb{N}$ and $b, c$ are out of square. (In part a writing $a$ as $x^2y$ 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$