def brute(n): n = int(n) if n <= 1: return 0 if n % 2 == 0: return 1 + brute(n / 2) return min(brute(n + 1), brute(n - 1)) + 1 def trailingZeros(n): return len(bin(n).split('1')[-1]) def answer(n): n = int(n) count = 0 while n > 3: if n % 2 == 0: n /= 2 else: n += 1 if bin(n + 1).count('0') >= bin(n - 1).count('0') else -1 count += 1 return count + n - 1 def answer2(n): n = int(n) count = 0 while n > 3: if n % 2 == 0: n /= 2 else: n += 1 if trailingZeros(n+1) > trailingZeros(n-1) else -1 count += 1 return count + n - 1 def answer3(num): num = int(num) num = [int(i) for i in "{0:b}".format(num)] count = len(num) - 1 while len(num) > 1: a = (num[-2], num.pop()) if a == (1, 1) and len(num) > 1: while num[-1] is not 0 and len(num) > 1: num.pop() count += 1 num[-1] = 1 if len(num) is 1: count += 1 elif a == (1, 1): count += 1 elif a == (0, 1): count += 1 return count def answer4(n): n = int(n) count = 0 while n > 3: if n % 2 == 0: n /= 2 else: n += 1 if n % 4 == 3 else -1 count += 1 return count + n - 1 # print trailingZeros(58) # import sys # sys.exit() print ' '.join('{:2}'.format(i) for i in range(30)) print ' '.join('{:2}'.format(answer4(str(n))) for n in range(30)) print ' '.join('{:2}'.format(answer(str(n))) for n in range(30)) for i in range(5, 10000): print i if answer2(i) != answer(i): print answer4(i), answer(i) break print answer(10**300)