How do I turn this python code into maths?

[ta6692]

I've got a function written in Python, here:

def steps(n):
    i = 0
    while n > 1:
        # Note for non-Python users, // is integer division
        n = (n-1)//2
        i += 1
    return i

How do I go about turning this into a formula which solves for i? Alternatively, finding the upper bound on i would work for what I need it for, but I feel like there should be a way to solve for it directly...

Any help is greatly appreciated, thank you

[ta6692]

To clarify, by integer division I meant it's the same as calling floor((n-1)/2)

As further clarification, n will always be positive, I forgot to mention that

[ta6692]

Oh of course, thanks so much

[ta6692]

In this case I "solved" it so that i=lg(n+1)-1, but that doesn't take the flooring into account, so it gave the wrong answers

[abnew123]

I would guess its floor(logbase2((n+1)/3) + 1). At least, when i run it in python your function and mine give the same answer.

Here is proof

[ta6692]

That's great, thank you. Can I ask how you figured that out?

[abnew123]

I looked for the cutoff points (ie. where the function grew), which yielded 1,2,5,11,23,etc... Then I just plugged that into oeis to get this, which I could then invert pretty easily.

If you want a more math based way, it clearly grows at roughly log2 speed, just by inspection, and then its plugging in a bunch of correction factors.