Integer sequences containing the floor / ceiling function

There was this question on one sequence where the expression for the general term contains the floor function. I can clearly see that the floor function is needed for an expression which doesn't burn ones eyes out, but I have no idea how one goes about to construct the explicit formula.

For more examples, there is the sequence A014132 $$n + \left\lfloor 1/2 + \sqrt{2n} \right\rfloor$$ which contains every integer but the triangular numbers and A000037 $$n + \left\lfloor1/2 + \sqrt{n-3/4}\right\rfloor$$ which misses exactly the square numbers.

So, let's say you are given the sequence $$4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25,\ldots$$ of non-Fibonacci numbers during an exam (i.e. you cannot use the OEIS to look it up), and you are told to construct a expression like the ones above for the $n$'th term, how does one think to get to the right answer?

Edit: As a side question, is there some quick way to see which one of the floor and ceiling functions yield the nicest expressions?

New edit: I see that the expression for non-Fibonacci numbers is quite complicated, containing base-$\phi$ logarithms. (I didn't research enough, apparently. I expected it to be on par with the two others.) I'll accept a solution for any of the other sequences, or any similar sequence not discussed here.

• Also, I have observed that the expressions for all the sequences discussed here are $\lfloor f(n) + 1/2\rfloor$ or $\lceil f(n) - 1/2\rceil$, so I guess the rounding function is actually the most accurate to use. This shouldn't change what I'm asking for, though. – Arthur Dec 10 '12 at 12:25

Bakir Farhi's paper explains much. In particular, how to generate complementary sequences for sequences of the form $n^a$ and $a^n$, and for the Fibonacci sequence.
• You're right, I didn't see the inversion of $\phi$ there. I thought theorem 1.1 was just a formulation of the usual test, and must have skimmed over it. I will sit down and try it out later today. – Arthur Dec 13 '12 at 8:24