# Prove that a sequence is a permutation of the natural numbers

Consider the following sequence (A050000 in the OEIS): $$k(n)=\left\{\begin{array}{ll} \lfloor{0.5\cdot k(n-1)}\rfloor, & \lfloor{0.5\cdot k(n-1)}\rfloor\notin \{0, k(1), k(2), \dots, k(n-1)\} \\ 3\cdot k(n-1) & otherwise\end{array}\right.$$ with $k(1)=1$. Does it ever repeat, i.e. are there two distinct natural numbers $i, j$ such that $k(i)=k(j)$? And does the sequence contain every positive natural number?

As for the first part, I already tried assuming there were two such natural numbers and then picked the pair $(i, j)$ with the smallest $j$ and tried to reduce this to a contradiction, e.g. there is a pair $(i', j')$ with $k(i')=k(j')$ with $j'<j$. This works fine except for the case that $k(i)= \lfloor{0.5\cdot k(i-1)}\rfloor$ and $k(j)=3\cdot k(j-1)$. That's where I'm stuck at the moment.

Can anyone give a $\textbf{hint}$?

EDIT: Concerning the second question: If $K$ is the set of all the elements of the sequence and we suppose that there is some natural number $M$ with $M \notin K$, then let $m$ be the smallest such $M$. It follows that $2m$ and $2m+1$ cannot be in $K$, otherwise they would generate $m$ as the next element. Likewise, $4m, 4m+1, 4m+2, 4m+3 \notin K$ and $8m, 8m+1, 8m+2, ..., 8m+7 \notin K$. In general $2^lm, 2^lm+1, 2^lm+2, ..., 2^lm+(2^l-1) \notin K$ for every nonnegative integer $l$. Hence, there are arbitrarily long "gaps" in $K$ if there was one natural number that is not in $K$. Does this help to answer the second question? Does it maybe help if we suppose that we have already proved that the sequence does never repeat (first question)?

• Did you try reading this pdf, linked from the OEIS entry? prac.im.pwr.edu.pl/~kwasnicki/stuff/MDproblem.en.pdf May 13 '17 at 20:10
• When reading the OEIS entry, I did see that pdf, too, but what I am actually looking for is some kind of more elementary proof. One might be able to achieve this if one only considers this specific sequence instead of a whole family of sequences like in the pdf you linked. May 13 '17 at 20:13
• That is often not the case, but one can always hope. Cheers! May 13 '17 at 20:24
• Um... this is one of the great unsolved problems. You can look for some kind of more elementary proof but that doesn't mean you'll find one. So can anyone give you a hint? No, I believe the answer is quite literally that, no, there is not a single person on these boards, that will be capable, whether they want to or not, of giving you a hint. I know I certainly can not. May 13 '17 at 20:26
• On the other hand, this problem is from a maths journal for $\textit{school pupils}$ so there must be some kind of elementary proof. May 13 '17 at 20:30