Any useful mathematical function / algorithm to break down big numbers?

Question

So what I want to do is breaking down numbers that are dozens of thousands big into smaller numbers, preferably 2~9.

The first thing came to my mind was prime factorization, for instance the number 49392 can be expressed as (2 x 2 x 2 x 2 x 3 x 3 x 7 x 7 x 7). But there are prime numbers and numbers such as 25378 = 2 × 12689 that cant be expressed with only multiplication.

So I want to break these numbers down using multiplication and addition, for example, the number 25378 could be expressed as 25346 + 32 = (2 × 19 × 23 × 29) + (2^5). Still, 23 and 29 are too big but I just picked random number just to show what I mean by using addtion and multiplication together to express big numbers, I'm sure there's a better combination of number that express 25378 than 25346 and 32.

Anyways, I thought programming this would involve ton of unnecessary if statement and would be incredibly slow in the big picture. So I was wondering, if there is a mathematical algorithm or function that does this thing? If not, I could just optimize the code myself, but I was just curious, I couldn't find anything on google myself though.

Answer 1

Assuming the problem is to write a number as the simplest expression containing the numbers 1-9, addition and multiplication (simplest = smallest number of operators), then this Python program does this in O(N^2) time.

A number N can be written as the sum or product of two smaller numbers, so if you've precalculated the simplest way of constructing the numbers 1..N-1, then you can find the simplest way of constructing N in O(N) time. Then it's just a matter of avoiding duplicate work -- for example without loss of generality in the expressions A+B and AB, A<=B, and nicely printing out the final expression.

def nice_exp(x, pri):
    if isinstance(x, int):
        return str(x)
    else:
        oppri = 1 if x[0] == '*' else 0
        if oppri < pri:
            bracks = '()'
        else:
            bracks = ['', '']       
        return '%s%s %s %s%s' % (bracks[0], nice_exp(x[1], oppri), x[0], nice_exp(x[2], oppri), bracks[1])

def solve(N):
    infinity = 1e12
    size = [infinity] * (N+1)
    expr = [None] * (N+1)
    for i in range(N+1):
        if i < 10:
            size[i] = 1
            expr[i] = i
            continue
        for j in range(2, i):
            if j * j > i: break
            if i%j == 0 and size[j] + size[i//j] + 1 < size[i]:
                size[i] = size[j] + size[i//j] + 1
                expr[i] = ('*', expr[j], expr[i//j])
        for j in range(1, i):
            if j > i-j: break
            if size[j] + size[i-j] + 1 < size[i]:
                size[i] = size[j] + size[i-j] + 1
                expr[i] = ('+', expr[j], expr[i-j])
    return nice_exp(expr[N], 0)

print(solve(25378))

Output:

2 * (5 + 4 * 7 * (5 + 7 * 8 * 8))