Реализация алгоритма из моего комментария чуть выше, алгоритм последовательно перебирает все числа до нужного, ища оптимальное представление записи.
Алгоритм рассматривает варианты
i+j
i*j
i+j+1
i*j+1
Не буду браться за математическое доказательство, но скорее всего другие представления не дадут оптимизации длины записи. Хотя не буду это утверждать.
def getArray(maxN):
res={} # [ключ]=сумма единиц, строка представления
res[1]=[1, "1"] #стартовые значения
res[2]=[2, "1+1"]
for current in xrange(3, maxN): #текущее обрабытываемое число
minims=[current+1, 0, 0, 0] #[минимальное значение, i, j, метод]
for i in xrange(1, current):
for j in xrange(1, current):
values=[ # варианты представлений записи
i+j,
i*j,
i+j+1,
i*j+1,
]
for k in range(4):
# если число можно выразить через i и j, и сумма единиц меньше, чем ранее найденные
if values[k]==current and res[i][0]+res[j][0]+int(k>1)<minims[0]:
minims=[res[i][0]+res[j][0]+int(k>1), i, j, k]
res[current]=[minims[0], getSummaryString(res[minims[1]], res[minims[2]], minims[3])]
return res
# создает строку представления числа
def getSummaryString(val1, val2, method):
if method%2==0:
res= val1[1]+"+"+val2[1]
else:
res= "("+val1[1]+")("+val2[1]+")"
if method>1:
res+="+1"
return res
arr=getArray(40)
print arr
Результат
{1: [1, '1'], 2: [2, '1+1'], 3: [3, '1+1+1'], 4: [4, '1+1+1+1'], 5: [5, '1+1+1+1+1'], 6: [5, '(1+1)(1+1+1)'], 7: [6, '1+(1+1)(1+1+1)'], 8: [6, '(1+1)(1+1+1+1)'], 9: [6, '(1+1+1)(1+1+1)'], 10: [7, '1+(1+1+1)(1+1+1)'], 11: [8, '1+(1+1+1)(1+1+1)+1'], 12: [7, '(1+1)((1+1)(1+1+1))'], 13: [8, '1+(1+1)((1+1)(1+1+1))'], 14: [8, '(1+1)(1+(1+1)(1+1+1))'], 15: [8, '(1+1+1)(1+1+1+1+1)'], 16: [8, '(1+1)((1+1)(1+1+1+1))'], 17: [9, '1+(1+1)((1+1)(1+1+1+1))'], 18: [8, '(1+1)((1+1+1)(1+1+1))'], 19: [9, '1+(1+1)((1+1+1)(1+1+1))'], 20: [9, '(1+1)(1+(1+1+1)(1+1+1))'], 21: [9, '(1+1+1)(1+(1+1)(1+1+1))'], 22: [10, '1+(1+1+1)(1+(1+1)(1+1+1))'], 23: [11, '1+(1+1+1)(1+(1+1)(1+1+1))+1'], 24: [9, '(1+1)((1+1)((1+1)(1+1+1)))'], 25: [10, '1+(1+1)((1+1)((1+1)(1+1+1)))'], 26: [10, '(1+1)(1+(1+1)((1+1)(1+1+1)))'], 27: [9, '(1+1+1)((1+1+1)(1+1+1))'], 28: [10, '1+(1+1+1)((1+1+1)(1+1+1))'], 29: [11, '1+(1+1+1)((1+1+1)(1+1+1))+1'], 30: [10, '(1+1)((1+1+1)(1+1+1+1+1))'], 31: [11, '1+(1+1)((1+1+1)(1+1+1+1+1))'], 32: [10, '(1+1)((1+1)((1+1)(1+1+1+1)))'], 33: [11, '1+(1+1)((1+1)((1+1)(1+1+1+1)))'], 34: [11, '(1+1)(1+(1+1)((1+1)(1+1+1+1)))'], 35: [11, '(1+1+1+1+1)(1+(1+1)(1+1+1))'], 36: [10, '(1+1)((1+1)((1+1+1)(1+1+1)))'], 37: [11, '1+(1+1)((1+1)((1+1+1)(1+1+1)))'], 38: [11, '(1+1)(1+(1+1)((1+1+1)(1+1+1)))'], 39: [11, '(1+1+1)(1+(1+1)((1+1)(1+1+1)))']}
Путей к повышению производительности этого кода- десятки, я не стал этого делать, так как это лишь демонстрация.