# Five digit re-write game

In the habit of factoring numbers, a notebook I bought had a five digit item number $77076$, which factors as $2^2 3^2 2141$, which may also be $9 \cdot 8564$, and in this form the count of digits is again five. (Repeated digits count separately). [Note I thank Calvin Lin for pointing out I initially had the wrong product for $77076$.]

So I wondered how often this can work for five digit numbers, and started at $10001=73 \cdot 167$, $10002=2 \cdot 3 \cdot 1667=6\cdot 1667,$ and so on. The rules I decided to stick to were only that the five digit number has to be re-written as a product of two or more factors, where the total number (with repetitions) of digits occurring in the factors is again five.

Of course one runs into problems if the five digit number is itself a prime, for example at $10007$ and $10009$. There may be other general restrictions, statable in terms of the form of the prime factorization of the given five digit number; if so I'd be interested in that.

Sometimes the initial factorization into primes has to be juggled with. For example $10010=2 \cdot 5 \cdot 7 \cdot 11 \cdot 13$, which as it stands is two digits over the goal of five. We can lower the digit count by $1$ if we can for example multiply a one digit by a two digit prime in the factorization, and get only a two digit result. For this case we can use $2 \cdot 11=22,\ 5 \cdot 7=35,$ to get $$10010=7 \cdot 22 \cdot 65,$$ so the five digit requirement is met. In this same example we could instead use $2 \cdot 13=26,\ 5 \cdot 11=55$ and get another re-write: $$10010=7 \cdot 26 \cdot 55.$$

I know this is not serious math, hence the recreational tag; maybe someone might find it amusing to look at these rewrites.

Just to make a few specific questions: Is there a nice characterization, say in terms of the numbers of digits in the primes occurring in the factorization of $n$, which would say which composite $n$ with five digits did not have five digit rewrites as above? What happens in case we increase the number of digits to say 6 or 7?

-
Erm... $6\cdot 6 \cdot 2141$ has 6 digits... – Zen May 23 '13 at 0:56
You'd want $77076 = 9 \times 8564$ for the initial sentence. – Calvin Lin May 23 '13 at 1:01
@CalvinLin Thanks to both you and Zen. I got sloppy and went on to the 10001,etc. cases more carefully. I'll adjust (with attribution). – coffeemath May 23 '13 at 1:07

Since $(10^k-1)^2=10^{2k}-2\cdot10^k+1\lt10^{2k}$ (e.g. $9\cdot9\lt100$), the number of digits in a factorization cannot decrease by further subdivision of the factors. Thus a number $n$ with $k$ digits has a non-trivial factorization with $k$ digits if and only if it has such a factorization with two factors. For a factorization of $n$ with two factors to have $k$ digits, it is necessary and sufficient that one of the factors has a higher mantissa than $n$.

Thus $n$ has a factorization with $k$ digits if and only if it has a divisor with a higher mantissa than its own. That explains why you found no counterexamples other than primes when you started with the lowest mantissas. At the other end of the spectrum, there are no factorizations with $5$ digits of any $5$-digit number greater than $99\cdot999=98901$.

-
For the $10010$ example, your answer motivated a re-look and I found $286\cdot 35$. I liked the "iff" characterization, though one still needs to examine all the factors of $n$ to apply it. Still that would be fast, since you know one only needs to look at ther factors of $n$ individually, rather than all ways of multiplying several factors to obtain $n$. +1 – coffeemath May 23 '13 at 3:51
More generally $(10^j-1)(10^k-1)<10^{j+k}$. – Zander May 26 '13 at 11:25

This is an interesting idea. A few things that immediately come to mind:

For five digit numbers $n$, $10000 \leq n \leq 99999$. Notice the number of digits required to represent a positive integer $n$ in base 10 is equal to $\lfloor {\log_{10}{n}}\rfloor+1$, which in this case you want to be 5, so $\lfloor {\log_{10}{n}}\rfloor=4$. Also remember that $\log{abc}=\log{a}+\log{b}+\log{c}$.

What happens if $n$ can be factored into, say $abc$? (to take a specific example). Then the factorization requires $\lfloor {\log_{10}{a}}\rfloor+1+\lfloor {\log_{10}{b}}\rfloor+1+\lfloor {\log_{10}{c}}\rfloor+1=\lfloor {\log_{10}{a}}\rfloor+\lfloor {\log_{10}{b}}\rfloor+\lfloor {\log_{10}{c}}\rfloor+3$ digits to represent, and you want this number to also be 5. So you want $\lfloor {\log_{10}{a}}\rfloor+\lfloor {\log_{10}{b}}\rfloor+\lfloor {\log_{10}{c}}\rfloor$=2 which means that either one of a, b, c is between 100 and 999 and the others are between 2 and 9 or two are between 10 and 99 and the other is between 2 and 9.

Can you extend this to more/less than three factors? What if $n$ has 6, 7 digits?

-
An interesting way to look at the search for a given $n$. Of course if $a,b,c$ aren't prime other rearrangements might occur, and of course other numbers of factors may be involved... +1 – coffeemath May 23 '13 at 1:39

Square of prime numbers with 3 digits , for example 10201 = 101 * 101, can´t be written as a product of two or more factors, where the total number (with repetitions) of digits occurring in the factors is five.

-
That seems clear. If $p$ has 3 digits, then $p^2$ can only be factored as $1\cdot p^2$ or $p\cdot p$. The latter is out with six digits, and since as you note $101^2$ already has 5 digits, the extra 1 in the first factorization would bring the digit count up to at least six. Other factored form results would be of interest, even if one plays e.g. the "six digit (or higher) re-write game". +1. – coffeemath Jun 26 '13 at 0:08