7
$\begingroup$

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.

Improve this question
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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...) $\endgroup$ – tucuxi Apr 17 '15 at 13:24
0
$\begingroup$

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]

Answer:

2212 x 37445 = 221237445 (2212,37445) -- [Decimal: 145003077] (100010100100,1001001001000101)

Or maybe:

2212 x 37445 = 374452212 (37445,2212) -- [Decimal: 306753700] (1001001001000101,100010100100)

I'm not quite sure of the entire answer, but this is a start

Improve this answer
$\endgroup$
1
  • $\begingroup$ x is standard integer multiplication. You should explain why 2 x 3 = 23 (?) or 23 = 19 (?). On the plus side, you have found some of the clues left behind by Mr. EG... $\endgroup$ – tucuxi Apr 16 '15 at 14:39

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.