Вам нужно умножить некоторое большое число X ** 27. У вас есть калькулятор, но **...

Question

Вам нужно умножить некоторое большое число X на 27. У вас есть калькулятор, но на
калькуляторе сломались все кнопки операций, кроме сложения. Поэтому вы можете только
складывать разные числа (например, можно сложить число X и число X, тогда получится 2X,
затем можно сложить число 2X и 2X и получится 4X, а можно сложить 2X и X и получится
3X, то есть можно складывать любые ранее полученные числа между собой). Определите,
при помощи какого минимального числа сложений можно получить число 27X. Приведите
последовательность операций, при помощи которых можно получить число 27X за указанное
число сложений.

Answer 1

Программа на питоне, перебирающая варианты и возвращающая все ответы минимальной длины:
def number_of_adds(n):
  def next_seq(seq):
    new_elems = set()
    for i in range(len(seq)):
      for j in range(i, len(seq)):
        new_elem = seq[i] + seq[j]
        if new_elem > seq[-1] and new_elem not in new_elems:
          new_elems.add(new_elem)
          yield seq + [new_elem]
  
  current_stage = None
  next_stage = [[1]]
  answer = []
  while len(answer) == 0:
    current_stage = next_stage
    next_stage = []
    for chain in current_stage:
      next_stage.extend(next_seq(chain))
    answer = [seq[1:] for seq in next_stage if seq[-1] == n]
  return answer
    
def print_solution(n):
  answer = number_of_adds(n)
  print("Для {} есть {} решений(-я, -е):".format(n, len(answer)))
  for i in range(len(answer)):
    print("{}. {}".format(i + 1, " ".join(map(str, answer[i]))))
  print()


print_solution(27)

Запустив, находим, что необходимо 6 сложений. За 6 сложений можно получить 27X, например, так:
X + X = 2X
2X + X = 3X
3X + 3X = 6X
6X + 6X = 12X
12X + 12X = 24X
24X + 3X = 27X