# Bitwise multiplication

Mr. EG has come up with a great coding scheme for (non-negative) integers in binary. To show off his creation, he demonstrates the following multiplications:

010 x 011 = 010011
011 x 010010 = 010010011
010011 x 010010011 = 010010010011011
01000101 x 01001000111 = 0100100100010100111


What is the result of the following multiplication?

0100010100101 x 01001001001000101


Can you translate all those confusing 1s and 0s back to good old decimal integers?

Note: x represents standard integer multiplication.

The result of the multiplication:

0100010100101 x 01001001001000101 = 010010010010010001010010100101

Description of Mr. EG's coding scheme:

To code a positive integer, factor it as a product of primes, and write those primes in increasing order of size. Write each prime factor in binary, and prepend a number of 0's which is one less than the number of digits. Then concatenate the resulting strings.

As an example, to code $20$, we factor $20=2\cdot 2\cdot 5$. The binary representations of $2$ and $5$ are 10 and 101. We prepend one and two 0's, respectively, to get 010 and 00101. Finally, we concatenate two copies of 010 and one copy of 00101 to get 01001000101.
The purpose of the leading 0's is to indicate the number of digits in each prime, so that a positive integer can be unambiguously recovered from its representation. For instance, if we did not prepend 0's, the string 11111 could either come from $21=3\cdot 7$, or from $31$.

Translating back into decimal, the given multiplications are:
$2\times 3 = 6$,
$3\times 4=12$,
$6\times 12=72$,
$10\times 28=280$.
The missing multiplication becomes $(2\cdot 5\cdot 5)\times(2\cdot2\cdot 2\cdot 2\cdot 5)=4000=(2\cdot2\cdot2\cdot2\cdot2\cdot5\cdot 5\cdot 5)$, which is coded as 010 010 010 010 010 00101 00101 00101.

• Almost perfect (and surprisingly quick!) - you have cracked the encoding and the puzzle. However, your interpretation of 01001000111 is slightly off - it would actually yield 01001000101 when encoded. Fix it and I'll accept your answer. (On a minor note, you write "to encode 30", and then proceed to encode 20...) – tucuxi Apr 17 '15 at 13:24

2 x 3 = 23 (2,3) -- [Decimal: 19]

3 x 18 = 183 (18,3) -- [Decimal: 187]

19 x 147 = 14719 (147,19) -- [Decimal: 9371]

69 x 583 = 69583 (69,583) -- [Decimal: 149671]