Converting Numbers Between Different Bases: Is It Possible to Use Only n Digits?

[evinda]

Hello! (Wave)

We consider the usual representation of non-negative integers, where the digits correspond to consecutive powers of the basis in a decreasing order.
Show that at such a representation, for the conversion of a number with basis $p$ to a system with basis $q$, where $p=q^n$ and $n$ positive integer, it suffices that each digit of the number is expressed from initial system of basis $p$ to the system of basis $q$, using $n$ digits of the system of basis $q$.
Also the rule should be stated and it should be proved at the reverse case, i.e. when the conversion is done from the system of basis $q$ to the system of basis $p$.

Could you give me a hint how we could show this? (Thinking)

 

[I like Serena]

Hey evinda!

So we have a number like $p_0 + p_1\cdot p + p_2\cdot p^2 +\ldots$ yes?
And we have $p=q^n$ so that number is the same as $p_0 + p_1\cdot q^n + p_2\cdot q^{2n} +\ldots$.
That is a representation in the system with basis $q$ isn't it?
So if we needed $m$ digits to represent the number in the system with basis $p$, we can represent the number with $m$ digits in the system with basis $q$ as well.

 

[evinda]

Hey evinda!

So we have a number like $p_0 + p_1\cdot p + p_2\cdot p^2 +\ldots$ yes?
And we have $p=q^n$ so that number is the same as $p_0 + p_1\cdot q^n + p_2\cdot q^{2n} +\ldots$.
That is a representation in the system with basis $q$ isn't it?

Yes, it is... (Nod) But how do we know that the coefficients $p_0,p_1, \dots$ are also based on the system of basis $q$ ? (Thinking)

So if we needed $m$ digits to represent the number in the system with basis $p$, we can represent the number with $m$ digits in the system with basis $q$ as well.

Yes, but we need to show that $n$ digits suffice, right?

 

[I like Serena]

Yes, it is... But how do we know that the coefficients $p_0,p_1, \dots$ are also based on the system of basis $q$ ?

Didn't we just show that? :unsure:
We effectively wrote the same number with respect to the system with basis $q$, didn't we?

Yes, but we need to show that $n$ digits suffice, right?

Could it be that's a mistake in the problem statement?

Consider for example that $p=100$ and $q=10$. So $n=2$.
We can represent the number $10203$ with respect to $p$ as $123$, and we can represent the same number with respect to $q$ as $10203$.
In this case we need $m=3$ digits to represent the number and $n=2$ digits does not suffice to represent the number. :unsure:

 

[evinda]

Didn't we just show that? :unsure:
We efectively wrote the same number with respect to the system with basis $q$, didn't we?

Do we know that $p_0,p_1,p_2, \dots$ are also written in the system with basis $q$, since $p=q^n$ and so $p<q$ ?

Could it be that's a mistake in the problem statement?

Consider for example that $p=100$ and $q=10$. So $n=2$.
We can represent the number $10203$ with respect to $p$ as $123$, and we can represent the same number with respect to $q$ as $10203$.
In this case we need $m=3$ digits to represent the number and $n=2$ digits does not suffice to represent the number. :unsure:

We have that $\frac{10203}{100}=102 \cdot 100+3$ and so $10203=1023$ with respect to $100$ and $\frac{10203}{10}=1020 \cdot 10+3$ and so $10203=10203$ with respect to $10$, right? (Thinking)

 

[I like Serena]

Do we know that $p_0,p_1,p_2, \dots$ are also written in the system with basis $q$, since $p=q^n$ and so $p<q$ ?

More or less. It means that the digits with respect to $q$ are the same - except that there are $n-1$ zeroes in between each of the digits.

We have that $\frac{10203}{100}=102 \cdot 100+3$ and so $10203=1023$ with respect to $100$ and $\frac{10203}{10}=1020 \cdot 10+3$ and so $10203=10203$ with respect to $10$, right? (Thinking)

More accurately, we have $10203=1\cdot 100^2+2\cdot 100^1+3\cdot 100^0$ with respect to $p=100$.
And we have $10203=1\cdot 10^4+0\cdot 10^3 + 2\cdot 10^2+0\cdot 10^1 + 3\cdot 10^0$ with respect to $q=10$.

 

[evinda]

Didn't we just show that? :unsure:
We effectively wrote the same number with respect to the system with basis $q$, didn't we? Could it be that's a mistake in the problem statement?

Consider for example that $p=100$ and $q=10$. So $n=2$.
We can represent the number $10203$ with respect to $p$ as $123$, and we can represent the same number with respect to $q$ as $10203$.
In this case we need $m=3$ digits to represent the number and $n=2$ digits does not suffice to represent the number. :unsure:

Is it maybe meant that each digit of the number is expressed with $n$ digits of the system $q$ ?

For example in this case $3$ is written as $03$, $2$ as $02$ and $1$ to $01=1$.

So since $p=q^n$ it means that each digit in the $p$-system corresponds to $n$ digits of the $q$-system.

But is this statement sufficient when we want to prove that for the conversion of a number from the $p$-system to the $q$-system that then it suffices that each digit of the number is expressed using $n$ digits of the $q$-system?

 

[evinda]

Also the rule should be stated and it should be proved at the reverse case, i.e. when the conversion is done from the system of basis $q$ to the system of basis $p$.

Could you give me a hint how we could show this? (Thinking)

For the reverse case, we begin from the end and we pick consecutively $n$-digits at the $q$-system that correspond to one digit of the $p$-system. At the beginning, we might need to add 0s to get $n$ digits. Right? How could this rule be proved? (Thinking)

 

[I like Serena]

Is it maybe meant that each digit of the number is expressed with $n$ digits of the system $q$ ?

For example in this case $3$ is written as $03$, $2$ as $02$ and $1$ to $01=1$.

So since $p=q^n$ it means that each digit in the $p$-system corresponds to $n$ digits of the $q$-system.

But is this statement sufficient when we want to prove that for the conversion of a number from the $p$-system to the $q$-system that then it suffices that each digit of the number is expressed using $n$ digits of the $q$-system?

Ah right. That makes more sense. (Nod)

So we start with a number $p_0 + p_1 \cdot p^1 + p_2\cdot p^2 + \ldots$, which is equal to $p_0 + p_1 \cdot q^n + p_2\cdot q^{2n} + \ldots$.
We have that each $p_i$ is between $0$ and $p-1=q^n-1$.
So each of the $p_i$ can be written as an n-digit number with respect to $q$.
That is, we can write $p_i = q_{i0} + q_{i1} q^1 +\ldots + q_{i(n-1)} q^{n-1}$ with appropriate $q_{ij}$.

For the reverse case, we begin from the end and we pick consecutively $n$-digits at the $q$-system that correspond to one digit of the $p$-system. At the beginning, we might need to add 0s to get $n$ digits. Right? How could this rule be proved?

We can start with the general number $q_0+q_1 \cdot q^1+q_2\cdot q^2+\ldots$.
Now we can group those terms in groups of $n$, can't we? And each group corresponds to a digit with respect to $p$.

 

[evinda]

Ah right. That makes more sense. (Nod)

So we start with a number $p_0 + p_1 \cdot p^1 + p_2\cdot p^2 + \ldots$, which is equal to $p_0 + p_1 \cdot q^n + p_2\cdot q^{2n} + \ldots$.
We have that each $p_i$ is between $0$ and $p-1=q^n-1$.
So each of the $p_i$ can be written as an n-digit number with respect to $q$.
That is, we can write $p_i = q_{i0} + q_{i1} q^1 +\ldots + q_{i(n-1)} q^{n-1}$ with appropriate $q_{ij}$.

I see! (Nod)

We can start with the general number $q_0+q_1 \cdot q^1+q_2\cdot q^2+\ldots$.
Now we can group those terms in groups of $n$, can't we? And each group corresponds to a digit with respect to $p$.

I understand! Thank you very much! (Smirk)