def snoob(x):
next = 0
if(x):
# right most set bit
rightOne = x & -(x)
# reset the pattern and
# set next higher bit
# left part of x will
# be here
nextHigherOneBit = x + int(rightOne)
# nextHigherOneBit is
# now part [D] of the
# above explanation.
# isolate the pattern
rightOnesPattern = x ^ int(nextHigherOneBit)
# right adjust pattern
rightOnesPattern = (int(rightOnesPattern) /
int(rightOne))
# correction factor
rightOnesPattern = int(rightOnesPattern) >> 2
# rightOnesPattern is now part
# [A] of the above explanation.
# integrate new pattern
# (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern
return next
# Driver Code
for n in range(1,30):
x=2**n-1
count=0
while(x<=10**5):
count+=1
x=snoob(x)
print(count)
ZGVmIHNub29iKHgpOiAKICAgICAgCiAgICBuZXh0ID0gMAogICAgaWYoeCk6IAogICAgICAgICAgCiAgICAgICAgIyByaWdodCBtb3N0IHNldCBiaXQgCiAgICAgICAgcmlnaHRPbmUgPSB4ICYgLSh4KSAKICAgICAgICAgIAogICAgICAgICMgcmVzZXQgdGhlIHBhdHRlcm4gYW5kICAKICAgICAgICAjIHNldCBuZXh0IGhpZ2hlciBiaXQgCiAgICAgICAgIyBsZWZ0IHBhcnQgb2YgeCB3aWxsICAKICAgICAgICAjIGJlIGhlcmUgCiAgICAgICAgbmV4dEhpZ2hlck9uZUJpdCA9IHggKyBpbnQocmlnaHRPbmUpIAogICAgICAgICAgCiAgICAgICAgIyBuZXh0SGlnaGVyT25lQml0IGlzICAKICAgICAgICAjIG5vdyBwYXJ0IFtEXSBvZiB0aGUgIAogICAgICAgICMgYWJvdmUgZXhwbGFuYXRpb24uIAogICAgICAgICMgaXNvbGF0ZSB0aGUgcGF0dGVybiAKICAgICAgICByaWdodE9uZXNQYXR0ZXJuID0geCBeIGludChuZXh0SGlnaGVyT25lQml0KSAKICAgICAgICAgIAogICAgICAgICMgcmlnaHQgYWRqdXN0IHBhdHRlcm4gCiAgICAgICAgcmlnaHRPbmVzUGF0dGVybiA9IChpbnQocmlnaHRPbmVzUGF0dGVybikgLyAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGludChyaWdodE9uZSkpIAogICAgICAgICAgCiAgICAgICAgIyBjb3JyZWN0aW9uIGZhY3RvciAKICAgICAgICByaWdodE9uZXNQYXR0ZXJuID0gaW50KHJpZ2h0T25lc1BhdHRlcm4pID4+IDIKICAgICAgICAgIAogICAgICAgICMgcmlnaHRPbmVzUGF0dGVybiBpcyBub3cgcGFydCAKICAgICAgICAjIFtBXSBvZiB0aGUgYWJvdmUgZXhwbGFuYXRpb24uIAogICAgICAgICAgCiAgICAgICAgIyBpbnRlZ3JhdGUgbmV3IHBhdHRlcm4gIAogICAgICAgICMgKEFkZCBbRF0gYW5kIFtBXSkgCiAgICAgICAgbmV4dCA9IG5leHRIaWdoZXJPbmVCaXQgfCByaWdodE9uZXNQYXR0ZXJuIAogICAgcmV0dXJuIG5leHQKICAKIyBEcml2ZXIgQ29kZSAKZm9yIG4gaW4gcmFuZ2UoMSwzMCk6Cgl4PTIqKm4tMQoJY291bnQ9MAoJd2hpbGUoeDw9MTAqKjUpOgoJCWNvdW50Kz0xCgkJeD1zbm9vYih4KQoJcHJpbnQoY291bnQp