Product of "reversed" numbers

298 Views Asked by At

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.

3

There are 3 best solutions below

1
On BEST ANSWER

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.

1
On

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$.

1
On

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.