How to determine in a fast way how many times to perform an n-1 operation for any odd number?

One of my programs does the following for odd numbers:

If the number is odd, subtract 1 from it.
If the number is even, divide it by 2.
Do until the final answer is 0.
Returns the number of the time minus 1, called subtimes. For example,the subtimes of 21 is 3. Here's a simple piece of code that shows how it works

def getsubtimes(num):
    subtimes=0
    while num!=0:
        if num%2==0:
            num/=2
        else:
            num-=1
            subtimes+=1
    return subtimes

I counted all the odd numbers between 3 and 1023, and then I did a visualization: This is my visual code

import matplotlib.pyplot as plt
subtimesAim=10
x=[i for i in range(3,2**subtimesAim+1,2)]
y=[getsubtimes(i) for i in x]
specialAim=[i for i in range(2,subtimesAim+1)]
specialNum=[2**i-1 for i in specialAim]
plt.plot(x,y,specialNum,specialAim)
plt.show()

The blue line is the subtimes required for these odd numbers. And then I also noticed that odd numbers like 2^n-1 always seem to have more subtimes, so I connected all the odd numbers like 2^n-1. The structure of the graph above looks pretty regular, but what is the pattern? Does it have to do with 2^n? If you're given an odd number, is there any way to get the subtimes of that number faster than by writing a piece of code that computes it step by step?

Solution

First of all, it is wrong to do num/=2 as (in Pyton 3) this will make num a float instead of an int, thereby limiting the precision and causing inaccurate results for big numbers. You should maintain the int data type by using num//=2 or num>>=1.

I connected all the odd numbers like 2^n-1. The structure of the graph above looks pretty regular, but what is the pattern? Does it have to do with 2^n?

The number of "subtimes" corresponds to the count of 1 bits in the binary representation of the number. In the case of numbers in the form 2^𝑛−1 this corresponds to the number of bits that are necessary to represent the number, which are all 1. For instance 2¹⁰−1 is 1111111111 in binary representation, and the corresponding number of subtimes is thus 10 (cf. the last 𝑥, 𝑦 in your graph). That 10 is the exponent given to 2 in the expression 2^𝑛−1.

The graph that you have drawn will hit the blue bars when 𝑥=2^𝑦−1, and to make 𝑦 a function of 𝑥, we can rewrite:

𝑥=2^𝑦−1
𝑥+1=2^𝑦
log_₂(𝑥+1)=𝑦

So the function that will follow the same fixation points is 𝑓(𝑥) = log_₂(𝑥+1)

If you're given an odd number, is there any way to get the subtimes of that number faster than by writing a piece of code that computes it step by step?

If with "odd" you specifically mean the forms of 2^𝑛−1 that you mentioned earlier, then you can use:

def getsubtimes(n):
    return n.bit_length()

But this will only give the desired result for numbers that are one less than a power of 2.

For the generic case (any unsigned integer), you could get the binary representation of the number as a string of "0" and "1" and count the "1"s:

def getsubtimes(n):
    return f"{n:b}".count('1')

or, similar:

def getsubtimes(n):
    return bin(n).count('1')

And since Python 3.10 you can use bit_count:

def getsubtimes(n):
    return n.bit_count()

As //2 does not have a constant time complexity, your (corrected) code has a time complexity of log²𝑛, while this solution has a time complexity of log𝑛.

The difference is significant but the difference in actual running time for practical inputs will be more due to the fact that this solution doesn't have a loop executing in Python code, but has all the looping happening in compiled code, making it run faster.

Of course, when you use one of the above one-liner functions, you don't really need the getsubtimes function wrapper, and could use the function used as implementation directly (i.e. bit_count if you have Python 3.10+). This will save you some more running time.