What's up, Subhasish! (I'm actually the friend Subhasish mentioned to @AmirSagiv)
I got a solution that starts working from the seventh term. However, it uses a different function for odds and evens.
The first couple terms which didn't follow the solution were: $1, 2, 4, 5, 9, 13$.
Afterwords odd-indices could be solved with $f(n) = 2^{\frac{n+1}{2}} + \frac{2^{n-3} - 1}{3} + 2^{n-4} - 4$
and even-indices with $f(n) = 2^{\frac{n}{2}} + \frac{2^{n-2} - 1}{3} + 2^{n-5} - 4$
I believe that there is a way that the two cases can be consolidated into one using modulos or the floor/ceiling functions. So, I may try to do that later.
The first couple terms of the sequence I found with my solution were: $1, 2, 4, 5, 9, 13, 25, 41, 81, 145$.
My solution was a little long, and to be honest, writing math out takes me forever. So I will talk in person with Subhasish (after he wakes up) and some other friends. If we can confirm or disprove my idea then we will edit what I wrote so far.
If anybody online can help to check my work that would be much appreciated as well!