Doubling and adding 1

gistfile1.py

#	Implementation of this algorithm:
#		https://www.reddit.com/r/mathriddles/comments/2v6eaj/doubling_and_adding_1/coey1j7
#
#	Save the code as filename.py. Then run something like
#		python filename.py 8 1

import sys

def getL(k):
	L=1
	Llist = []

	# We first create a list of L's that satisfy the inequalities
	while 2**L+L-2 <= 3*k:
		L = L+1
		if 2**L + L - 2 > k and 2**L + L - 2 < 3*k:
			Llist = Llist + [[L,abs(2**L+L-2*k-2)]]

	# We could use any L for our purpose but we choose one
	# that gets us as close to our goal as possible, by taking
	# as large steps as possible. Note that there's no reason to
	# believe a priori that this actually provides a more efficient
	# solution but it seems reasonable.

	minL = Llist[0][0]
	minval = Llist[0][1]
	for l in Llist:
		if l[1] < minval:
			minL = l[0]
	return minL

def op1(a,b):
	global operations
	operations = operations + 1
	print 2*a,b+1
	return 2*a,b+1

def op2(a,b):
	global operations
	operations = operations + 1
	print a+1,2*b
	return a+1,2*b

#	When (a,b) = (x,x+1) we will use the operations that always work in this case.
def fixone(x):
	return op2(*op2(*op1(*op2(*op1(*op1(*op1(*op1(*op2(*op2(x,x+1))))))))))

#	Figuring out the minimal number of needed operations is interesting.
#	Here's a plot of how well the algorithm at hand does:
#		https://i.imgur.com/z4CssvV.png

def operationsNeeded(k):
	if k == 0:
		return 0
	if k == 1:
		return 10
	L = getL(k)
	return 2*k+2+operationsNeeded(abs(2*k+2-2**L-L))

def makeOperationsNeededData():
	f = open('data','w')
	for i in range(1000000):
		f.write(str(operationsNeeded(i))+"\n")

def main():
	a = int(sys.argv[1])
	b = int(sys.argv[2])
	print a,b
	
	global operations
	operations = 0
	
	while 1:
		if a > b:
			print "Swapped the numbers"
			c = a
			a = b
			b = c
		k = b-a

		if k == 0:
			break
		if k == 1:
			a,b = fixone(a)
			break

		for i in range(k):
			a,b = op2(a,b)
		L = getL(k)
		for i in range(k-L+1):
			a,b = op1(a,b)
		a,b = op2(a,b)
		for i in range(L):
			a,b = op1(a,b)	

	print "Number of operations:", operations

if __name__ == '__main__':
	main()