1
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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}.$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ True, but the given value $k$ can be as big as $10^{10^6}$. We could as ourselves how many jumps need to be done in such a case... I don't know if is the best option: $\endgroup$
    – BgB
    Commented Aug 2, 2017 at 15:10
  • $\begingroup$ In the worst case scenario we will need $\log_{2}(10^{10^6}) + 1$ jumps (floored), so a total of $3,321,929$ jumps. $\endgroup$
    – BgB
    Commented Aug 2, 2017 at 15:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .