We can break the total sequence of operations into groups that take the form "[copy][some number of pastes]" In K operations of this group, the length of the string is multiplied by K.
Now, suppose N can be written as
N = d_1 * d_2 * ... * d_k. By the above reasoning,
N "A"s can be written on the tape in
d_1 + d_2 + ... + d_k operations. If any of the
d_i are composite, say
d_i = p*q (with
p>1, q>1), then we could write it in p + q instead of p*q operations by breaking up this divisor.
For example, if we make 15 with 15 operations, we could instead make it with 3 operations to get AAA then another 5 operations. Also, we should justify that
p+q <= p*q (because (p-1)(q-1) is positive), so we indeed do get savings by breaking up this product.
def minSteps(self, n): def factors(n): d = 2 while d * d <= n: while n % d == 0: n /= d yield d d += 1 if n > 1: yield n return sum(factors(n))