0
$\begingroup$

I was wondering why for example $\dfrac{1111_b \cdot 111_b}{11_b \cdot 1_b} = 11211_b$. Is there a good explanation for this and is there a name for products like this which have constant digits value independent of base? It also seems to hold with $\dfrac{11111_b \cdot 1111_b \cdot 111_b}{111_b \cdot 11_b \cdot 1_b}$ and other numbers as well.

Here is my general question:

Prove that $$R(m,k) = \frac{ 1^{(m)}_b \cdot 1^{(m-1)}_b\cdots 1^{(m-k+1)}_b}{1^{(1)}_b \cdot 1^{(2)}_b\cdots 1^{(k)}_b} = c_b$$ where $c$ is a constant and $b>2$.

$\endgroup$
  • $\begingroup$ The digit 2 does not exist in binary. $\endgroup$ – mathreadler Jun 25 '16 at 13:02
  • $\begingroup$ @mathreadler For any base other than $2$. $\endgroup$ – Puzzled417 Jun 25 '16 at 13:03
  • $\begingroup$ @Puzzled417, Write $$1111_b$$ as $$1+b+b^2+b^3$$ etc. $\endgroup$ – lab bhattacharjee Jun 25 '16 at 13:05
  • $\begingroup$ Typo in the numerator with $111_b$? $\endgroup$ – Piquito Jun 25 '16 at 13:17
0
$\begingroup$

This is because multiplication in a number system becomes a special type of convolution with carry. If the digits involved are small enough compared to the base used, then carry will never happen and we can calculate expressions like yours for example as a sequence of polynomial multiplications and divisions.


For example the first one: $1111_b$ can first be divided by $11_b$ to produce $101_b$, then the multiplication will be $111_b + 100_b\cdot 111_b = 11211_b$

$\endgroup$
  • $\begingroup$ In fact, the generalization is in terms of repunits. Let $$R(m,k) = \frac{ 1^{(m)}_b \cdot 1^{(m-1)}_b\cdots 1^{(m-k+1)}_b}{1^{(1)}_b \cdot 1^{(2)}_b\cdots 1^{(k)}_b} = c_b$$ where $c$ is a constant. $\endgroup$ – Puzzled417 Jun 25 '16 at 13:14
  • $\begingroup$ Yes but it will work for arbitrary polynomials if we ensure the coefficients are not too large. Arbitrary polynomials are more general than products and quotients of repunits. $\endgroup$ – mathreadler Jun 25 '16 at 13:18
  • $\begingroup$ Can you prove it in the case of the repunits? $\endgroup$ – Puzzled417 Jun 25 '16 at 13:23
  • $\begingroup$ That was not your original question. $\endgroup$ – mathreadler Jun 25 '16 at 13:41

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.