Find two binary numbers with a multiplication of a specific form

Question

Not sure if this is the best place to ask this question but I tried to search online, wasn't able to find anything useful.

Consider binary numbers of the form $$x=0|y|0|y$$ where $a|b$ means concatenate the bits of $a$ with the bits of $b$, $y$ is any sequence of bits of size $n$.

Is it possible to find three binary numbers $s_1,s_2,s\neq 0$ of the previous form such that $s_1.s_2=s$ where $.$ is just the plain multiplication operator? If not why?

Obviously, all of $s_1,s_2,s$ need to be of size $\leq 2n+2$ bits

Thanks!

score 1 · Accepted Answer · answered Apr 11 '18 at 02:52

1

Observe that $x = (2^{n}+1)y$. If you consider $2^n+1$ to be of the desired form, then we're done. Otherwise, this factorization places some constraints on your desired $s$.

answered Apr 11 '18 at 02:52

Jalex Stark

659

This will require $y$ to be of size greater than $n$ thou, since it need to be of that form too – Shadowfirex Apr 11 '18 at 03:40
@Shadowfirex: no. Consider $y=11_2=3_{10}$. Then $x=11011_2=27_{10}=3\cdot 9$ – Ross Millikan Apr 11 '18 at 03:45
Sorry I noticed the question says "two numbers" I edited that. I meant all of $s_1,s_2,s$ are of that form, for $y=11_2$ it's not the case. – Shadowfirex Apr 11 '18 at 03:55
@Shadowfirex: and how about $y=101_2=5_{10}, x=1010101_2=85_{10}=5\cdot 17$ – Ross Millikan Apr 11 '18 at 03:57
Oh wow, thanks a lot! – Shadowfirex Apr 11 '18 at 04:03

Find two binary numbers with a multiplication of a specific form

1 Answers1