Simulated Annealing for Large Digit Sum

Energy landscape for digit sum of a^b

Thought it’d be fun to try simulated annealing on the maximum digit sum for a^b for a, b ≤ K. In the above diagram K = 100, hence giving a discrete search space of 10,000 values.

Though it is quite easy to brute force search the digit sum, simulated annealing offers a more scalable solution for large K. Below is an implementation in Python:

def digit_sum(number):
	s = 0
	while number:
		s += number % 10
		number /= 10
	return s 

def compute_energy(base, exponent):
	return -(digit_sum(base ** exponent))

def simulated_annealing(start_temp, cooling_rate, max_base, max_exponent, max_iter):
	initial_base = np.random.randint(1, max_base + 1)
	initial_exponent = np.random.randint(1, max_exponent + 1)
	initial_energy = compute_energy(initial_base, initial_exponent)
	iter = 0
	while iter < max_iter:
		new_base = np.random.randint(1, max_base + 1)
		new_exponent = np.random.randint(1, max_exponent + 1)
		new_energy = compute_energy(new_base, new_exponent)
		if new_energy < initial_energy:
			initial_energy = new_energy
			start_temp *= (1 - cooling_rate)
		elif new_energy == initial_energy:
			start_temp *= (1 - cooling_rate / 5)
		elif new_energy > initial_energy:
			if np.exp((initial_energy - new_energy) / start_temp) > np.random.random():
				initial_energy = new_energy
				start_temp *= (1 - cooling_rate)
			else:
				start_temp *= (1 - cooling_rate / 5)
		iter += 1
	return -(initial_energy)