8
$\begingroup$

I have a friend ~200 years old mathematician who has forgotten some digits and now he counts things in very strange manner: when he is going to count the $n$-th thing and $n$ contains a digit he cannot pronounce and write (because of his senile memory - oh, poor man) he skip $n$ and tries to think of next smallest number after $n$ that does not contain the digit.

Poor old mathematician who forgot digits 0, 2, 5, 6, 7 counts:
1, 3, 4, 8, 9, 11, 13, 14, 18, 19, 31, 33, 34, 38, 39, 41, 43, 44, 48, 49, 81, 83, 84, 88, 89, 91, 93, 94, 98, 99, 111, 113, ...

He claims that second thing is third, third is fourth, fourth is eighth and do not see any problems at all. However I do have a problem now, that is keep bothering me:

How do I easily name the $n$-th thing in his counting system?

Generally,

Natural numbers that contain certain digits are dropped from $\mathbb{N}$. What is a formula for the $n$th number of this sequence?

Let's look at a plot of the numbers my friend still remember:
$\hskip0.75in$enter image description here
that looks like a random hops at the first glance, but take the difference between $\left(n+1\right)$th and $n$th element and you'll get this:
$\hskip0.75in$enter image description here
hence the second part of the question's title. I believe that this is a some fractal structure and therefore there exist a recurrence relation that is a solution to my problem.

Firstly, I've tried to examine a very simple example: Base 3; digits allowed: 0, 2:

0, 2, 20, 22, 200, 202, 220, 222, 2000, 2002, 2020, 2022, 2200, 2202, 2220, 2222, ...
adjacent differences:
2, 11, 2, 101, 2, 11, 2, 1001, 2, 11, 2, 101, 2, 11, 2, ...

There are some "oscillations" seen...
$\hskip0.75in$enter image description here

Notation:
Let $n$ be the number we want to get, $b$ - the base of numerical system, $D$ - set of digits allowed, then $N(D, b, n)$ - $n$th number in the sequence of numbers of base $b$ with only allowed digits $D$.

So far, I have only seen that $N(\{0,2\},3,n^3+1)=N(\{0,2\},3,n^3)+2$.

Help me, please (at least by small hints or advices) to deduce the relations that will help me to beat the problem and consequently help to reach a compromise between my friend and me. :)

Update
It may seem strange that I ask about generating sequences with some of them already found and even plotted. Indeed, I've already found an easy programming solution that uses combinations of digits to form those numbers and it's highly inefficient and not a matter of talk at this site at all. I'm asking about purely mathematical solution.
Update
I've just seen the sequence of adjacent differences from my example Base 3; digits allowed: 0, 2 that looks like this (in decimal): $$\left\{\begin{cases} 1+3^0,\quad n\equiv 2^0-1\pmod {2^1}\\ 1+3^1,\quad n\equiv 2^1-1\pmod {2^2}\\ 1+3^2,\quad n\equiv 2^2-1\pmod {2^3}\\ \cdots\\ 1+3^p,\quad n\equiv 2^p-1\pmod{2^{p+1}}\\ \cdots \end{cases} \right\}_{n\ge0}$$ In other words, if $a(n)$ is a $n$th element of the sequence, then $$a(2^{p+1} n + 2^p - 1) = 1 + 3^p, \quad p \ge 0$$ Update
Using this ideas, I conclude that $$a(n)=\sum_{i=1}^\infty\frac{1}{2^i}\sum_{j=1}^{2^i}cos(j\,n\,π/2^{i-1})$$ Thus, $$N(\{0,2\},3,n)=N(\{0,2\},3,n-1)+1+3^\wedge(\sum_{i=1}^\infty\frac{1}{2^i}\sum_{j=1}^{2^i}cos(j\,n\,π/2^{i-1}))$$ But this particular solution does not enlighten me on a general solution.

$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

The original answer worked if the digits he could say included zero. I have kept it. Let him be able to say $0,1,3,4,8$, the algorithm would be to express $n$ in base $5$, then change the digits $0 \to 0, 1 \to 1, 2 \to 3, 3 \to 4, 4 \to 8$ and you get the $n^{\text{th}}$ number he can say. So for $n=1234567,$ we have $1234567_{10}=304001232_5 \to 408001242$ as the $1234567^{\text{th}}$ number he can say.

For the original question where he can say $1,3,4,8,9$, because $0$ is among the forgotten numbers, there are $5$ one digit numbers he can say (not $4$), $25$ two digit numbers he can say, etc. For numbers with up to $k$ digits, there are $5+5^2+\dots +5^k=\dfrac {5^{k+1}-5}{5-1}=N(k)$ To find the $n^{\text{th}}$ number he can say, find the $k$ such that $N(k) \lt n \le N(k+1).$ The number will have $k+1$ digits. If $n=N(k+1),$ the $n^{\text{th}}$ number he can say is a series of $k\ 9$'s. Otherwise, compute $d_{k+1}=\left \lfloor \frac {n-N(k)}{5^k} \right \rfloor$, which will be in the range $[0,4]$ With the conversion $0 \to 1, 1 \to 3, 2 \to 4, 3 \to 8, 4 \to 9$ you have the leading digit. Now compute $n_k=n-(1+d_{k+1})5^k$ and express $n_k$. It will be large enough to require $k$ digits. For example, if we want the $397^{\text{th}}$ number he can say, we find $k=3, N(k)=155$ numbers he can say with up to three digits. $d_4=\left \lfloor \frac {397-155}{125} \right \rfloor=1$, so the leading digit is $3$. Then $n_3=397-2\cdot 125=147$ and we continue $d_3=\left \lfloor \frac {147-30}{25} \right \rfloor=4$, so the next digit is $9$. $n_2=147-5\cdot 25=22, d_2=\left \lfloor \frac {22-5}{5} \right \rfloor=3$ so the next digit is $8$ and finally we have $2$ left and the last digit is $4$. The $397^{\text{th}}$ number he can say is $3984$. I hope he remembers $0$.

$\endgroup$
6
  • $\begingroup$ When I've read your answer I was a bit astonished - how couldn't I think of this simple and elegant solution? If we reassign visual representation of digits like this $\mathbf{1}=0,\mathbf{3}=1,\mathbf{4}=2,\mathbf{8}=3,\mathbf{9}=4$ then $1,3,4,8,9,11,13,14,18,19,31,\dots$ is legal numerical system of base $5$, but it can take a while to get used to it. To convert a number in such system to normal one we need to replace new digits by their actual values and express resulting number in base $10$. Inverse process is what you've just written. Thank you a lot! $\endgroup$ Commented Nov 9, 2014 at 17:08
  • $\begingroup$ I like your solution of finding $n$th number. It's also applicable for all such counting systems I've described. One note is that if $0$ is allowed we needn't to decrement $n$. $\endgroup$ Commented Nov 9, 2014 at 17:18
  • $\begingroup$ We've missed something... I've just found that if we plug in $7$ in the algorithm, we get result of $31$, not $11$... $\endgroup$ Commented Nov 10, 2014 at 10:20
  • $\begingroup$ @DanyloDubinin: you are right. It is related to the $-1$ I had to put in because $0$ is not allowed. There are then $25$, not $20$ two digit numbers he can say. I'll update. $\endgroup$ Commented Nov 10, 2014 at 15:23
  • 1
    $\begingroup$ The point of my algorithm is that once you decide it has four digits, the one, two, and three digit numbers take up $5+25+125=155$, then each cycle through a given leading fourth digits takes $125$. Since $155+125 \lt 397 \lt 155+125+125,$ we are in the second cycle of four digit numbers. The first has leading digit $1$, the second has leading digit $3$. True, it is coincidence that the leading digit in decimal and in this representation are the same. If we wanted the $402nd$ number it would be $3994$. I think this algorithm works. $\endgroup$ Commented Nov 11, 2014 at 14:09
2
$\begingroup$

At least if you just want asymptotics, it's easier to answer the inverse question first: how many of the integers between $0$ and $N$ (inclusive) can your friend name?

Let's say we work in base $b$ and that your friend can only use $k$ of the possible $b$ digits, and for simplicity let's assume that he can use $0$. The easiest case is when $N = b^n - 1$, since in this case it's clear that your friend can name exactly $k^n$ numbers: of the $n$ possible digits, your friend can freely choose each of them to be one of the $k$ allowable digits.

That is, if $f_{b, k}(N)$ is the number of integers between $0$ and $N$ that your friend can name, then

$$f_{b, k}(b^n - 1) = k^n.$$

This suggests that asymptotically we expect

$$f_{b, k}(N) \approx N^{ \log_b k }$$

and hence the inverse function should asymptotically satisfy

$$f_{b, k}^{-1}(M) \approx M^{ \log_k b }.$$

Disallowing $0$ isn't much harder and doesn't change the asymptotics much but getting more precise counts is fiddly and depends on both the digits of $M$ and on the digits that are allowed / disallowed. In your original example,

$$f_{10, 5}^{-1}(M) \approx M^{ \log_5 10} \approx M^{1.43}$$

although this won't be all that accurate for random values of $M$ because a lot depends on whether a particular first digit is allowed.

$\endgroup$
1
  • $\begingroup$ Your explanations are great. Thank you, I appreciate your analysis. I was thinking about the inverse question but couldn't figure out how it would help. Now it's clear for me. $\endgroup$ Commented Nov 8, 2014 at 12:15

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.