12
$\begingroup$

I was able to work out the cases for $n$ having up to $4$ digits and was wondering if someone could verify my generalization to $m$ digits. Here I am assuming that when a reversal results in there being a leading $0$ it get ignored (e.g. $76130$ gets reversed to $3167$, $998700$ to $7899$ etc.)

I believe the function can be expressed as $r(n): \mathbb{N} \rightarrow \mathbb{N}$ $$r(n) = \left \lfloor \frac{n}{10^m}\right \rfloor +\sum_{k=0}^{m-1}10^{m-k} \left( \left \lfloor\frac{n}{10^k} \right \rfloor-10 \left \lfloor \frac{\left \lfloor \frac{n}{10^k}\right \rfloor}{10}\right \rfloor \right)$$

where again, $n$ has $m$ digits.

It seems like this combination of the floor function and powers of 10 is the only way to achieve this but is this true?

$\endgroup$
  • $\begingroup$ I find hard to imagine that such kind of formula has any theorical or numerical use... See "bit reversal" for base two. And this related (dup?) math.stackexchange.com/questions/323268/… $\endgroup$ – leonbloy Aug 21 '13 at 17:55
  • 1
    $\begingroup$ Note: If you drop the initial zeros, applying the reversal operation twice will not be the identity. $\endgroup$ – Mark Bennet Aug 21 '13 at 18:03
7
$\begingroup$

Your first term is always $0$, and you’re off by a factor of $10$; for example, by your formula

$$\begin{align*} r(123)&=\left\lfloor\frac{123}{100}\right\rfloor+\sum_{k=0}^210^{3-k}\left(\left\lfloor\frac{123}{10^k}\right\rfloor-10\left\lfloor\frac1{10}\left\lfloor\frac{123}{10^k}\right\rfloor\right\rfloor\right)\\\\ &=0+1000(123-120)+100(12-10)+10(1-0)\\ &=3210 \end{align*}$$

instead of the correct $321$. However,

$$r(n)=\sum_{k=0}^{m-1}10^{m-1-k}\left(\left\lfloor\frac{n}{10^k}\right\rfloor-10\left\lfloor\frac1{10}\left\lfloor\frac{n}{10^k}\right\rfloor\right\rfloor\right)$$

does the trick.

Suppose that $n=\sum_{i=0}^{m-1}d_k10^i$, where each $d_i\in\{0,1,\dots,9\}$, and $d_{m-1}\ne 0$, so that the decimal expansion of $n$ is $d_{m-1}d_{m-2}\ldots d_1d_0$. Then

$$\left\lfloor\frac{n}{10^k}\right\rfloor=\sum_{i=k}^{m-1}d_i10^{i-k}=10\sum_{i=k+1}^{m-1}d_i10^{i-k}+d_k\;,$$

so

$$\left\lfloor\frac{n}{10^k}\right\rfloor-10\left\lfloor\frac1{10}\left\lfloor\frac{n}{10^k}\right\rfloor\right\rfloor=\left(10\sum_{i=k+1}^{m-1}d_i10^{i-k}+d_k\right)-10\sum_{i=k+1}^{m-1}d_i10^{i-k}=d_k\;,$$

and

$$r(n)=\sum_{k=0}^{m-1}10^{m-1-k}d_k=\sum_{k=0}^{m-1}d_{(m-1)-k}10^k\;,$$

whose decimal expansion is $d_0d_1\ldots d_{m-2}d_{m-1}$, as desired.

$\endgroup$
  • $\begingroup$ Yes, that's right. Not sure how I missed that. Thanks for checking my formula. $\endgroup$ – Patrick Aug 21 '13 at 20:48
  • $\begingroup$ @Patrick: You’re welcome. $\endgroup$ – Brian M. Scott Aug 21 '13 at 20:49
2
$\begingroup$

This is what I came up with: $$\sum_{k=1}^{n}10^{k-1}\frac{xmod10^{n-k-1}-xmod10^{n-k}}{10^{n-k}}$$ Where n is the number of digits in the number x, it could be replaced with $\lfloor{log_{b}x}\rfloor+1$
I believe it works in different bases (just change 10 for the desired base), although it has only been tested in base 10! Taking the first term k = 1, with n = 3 for example gives: $$\frac{xmod1000-xmod100}{100}$$ The $xmod1000$ term returns the original number, the $xmod100$ term returns the remainder after division by 100 which will be the two digit number after the "number of hundreds", the result will then be the number of hundreds eg. for 345 the numerator will be 300, dividing by 100 returns 3. The next term in the series essentially does the same thing, the fraction returns the value the next power of ten along with one important difference; the $10^{k-1}$ term makes the digit be worth ten times what it was so in the 345 example the 3 will be worth 3 instead of 300 the for will remain at the same value of 40 and the 5 will be worth 500 because $10^{3-1}$ = 100 so at the third pass the value of the fraction is equal to 100 times the value of the digit at the third place. Adding all the terms together reverses the number 345 becomes 543, 1432 becomes 2341. If my explanation isn't clear let me know!

$\endgroup$
1
$\begingroup$

We start again with the Kronecker delta:

$$\delta \left( x,y \right) =\cases{1&$x=y$\cr 0&$x\neq y$\cr}\quad\qquad\quad\qquad\quad\qquad\quad\qquad\quad\qquad\quad\qquad\quad\qquad\quad\quad\quad\quad\quad\quad\quad\text{ (1)}$$

Which allows us to express the digits of a number 'a' in base 'b' in a computable integer sequence, in that we already know the exact length of the sequence which is of course the number of digits in total. The expression for this computation is:

$$d_{{n}} \left( a,b \right) =\sum _{k=1}^{ \Bigl\lfloor {\frac { \ln \left( a \right) }{\ln \left( b \right) }}\Bigr\rfloor +1} \left( \delta \left( n,k \right) -b\delta \left( n,k+1 \right) \right) \Bigl\lfloor{a{b}^{k- {\Bigl\lfloor\frac {\ln \left( a\right) }{\ln \left( b \right) }\Bigr\rfloor} -1}} \Bigr\rfloor \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$

For example, $a=12345$ in base $b=10:$ will, purely coincidentally of course, evaluate to the arithmetic progression with initial value of 1 and d=1 of length 5: $$\left\{ d_{{1}} \left( 12345,10 \right) ,d_{{2}} \left( 12345,10 \right) ,d_{{3}} \left( 12345,10 \right) ,d_{{4}} \left( 12345,10 \right) ,d_{{5}} \left( 12345,10 \right) \right\} = \left\{ 1,2,3,4, 5 \right\} $$

But this(2) will compute the $n^{th}$ digit for the number in any base $b>1$, and thus these values correspond to the coefficients of the b-adic expansion * of the number thus we have as follows:

$$\mathcal{P} \left( a,b \right) =\sum _{n=0}^{ \Bigl\lfloor { \frac {\ln \left( a \right) }{\ln \left( b \right) }} \Bigr\rfloor +1}d_{ {n}} \left( a,b \right) {b}^{n}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{ (3)} $$

And from this we can perform digit reversal as follows in any base as far as I can guess, although don't quote me on it because when I noticed this i thought it was too silly to share so i haven't checked other values of b:

$${\frac {\mathcal{P} \left( N,b \right) }{b}}$$

$$\frac{\mathcal{P} \left( 12345,10 \right)}{10} =54321$$

$$\frac{\mathcal{P} \left( 13454345345,10 \right)}{10} =54354345431$$

$$\frac{\mathcal{P} \left( 842622684442,10 \right)}{10} =244486226248$$

I'm sorry if that was overkill, but I am still working on the formal proof for a lot of things with p-adic integers and I have had some pretty traumatic experiences with induction.

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