Finding the 'decryption' algorithm

114 Views Asked by At

We have an encryption procedure, and we want to get an algorithm in order to recover the original number. The encryptation process is the following:

$$\text{Given a }n>0\text{, we concatenate } n \text{ times the decimal expression of }n. $$ $$\text{Then, we simply count the number of digits of the resulting number.}$$

For example, the encryptation of the numbers with only one digit are itselves.

If we denote the number of digits of a number $n$ as $d(n)$, clearly we are sending $n$ to $n\cdot d(n)$.

Then, given $k=n⋅d(n)$ for a certain $n\in\mathbb{N}$, how we could find the original number $n$? I attacked the problem in the following way: We can express the $d$ operator as $$d(n)=\left \lfloor{\log_{10}(n)}\right \rfloor+1$$ so we would need to find a inverse to the function $f(n)=n(\left \lfloor{\log_{10}(n)}\right \rfloor+1)$, but I could not get an inverse function, and we know for sure that doesn't exist in a general sense because $f$ is not exhaustive.

Any ideas?

2

There are 2 best solutions below

0
On BEST ANSWER

Since (writing $d$ for $d(n)$)

$$d\cdot 10^{d-1} \leqslant k < d\cdot 10^d,$$

you have

$$d-1 + \log_{10} d \leqslant \log_{10} k < d + \log_{10} d.$$

That gives a fairly small range of possible values for $d$ starting with $d \approx \log_{10} k$ (the range is $\approx \log_{10} \log_{10} k$). Once $d$ is determined, one has

$$n = \frac{k}{d}.$$

2
On

https://en.wikipedia.org/wiki/Binary_search_algorithm can easily do that since f(n) is monotonous.