Where I live, mobile phone numbers tend to be combinations of 9 digits, mainly starting by 6, and I've been days wonder whether is it possible to express a given number as sums/products involving less digits than the original, and if is it possible to conceive a reasonable algorithm to find a solution.
My first thought was to factorize it, but prime factors usually involve some relatively big prime number.
I've managed to find nice examples testing some combinations. For instance, let's say my phone number is 671088640. This number can be obtained as 5*8^9, that is, you only need to remember 3 digits (and 2 operators).
How would you approach this problem away from brute force?
Thank you.
I will assume the operations you allow are only +/-, × and ^. My reasoning for that is, that there is noting inherently special about the operations that "have a name" and if I would allow ANY operation, then for the phone number T I could just take the operation a#b = abT or even a#b = T for any a,b.
From those 3 operations only ^ saves on digits: + increases the number of digits required and * leaves it the same. This means, that our goal will be to find a way to incorporate a^b for b as big as possible into our equation.
As pointed out before, it will rarely be the case, that T is divisible by a high power of a number. However, when combining this with +/- there is hope for one of the numbers T, T+1, T-1, T+2, T-2 etc to be divisible by a high power of a number. Unfortunately, this will still not help for most numbers.
When you look at the information theoretical side of it, you will see, why there can be no fool-proof algorith for this:
Using 9 decimal points, I can represent 10^9 different numbers. Using sequences of 0,1,2,3,4,5,6,7,8,9,+,-,^,× of lenght at most 7 we can represent less than (as some sequnces represent the same number) 14^7 < 10^9 different numbers. This means, that you cannot hope for a general algorithm to significantly (or probably at all) cut down on the number of digits you have to remember. (And now you also have to remember signs)
For a specific number T your best bet is to hope that one of T-99, ..., T+99 is a multiple of a high prime power, or that you can find small a, b, k, l such that T = a×8^k + b×9^k or, if that fails try 7^k, ...