tanishq2507's blog

Why does the base 10 to base b conversion algorithm work?
By tanishq2507, history, 14 months ago, In English

This base conversion algorithm has an application in this problem 1811E - Living Sequence.Why does the base conversion work here.What do the remainders signify in the base conversion?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

you can think of it like just converting to base 9 (because there are 9 digits) but with different namings/symbols.

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

In base 10, you can decompose numbers by their decimal cases, for example

Unable to parse markup [type=CF_MATHJAX]

. The same goes for an arbitrary base

Unable to parse markup [type=CF_MATHJAX]

.

Let $$$n$$$ be a number in base $$$B$$$ with digits

Unable to parse markup [type=CF_MATHJAX]

. Following the same logic as of base $$$10$$$, $$$n$$$ can be written as

Unable to parse markup [type=CF_MATHJAX]

. Now, notice that, all digits have "values" divisible by $$$B$$$, except for digit $$$0$$$. So, we can write $$$n$$$ in the follow way

Unable to parse markup [type=CF_MATHJAX]

. By Euclid's division lemma, the quotient of the division of $$$n$$$ by $$$B$$$ is

Unable to parse markup [type=CF_MATHJAX]

, and the remainder is $$$d_0$$$. Observe that the quotient of that division is the base $$$B$$$ number

Unable to parse markup [type=CF_MATHJAX]

, which is our original number $$$n$$$, without it's last digit. Therefore, we can repeat this procedure until we find all the digits of $$$n$$$.

In the problem you mentioned, you're basically counting in base $$$9$$$, except we are using the digits

Unable to parse markup [type=CF_MATHJAX]

instead of $$$0$$$ to $$$8$$$. So, all you need to do is find the base $$$9$$$ number, and map the digits

Unable to parse markup [type=CF_MATHJAX]

to

Unable to parse markup [type=CF_MATHJAX]

.
→ Reply