Uniqueness of an increasing sequence I have an increasing sequence $(a_i)_{i=1}^{\infty}$$(a_i\in\mathbb{N})$ , satisfying the conditions
1) If  $a_n$ is a prime number, then $n$ is prime number.
2) For all $n$, $a_{2n}=a_n+n$.
Is $a_n=n$ the only possible sequence?
I haved proved that it is true for strictly increasing sequence. I suppose there is another solution if $(a_i)_i$ is only an increasing sequence, but I fail to construct one. If I assign $a_n$ with a value, I have to be sure that $a_n+n$ is not a prime. 
 A: The answer is, perhaps surprisingly, negative if strictly increasing is replaced by only nondecreasing: first of all, let $k_0$ be the smallest known  Sierpiński number, that is, $k_0 = 78557.$ Let $A = \{2^l k_0, l \ge 0\}.$ Define then the sequence $\{a_i\}_{i \ge 1}$ by the following:

*

*If $k \not \in A,$ then $a_k = k;$


*If $k \in A,$ we let $a_k = k+1.$
Let us check that it satisfies all properties:
$\{a_i\}$ is nondecreasing: indeed, if $k,l \not \in A,k<l,$ the conclusion $a_k \le a_l$ follows trivially. If both $k,l \in A,$ it follows trivially as well from the way we defined the sequence. Moreover, if $k \in A, l \not \in A,$ then $a_k = k+1 = a_{k+1} \le a_l.$ Also, if $k \not \in A, l \in A,$ we have $a_k = k < l+1 = a_l.$
$a_i$ prime implies $i$ prime: indeed, if $i \not \in A,$ the conclusion is again obvious. If, on the other hand, $i \in A,$ then the definition of a Sierpiński number itself, then $a_i$ is never prime (as it is of the form $2^n k_0 + 1, n \ge 1.$)
$a_{2n} = a_n + n:$ notice that, by the way we defined $A,$ if $2n \in A,$ then $n \in A,$ and vice-versa. If $n \not \in A,$ the property is once more trivial. If $n \in A,$ then $a_n = n+1, a_{2n} = 2n+1 = (n+1) + n = a_n + n,$ as desired.
As a final comment, notice that it is known that there are infinitely many Sierpiński numbers, and doing such a construction with each of them yields a different solution. Also quite related and, in some sense, analogous is the concept of a Riesel number, which also yields solutions of this problem.
