16
1
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
Hmm, I smell an algorithm similar to the ones we used on your Blackjack sequence challenge... – ETHproductions – 2017-02-21T15:49:48.203
@ETHproductions Hmm, really? They're honestly supposed to be completely unrelated. – Arnauld – 2017-02-21T15:55:09.867
Well, they're mainly similar in that you need to check every contiguous substring for a specific property. Other than that they really are pretty unrelated. – ETHproductions – 2017-02-21T15:56:31.490
"and probably encouraged" - I'm sorry. We don't care about the speed of our code. – John Dvorak – 2017-02-21T16:02:14.463
@JanDvorak Fair enough. Removed. – Arnauld – 2017-02-21T16:05:02.323
Perhaps it would be faster to divide N by every substring of N*m, even, and not attempt factorization? – John Dvorak – 2017-02-21T16:05:20.030
Don't worry. You can still encourage us, even if it doesn't affect our code. – John Dvorak – 2017-02-21T16:06:06.147
In JavaScript particularly, must we support all inputs for which
N*m
is under 2^53, or can we stop at 2^31? – ETHproductions – 2017-02-21T19:41:16.413@ETHproductions Because
2^31
is a limit of the language for certain operations, I'd say that it's OK. – Arnauld – 2017-02-21T19:57:14.213