6
$\begingroup$

Take the sequence of Natural numbers which do not contain the digit zero.

So your sequence becomes:

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12 ...

Can we find an expression for ${a_n}$ ?

$\endgroup$
  • $\begingroup$ @JackV, I thought that too... but you skip numbers like 10, or 103 because they contain a 0. $\endgroup$ – TravisJ May 6 '15 at 1:04
  • $\begingroup$ Yup ${a_{10}}$ = 11 not 10 $\endgroup$ – Adeetya May 6 '15 at 1:04
  • $\begingroup$ @Adeetya Oh my apologies i misunderstood $\endgroup$ – JackV May 6 '15 at 1:05
  • 3
    $\begingroup$ You could probably write something nasty involving $\log_{10}$, floor, etc. But why, when it's simpler to describe it in English? $\endgroup$ – aschepler May 6 '15 at 1:05
  • $\begingroup$ Do you need this in some sort of code. What is the purpose. $\endgroup$ – Ilaya Raja S May 13 '15 at 18:58
5
$\begingroup$

There are $9^m$ members of $\{a_n\}$ with $m$ digits. After that, the $(m+1)$-digit members of $\{a_n\}$ follow the rule that $a_n = a_{\left(n-9^m\right)} + 10^m.$ And then the pattern repeats.

$\endgroup$
  • $\begingroup$ I have got the following expression for $a_n$ in the AoPS link artofproblemsolving.com/community/c6h474012p2654654 by user BISHAL_DEB #8 $$a_n=n +\sum_{i=1}^\infty 10^{i-1}\times[\frac{n-(9^i-1)/8}{9^i}]$$ where [] is the floor function I have no idea on how to prove this.can you throw some light on this.Thanks $\endgroup$ – Navin May 11 '17 at 21:27
1
$\begingroup$

Yes. $a_{n}=n+p(n)$ where $p(n)$ is the number of natural numbers at most $n$ that contain a zero digit. There is a nice combinatorial way to do this if you write out the base 10 digits of $n$. The way you count $p(n)$ is to write out $n=d_{m}d_{m-1}...d_{2}d_{1}d_{0}$ where each $d_{i}$ is a decimal digit of $n$. Then, how many numbers can you make that have a zero somewhere in there and are smaller than (or equal to) $n$? Construct a number (with a zero digit) that is $b_{m}b_{m-1}...b_{2}b_{1}b_{0}$. $b_{m}\leq d_{m}$. If $b_{m}<d_{m}$ then you fix it, and count how many $m-1$ digit numbers there are with a zero. Repeat, repeat. There should be a "nice" formula involving a sum and product of binomial coefficients.

$\endgroup$
0
+50
$\begingroup$

There’s a very nice characterization of $a_n$ in the Online Encyclopedia of Integer Sequences entry for this sequence (A052382), which is attributed to Robin Garcia. Here’s how it goes.

The number $a_n$ is $\sum_{i=0}^k d_i {10}^i$ (i.e., the base-10 number $d_kd_{k-1}\dots d_0$), where $d_kd_{k-1}\dots d_0$ is the representation of $n$ in “modified base 9,” which has the same place-value interpretation as base 9 but uses the digits $1$ through $9$ instead of the usual base-9 digits $0$ through $8$. (Every positive integer has a unique representation in “modified base 9.”)

For example, to find $a_{118349}$, first write $118349$ in regular base $9$: $118349_{ten}={200308}_{nine}$. Now, zeros are not allowed in modified base 9, so eliminate them from right to left by “borrowing nine” from the left and adding it to each zero you encounter: $${118349}_{ten}={200\color{red}{\it 30}8}_{nine}=200\color{red}{\bf 29}8_{nine}=\color{blue}{\it 200}298_{nine}=\color{blue}{\bf 189}298_{nine}.$$

Thus $a_{118349}=189298.$ To find the modified base-9 representation of $118349$, we needed to “borrow” twice: $$30_{nine}=3\cdot9+0=2\cdot9+9=29_{nine};$$ $$200_{nine}=2\cdot9^2+0\cdot9+0=1\cdot9^2+9\cdot9+0=1\cdot9^2+8\cdot9+9=189_{nine}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.