European Mathematical Cup

Instead of sequence $a_n$, we'll use notation with the function $f(n)$ with same properties.

There exists only one such function: $f(n)=n$. We'll solve the problem with many separate facts.

Fact 1: $f(1)=1$

Proof. According to a) it holds $f(1)=f(1)f(1)=f(1{)}^2$. Since $f(1)$ is positive integer, it can't be $f(1)=0$, so it must be $f(1)=1$.

Fact 2: Function $f$ is bijective.

Proof. Firstly, we'll show that $f$ is injective. Let $a\ne b$ be two arbitrary positive integers and let's assume $f(a)=f(b)$. Since $\{1,2,...,n\}=\{f(1),f(2),...,f(n)\}$ holds for infinitely any positive integers $n$, it holds for some integer greater than $a$ and $b$. Then, since $f(a)=f(b)$, set $\{f(1),f(2),...,f(n)\}$ contains $n-1$ or less (different) elements, but according to b), it contains $n$ elements.

Secondly, we'll show that $f$ is surjective. Let $c$ be arbitrary integer and let's assume that $f(n)\ne c$ for all positive integers $n$. Similarly as in first part of proof, let's take positive integer $n$ such that $\{1,2,...,n\}=\{f(1),f(2),...,f(n)\}$ holds. Since $c\in \{1,2,...,n\}$, $c$ is also element of the set $\{f(1),f(2),...,f(n)\}$, so there exists positive integer $m\le n$ such that $f(m)=c$.

Fact 3: Positive integer $n$ is prime if and only if $f(n)$ is prime.

Proof. Let's assume that $n$ is prime, but $f(n)$ isn't. Then it must be $f(n)=a^{\prime }{b}^{\prime }=f(a)f(b)=f(ab)$, where $a^{\prime },b^{\prime }$ are positive integers greater 1, and $a,b$ are unique positive integers such that $f(a)=a^{\prime }$, $f(b)=b^{\prime }$ (they exist since $f$ is bijective). Since $f$ is injective, $f(1)=1$ and $a^{\prime },b^{\prime }$ are not equal to 1, integers $a,b$ are also not equal to 1. Since $f$ is injective and $f(n)=f(ab)$, we have $n=ab$, so $n$ is composite.

Let's assume that $f(n)$ is prime, but $n$ isn't. Then there exist positive integers $a,b$ greater than one such that $n=ab$. From there we have $f(n)=f(ab)=f(a)f(b)$. Again from injectivity of $f$ and $f(1)=1$, we see that $f(n)$ is product of two integers greater than 1.

Fact 4: If $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}...p_k^{{\alpha }_k}$ is unique factorization of positive integer $n$, then $$f(n)=f(p_1{)}^{{\alpha }_1}f(p_2{)}^{{\alpha }_2}...f(p_k{)}^{{\alpha }_k}$$ is unique factorization of positive integer $f(n)$.

Proof. From multiple use of the condition a) we get identity $f(n)=f(p_1{)}^{{\alpha }_1}f(p_2{)}^{{\alpha }_2}...f(p_k{)}^{{\alpha }_k}$. From fact 3, numbers $f(p_i)$ are prime. Since $f$ is injective, none of two numbers $f(p_i)$ and $f(p_j)$ are equal.

Fact 5: (Technical result) For all positive integers $y<x$ there exist positive integer $n_o$ such that for all positive integers $n>n_o$ holds inequality $$y^{n+1}<x^n.$$

Proof. It is sufficient to prove the fact only for consecutive integers $y$ and $y+1$ (because we'll have $y+1<(y+1{)}^n\le x^n$. By binomial theorem we have $$(y+1{)}^n\ge y^n+n{y}^{n-1}=y^{n-1}(y+n).$$ Thus if we define $n_o=y^2-y+1$, then for all $n\ge n_o$ we have $$(y+1{)}^n\ge y^{n-1}(y+n)\ge y^{n-1}(y+n_o)=y^{n-1}(y^2+1)>y^{n+1}.$$ Another proof. Inequality is equivalent to $${\left(\frac{y}{x}\right)}^n>y.$$ The fact follows from the fact that the expression on the left hand side is increasing and it is unbounded, while the right hand side is fixed.

Fact 6: For all prime numbers $p$ we have $f(p)\le p$.

Proof. Let $p_1,p_2,\dots ,p_n,\dots$ be the increasing sequence $2,3,5,7,\dots$ of all primes. Let's take arbitrary prime number $p_n$. From the Fact 3 we have that $f(p_n)$ is also prime. Let's take positive integer $n_0$ as the integer from the Fact 5, for positive integers $y=p_n<p_{n+1}=x$. Since b) holds for infinitely many positive integers, it holds for some positive integer $N$ such that $\{1,2,\dots ,N\}=\{f(1),f(2),\dots ,f(N)\}$, and such that $N\ge p_n^{n_0}$. Let $\alpha$ be the greatest positive integer such that $p_n^{\alpha }\le N$. From definitions of $N$ and $\alpha$ we have $\alpha \ge n_0$.

In set $\{1,2,\dots ,N\}$ we'll observe all positive integers which are ${\alpha }^{th}$ power of a prime number. Since $N\ge p_n^{\alpha }$, we have that $p_n^{\alpha }$ is in that set. It is easy to see that all numbers $p_1^{\alpha },p_2^{\alpha },\dots ,p_{n-1}^{\alpha }$ are also in that set. On the contrary, number $p_{n+1}^{\alpha }$ is not in that set, because from the definition of $\alpha$ and $N$ respectively we have $N<p_n^{\alpha +1}\le p_{n+1}^{\alpha }$ (remember Fact 5 and $\alpha \ge n_0$). Similarly, neither of the numbers $p_m^{\alpha }$ (for $m>n$) is not in the set $\{1,2,\dots ,N\}$.

Let us now observe all positive integers which are ${\alpha }^{th}$ power of a prime and they are in the set $\{f(1),f(2),\dots ,f(N)\}$. According to Fact 4, we have that $f(n)$ is ${\alpha }^{th}$ power of a prime. From that and from previous paragraph we conclude that only such numbers are $f(p_1^{\alpha }),f(p_2^{\alpha }),\dots ,f(p_n^{\alpha })$.

Now we have $\{p_1^{\alpha },p_2^{\alpha },\dots ,p_n^{\alpha }\}=\{f(p_1^{\alpha }),f(p_2^{\alpha }),\dots ,f(p_n^{\alpha })\}$. Thus $f(p_n^{\alpha })\in \{p_1^{\alpha },p_2^{\alpha },\dots ,p_n^{\alpha }\}$, so $f(p_n^{\alpha })=p_i^{\alpha }$ for some $1\le i\le n$, which implies $f(p_n^{\alpha })=p_i^{\alpha }$ for some $1\le i\le n\Rightarrow f(p_n)=p_i\le p_n$, which completes the proof.

Fact 7: For every positive integer we have $f(n)=n$.

Proof. From Fact 3 we have $f(p)$ if and only if $p$ is prime. Let $p_1,p_2,\dots ,p_n,\dots$ be the increasing sequence $2,3,5,7,\dots$ of all prime numbers. From fact 6 we have $f(p_1)\le p_1\Rightarrow f(2)=2$. For $n\ge 2$, inductively and from injectivity of $f$ we have $f(p_n)>p_{n-1}$ and from Fact 6 we have $f(p_n)\le p_n$, thus is must be $f(p_n)=p_n$, for all positive integer $n$.

Now for arbitrary positive integer $n$ from Fact 4 we have $$f(n)=f(p_1{)}^{{\alpha }_1}f(p_2{)}^{{\alpha }_2}\dots f(p_k{)}^{{\alpha }_k}=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}=n$$ which completes our proof.