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.
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))