# Membership in 1, 5, 2, 13, 10, … (recursively defined sequence)

Find if a given integer is in the series $$1, 5, 2, 13, 10, \dots$$ in the most efficient way, where the sequence is given by $$f(n) = \begin{cases} 1 & n=1, \\ 2f(\tfrac{n}{2})+3 & n \text{ even}, \\ 2f(\tfrac{n-1}{2}) & n>1 \text{ odd}. \end{cases}$$

The series is infinite of course, and $$x$$ can be a number with at most 9 digits. The idea is not to hardcode this and maybe find some kind of correlation that will allow you to solve this fast. I want to say that I have an idea of how to solve it but I don't.

• Welcome to COMPUTER SCIENCE @SE. It may be for the better this sequence looks too simple for the OEIS. What if you stare at a few elements more? – greybeard Dec 6 '20 at 7:57

Suppose first that $$x$$ is divisible by 3, and $$f(n) = x$$. Considering the definition, we see that $$x = 2f(n/2) + 3$$, and so $$f(n/2) = \tfrac{x-3}{2}$$, which is also divisible by 3. By induction, this is impossible.
Suppose next that $$x>0$$ is not divisible by 3. If $$x=1$$ then $$x$$ appears in the sequence since $$f(1) = 1$$, so we can assume that $$x \geq 2$$. We now consider two cases: $$x$$ even and $$x$$ odd.
If $$x$$ is even then $$\tfrac{x}{2} is positive not divisible by 3, and so by induction, $$\tfrac{x}{2} = f(m)$$ for some $$m$$. Then $$f(2m) = x$$.
Similarly, if $$x$$ is odd then $$\tfrac{x-3}{2} < x$$ is not divisible by 3. Furthermore, since $$x \geq 5$$, it is furthermore positive. By induction, $$\tfrac{x-3}{2} = f(m)$$ for some $$m$$. Then $$f(2m+1) = x$$.