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.

  • $\begingroup$ 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? $\endgroup$
    – greybeard
    Dec 6 '20 at 7:57

Your sequence contains all positive integers not divisible by 3. Let us prove this by induction.

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}<x$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.