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}$ ?
Asked
Active
Viewed 438 times
6
-
@JackV, I thought that too... but you skip numbers like 10, or 103 because they contain a 0. – TravisJ May 06 '15 at 01:04
-
Yup ${a_{10}}$ = 11 not 10 – May 06 '15 at 01:04
-
@Adeetya Oh my apologies i misunderstood – JackV May 06 '15 at 01:05
-
3You could probably write something nasty involving $\log_{10}$, floor, etc. But why, when it's simpler to describe it in English? – aschepler May 06 '15 at 01:05
-
Do you need this in some sort of code. What is the purpose. – Ilaya Raja S May 13 '15 at 18:58
-
Sorry guys look like I have posted a misunderstood answer so have deleted it – Ilaya Raja S May 15 '15 at 14:48
3 Answers
5
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.
David K
- 98,388
-
I have got the following expression for $a_n$ in the AoPS link https://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 – Navin May 11 '17 at 21:27
1
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.
TravisJ
- 7,426
0
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}.$$
Steve Kass
- 14,881