2

Let $s = (s_0, \dots, s_k)$ with $0 \leq s_i \leq 25 \ \forall i$, and $f(s) = s_0 26^0 + s_1 26^1 + s_2 26^2 + \dots + s_{k-1} 26^{k-1}$.

Is it possible, and if so how, to find all the $s_i$ knowing $f(s)$?

For example, if $s = (4, 1, 2, 3)$ then $f(s) = 4 \cdot 1 + 1 \cdot 26 + 2 \cdot 676 + 3 \cdot 17576 = 54110$. How would one go about finding all the $s_i : 4, 1, 2, 3$ from $f$ and its result $54110$?

Ps: I'm a bit of a math novice, so I'd appreciate a "noob friendly" version of an answer.

Alex M.
  • 35,207
darthDoe
  • 23
  • Your post was quite confusing, so I have edited it to clarify its meaning. Despite my best efforts, it is possible that I might have betrayed your intentions, so please check whether my changes still convey what you meant. The current title is not the best, but is clearly better than the original one. – Alex M. Nov 21 '16 at 11:54
  • Ah, sorry about my confusing formulation. Yes, your changes still convey what I meant, thanks for the editing – darthDoe Nov 21 '16 at 12:09

3 Answers3

3

Let's recall the algortihm for compuing the decimal digits of a natural $\rm \,n.$

Let $\rm \,D(n)\,$ be the list of digits of $\rm\,n\,$ and let $\,\sqcup\,$ denote list concatenation.

By division $\rm\, n = 10 q + r\ $ for $\rm \,r = n\bmod 10,\ $ where $\rm \ 0\le r < 10$

Hence $\rm \, D(n) = D(q) \sqcup [r],\, $ which leads to the following algorithm

$\qquad\ \ \ \begin{align} \text{D(n) := }& \text{if $\rm \ n < 10\ $ then $\rm \,[\,n\,]$}\\ &\text{else let $\rm \{\,r = n\bmod 10;\ \ q = (n\!-\!r)/10\,\}$}\\ &\qquad\ \ \rm D(q)\sqcup [\,r\,] \end{align}$

The above algorithm works for any radix $\rm\,b\,$ by replacing $\,10\,$ by $\rm \,b\,$ above.

Bill Dubuque
  • 272,048
  • this in combination with the answer from @Takahiro Waki now makes total sense.. about time I understood how these 'base switches' worked, thanks! – darthDoe Nov 21 '16 at 21:59
  • @darthDoe Yes, that is the same algorithm (except it is not presented in recursive form there). – Bill Dubuque Nov 21 '16 at 22:04
1

Try with smaller basis - 2,8,10,... The algorithm will be analogous, for example:

$s_0 = f(s) (\mod 26^1) $

$s_1 = (f(s) - s_026^0)(\mod 26^2) $

...

$s_n = \left(f(s)-\sum_{k=0}^{n-1}s_k 26^{k}\right)(\mod 26^{n+1})$

Jaroslaw Matlak
  • 4,895
  • I'm not sure if i understand this correctly, but if, like in the example $s=(4,1,2,3)$ and $f(s) = 5411054110$ then my $s_0$ should be $5411054110 \mod 26^1$ but that equals $20$ and not $4$? – darthDoe Nov 21 '16 at 13:39
  • $f((4,1,2,3))=54110$, $54110(\mod 26) = 4$ – Jaroslaw Matlak Nov 21 '16 at 14:24
  • Oh wow, I accidentally pasted the result in twice. Thanks! – darthDoe Nov 21 '16 at 14:39
  • @darthDoe Beware that there is a bug above (you need to cancel $26^i$ to get $,s_i)., $ See my answer for a natural recursive algorithm to compute the digits in any radix. – Bill Dubuque Nov 21 '16 at 16:10
  • @BillDubuque Could you elaborate the bug? – Somebody Nov 21 '16 at 16:58
  • @BillDubuque thanks for pointing that out, I thought I was going crazy for not getting to the right result. Although I have to admit I still don't understand what you mean by "cancel $26^i$ to get $s_i$". – darthDoe Nov 21 '16 at 17:01
  • @darthDoe The above gives $,s_i 26^i,$ so if you want $,s_i,$ you need to cancel/divide by $,26^i.,$ It is more efficient to use the method I describe if you want all of the digits. – Bill Dubuque Nov 21 '16 at 17:09
  • @BillDubuque thanks alot, this approach works now.. at last. I'm still trying to wrap my head around your answer bellow. – darthDoe Nov 21 '16 at 17:44
  • @darthDoe Great. If you need some elaboration on the other method let me know what parts are not clear to you. – Bill Dubuque Nov 21 '16 at 17:53
1

The algorithm is like this. The example 231 base 4.

enter image description here

Takahiro Waki
  • 2,310