Trouble finding the smallest number of 1's required to represent an integer

Question

I'm doing some programming challenges for fun and I've gotten really stuck on one particular problem regarding how to represent integers using only ones. The question is what is the least number of ones needed to express an integer smaller than 100000 using the operations +, x and © where © is the concatenation operation (12 © 34 = 1234). This value is referred to as the complexity C(n) in the problem definition. My solution uses a memo array where I keep the complexity of each number that I've already processed. For each new integer I get the complexity by taking the smallest complexity from all factorizations, all concatenations and the integer minus 1. Eg for 77 I assign the complexity to be min( C(7) + C(11), C(7) + C(7), C(76) + C(1) ). My reasoning for this is that since the concatenations, factorizations and subtractions all result in smaller integers I should always have the smallest complexity of these parts memoized.

This solution gets correct answers for integers such as 10101 and 99999 but it gets stuck on 99984 for some reason. The solution I've found is:

( (1©1©1) x (1+1+1) x (1+1+1) ) © ( ((1+1) © 1) x (1+1+1+1) ) = 99984

The complexity here becomes C(99984) = 16 which apparently is wrong. I've stared myself blind on this problem and would really appreciate some pointers on where I've gone wrong. Below follows my Python 3 code:

def find_complexity(input_number):
    complexity_array = [0]*(input_number+1)
    complexity_array[1] = 1
    largest_divisor = 2

    for number in range(2, input_number+1):
        smallest_complexity = number
        
        #Loop through all concatenation splits
        str_number = str(number)
        for i in range(len(str_number)-1):
            tail = str_number[i+1:]
            if tail[0] == '0':
                continue
            head = str_number[:i+1]
            complexity_sum = complexity_array[int(head)] + complexity_array[int(tail)]
            if smallest_complexity > complexity_sum:
                smallest_complexity = complexity_sum
                
        #Loop through all factorizations
        if number == largest_divisor**2:
            largest_divisor += 1
        for divisor in range(2, largest_divisor):
            if number % divisor != 0: 
                continue
            dividend = number // divisor
            complexity_sum = complexity_array[dividend] + complexity_array[divisor]
            if smallest_complexity > complexity_sum:
                smallest_complexity = complexity_sum
                
        #Loop through all summations
        complexity_sum = complexity_array[number-1] + 1
        if smallest_complexity > complexity_sum:
            smallest_complexity = complexity_sum
        
        complexity_array[number] = smallest_complexity
    
    return complexity_array[input_number]

input_number = 99984
output = find_complexity(input_number)
print(output)

Answer 1

You forgot some possible operations. For any integer n, you can reach it by summing k and n-k, for any 1 <= k <= n-1.

For instance, consider 53. It can be written (1 © 1) + ((1 + 1) x ((1 + 1) © 1)), so C(53) = 7. Your code returns 8.

Note that 53 is the first integer for which your code is wrong.

I think you don't have any implementing issue, so I let you code this.