Some Tips to improve Efficiency in Python
if n % 2
can change to
if n & 1
if n //= 2
can change to
if n >> 1
one line to do if condition
[on_true] if [expression] else [on_false]
delete all the punctuation:
for c in string.punctuation:
s = s.replace(c,'')