1
$\begingroup$

Consider any 2 binary numbers, e.g.: 10101011 ; 11111101 and their product, say P.

"Reverse" (mirror image) all the digits of the 2 numbers, e.g.: 11010101 ; 10111111

and consider their product, say M.

Question

Is there any simple math relation between P and M ? Can I get M only knowing P ?

PS. Please assume:

    The numbers always start and end with 1.
    The numbers have the same number of digits 
     or, even better, in any case the lengths of those 2 numbers are *known*

(Thank you to user2566092 for asking about possible constraints)

PS. Another interesting condition, suggested by the notes of Steve Kass, might be that P is a semiprime.

$\endgroup$
8
  • 1
    $\begingroup$ The requirement that the numbers both begin and end with 1 is a very strong one. If you just assume the lengths of the numbers are known, here’s a counter-example of lengths 6: Suppose $M=180$. Then the reversed numbers could have been (000011 and 111100) or (000101 and 100100), and these don’t have the same value of $P$. $\endgroup$ – Steve Kass Apr 19 '14 at 21:54
  • $\begingroup$ @Steve Kass Thank you. That is why I introduced it :-) I am trying to make the inversion meaningful :-) Does your argument also hold with the whole set of constraints ? Actually the 1...1 is just what I need in my practical circumstances (I also know the lengths). $\endgroup$ – Pam Apr 19 '14 at 21:59
  • $\begingroup$ Surely if one allows ending with 0's, they get "destroyed" in the reverse ("mirroring"), so the problem is not actually interesting in that case. $\endgroup$ – Pam Apr 19 '14 at 22:01
  • $\begingroup$ Here's a counterexample assuming you know each number begins and ends with 1, and you know each length (but the lengths may be different): 101*1101001 = 111*1001011, but 101*1001011 != 111*1101001. $\endgroup$ – Steve Kass Apr 19 '14 at 22:08
  • 1
    $\begingroup$ You asked “Can I get M only knowing P?” My examples show that the answer to this question is no, because they show that you can have the same P value in two situations that have different M values. Take the first example. 000011*111100=000101*0100100=180, so if this is P, you don't know if M was 110000*001111=720 or 101000*0010010=360. (I reversed M and P from the way you asked the question, but it doesn't matter which you call which - there are examples where you can't deduce one from the other, because there are multiple possibilities.) $\endgroup$ – Steve Kass Apr 19 '14 at 23:43
1
$\begingroup$

I will assume both numbers have the same length. If $A=a_n2^n+a_{n-1}2^{n-1}+\cdots +a_0$, $B=b_n2^n+b_{n-1}2^{n-1}+\cdots +b_0$ then $$A\times B=(a_0b_0)+(a_0b_1+a_1b_0)2+\cdots (a_nb_n)2^{2n}$$ The product of the reversals would be $$A_R\times B_R=(a_nb_n)+(a_nb_{n-1}+a_{n-1}b_n)2+\cdots (a_0b_0)2^{2n}$$ In other words, don't carry while multiplying. Then P and M will be reversals of each other. Otherwise, the counterexample given in the comments seems to show that no function of P will yield M.

$\endgroup$
1
  • $\begingroup$ So due to the symmetry of the expressions yielding the digits, if one ignores the carry, it is indifferent in the product going from left to right or vice versa. Could we perhaps say that M = P - Carry and provide an explicit formula for the carry so that we get an explicit relationship between P and M ? $\endgroup$ – Pam Apr 19 '14 at 23:30
1
$\begingroup$

Consider $2^n = 100 \ldots 0 \times 100 \ldots 0$, in binary, where each number has length $n/2$. If you reverse the digits of these two factors you get $1 \times 1 = 1$. So there is no way to recover $n$.

$\endgroup$
1
  • $\begingroup$ @ user2566092 Yes we can assume they have same number of digits (or, better, their lengths are known), and always starting and ending with 1 (I will add this in the question. Thank you for asking to make this more precise) $\endgroup$ – Pam Apr 19 '14 at 21:28
1
$\begingroup$

Half of the question was “Can I get $M$ only knowing $P$?” The answer to this question is no, even under the strong restriction that the original two numbers have the same number of binary digits (known) and both begin and end with a $1$.

Suppose there are two 11-bit binary numbers $a$ and $b$ whose product is $P=ab=2027025_{10}$. What is the “mirror product” of $a$-reversed and $b$-reversed?

Well, it could be that $a=10010000011_2$ and $b=11011011011_2$, because the product of these numbers is $2027025_{10}$. In this case the mirror product $M=11011011011_2*11000001001_2=2711475_{10}$.

But it could also be that $a=10111001101_2$ and $b=10101010101_2$, in which case the mirror product is $M=10110011101_2*10101010101_2=1961505_{10}$

This example shows that one cannot determine $M$ from simply knowing $P$, the length of the two numbers, and the fact that they both begin and end with a $1$ in binary.

$\endgroup$
1
  • $\begingroup$ Right, since knowing P does not uniquely identify its factors, also M (which is obtained by reversing the factors) "inherits" the same ambiguity. Well, anyway we may still be interested in getting at least one of those M, even if not unique. I wonder at this point if P is a modulus (semiprime) then M is unique. $\endgroup$ – Pam Apr 20 '14 at 0:18

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.