Given a semiprime N, find the smallest positive integer m such that the binary representation of one of the two factors of N can be found in the binary representation of N * m.
Example
Let's consider the semiprime N = 9799.
We try different values of m, starting at 1:
m | N * m | N * m in binary
---+--------+------------------
1 | 9799 | 10011001000111
2 | 19598 | 100110010001110
3 | 29397 | 111001011010101
4 | 39196 | 1001100100011100
5 | 48995 | 1011111101100011
6 | 58794 | 1110010110101010
7 | 68593 | 10000101111110001
8 | 78392 | 10011001000111000
9 | 88191 | 10101100001111111
10 | 97990 | 10111111011000110
11 | 107789 | 11010010100001101
We stop here because the binary representation of the last product contains 101001
which is the binary representation of 41, one of the two factors of 9799 (the other one being 239).
So the answer would be 11.
Rules and notes
- Trying even values of m is pointless. They were shown in the above example for the sake of completeness.
- Your program must support any N for which N * m is within the computing capabilities of your language.
- You are allowed to factorize N beforehand rather than trying each possible substring of the binary representation of N * m to see if it turns out to be a factor of N.
- As proven by MitchellSpector, m always exists.
- This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.
Test cases
The first column is the input. The second column is the expected output.
N | m | N * m | N * m in binary | Factor
-----------+------+---------------+----------------------------------------------+-------
9 | 3 | 27 | [11]011 | 3
15 | 1 | 15 | [11]11 | 3
49 | 5 | 245 | [111]10101 | 7
91 | 1 | 91 | 10[1101]1 | 13
961 | 17 | 16337 | [11111]111010001 | 31
1829 | 5 | 9145 | 1000[111011]1001 | 59
9799 | 11 | 107789 | 1[101001]0100001101 | 41
19951 | 41 | 817991 | 1[1000111]101101000111 | 71
120797 | 27 | 3261519 | 11000[1110001]0001001111 | 113
1720861 | 121 | 208224181 | 11000110100[100111111101]10101 | 2557
444309323 | 743 | 330121826989 | 100110011011100110010[1101010010101011]01 | 54443
840000701 | 4515 | 3792603165015 | 11011100110000[1000110000111011]000101010111 | 35899
1468255967 | 55 | 80754078185 | 1001011001101010100010[1110001111]01001 | 911