# Smallest multiplier that reveals a factor of a semiprime

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 |                                      011 |      3
15 |    1 |            15 |                                       11 |      3
49 |    5 |           245 |                                   10101 |      7
91 |    1 |            91 |                                    101 |     13
961 |   17 |         16337 |                             111010001 |     31
1829 |    5 |          9145 |                             10001001 |     59
9799 |   11 |        107789 |                          10100001101 |     41
19951 |   41 |        817991 |                       1101101000111 |     71
120797 |   27 |       3261519 |                     110000001001111 |    113
1720861 |  121 |     208224181 |               1100011010010101 |   2557
444309323 |  743 |  330121826989 |    10011001101110011001001 |  54443
840000701 | 4515 | 3792603165015 | 11011100110000000101010111 |  35899
1468255967 |   55 |   80754078185 |      100101100110101010001001001 |    911

• Hmm, I smell an algorithm similar to the ones we used on your Blackjack sequence challenge... – ETHproductions Feb 21 '17 at 15:49
• @ETHproductions Hmm, really? They're honestly supposed to be completely unrelated. – Arnauld Feb 21 '17 at 15:55
• 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 Feb 21 '17 at 15:56
• "and probably encouraged" - I'm sorry. We don't care about the speed of our code. – John Dvorak Feb 21 '17 at 16:02
• @JanDvorak Fair enough. Removed. – Arnauld Feb 21 '17 at 16:05

# Pyth, 13 bytes

ff}.BY.B*TQPQ


Demonstration

Explanation:

ff}.BY.B*TQPQ
f                Find the first integer >= to 1 where the following is true
f         PQ    Filter the prime factors of the input
*TQ      Multiply the input by the outer integer
.B         Convert to a binary string
.BY           Convert the prime factor to a binary string
}              Check whether the factor string is in the multiple string.


# 05AB1E, 1816 15 bytes

-2 bytes thanks to Riley!

-1 byte thanks to Emigna!

[N¹*b¹Ñ¦¨båOiNq


Explanation:

[                   # Infinite loop start
N                  # Push the amount of times we have iterated
¹*               # Multiplied by input
b              # Convert to binary
¹Ñ¦¨b         # Calculate the proper divisors of the input in binary excluding one
åO       # Check if a substring of N * m in binary is in the divisors
iNq    # If so, print how many times we have iterated and terminate the program


Try it online!

• ¹Ñ¦¨båO should work instead of checking each substring. – Riley Feb 21 '17 at 16:51
• @Riley thanks for spotting that! – Okx Feb 21 '17 at 16:56
• You can save another byte replacing ¼ and ¾ with N. – Emigna Feb 21 '17 at 17:42
• @Emigna I didn't know about that trick, thanks! – Okx Feb 21 '17 at 17:51

# JavaScript (ES6), 9695 80 bytes

n=>F=m=>(k=p=>p&&(q=1,g=x=>1<x&&x<n&n%x<1|g(x>>1,q*=2))(p)|k(p-q))(n*m)?m:F(-~m)


A function which returns a recursive function which uses a recursive function which uses a recursive function. I'm really starting to wonder if the .toString(2) route would be shorter...

Assign to a variable e.g. f=n=>... and call with an extra pair of parens, f(9)(). If that's not allowed (the meta post is at +6/-2), you can use this 83-byte version with standard invocation:

f=(n,m)=>(k=p=>p&&(q=1,g=x=>1<x&&x<n&n%x<1|g(x>>1,q*=2))(p)|k(p-q))(n*m)?m:f(n,-~m)


Both versions work for all but the last three test cases. You can try these test cases as well by changing x>>1 to (x-x%2)/2.

• Not sure if there's really a consensus about it (we are at +6/-2 at the time of posting), but as far as I'm concerned, the first input format is fine. – Arnauld Feb 21 '17 at 16:57

# Bash + Unix utilities, 85 84 bytes

for((;;m++)){ dc -e2o$[$1*m]n|egrep -q $(dc "-e2ofactor$1nBEPn")&&break;}
f n=min(n%(n#2)$1)$n%(ndiv(n#2))$1  Straightforward check. Factor first, then search linearly starting at 1 and take the minimum of the value for both factors. Takes a few seconds for the last testcase (1468255967), ghci reports (15.34 secs, 18,610,214,160 bytes) on my laptop. ## Mathematica, 83 bytes 1//.x_/;FreeQ[Fold[#+##&]/@Subsequences@IntegerDigits[x#,2],d_/;1<d<#&&d∣#]:>x+1&  # Brachylog (2), 14 bytes ḋḃᵐD∧?:.×ḃs∈D∧  Try it online! There's more than one way to write this in 14 bytes in Brachylog, so I went for the most efficient. As is common for Brachylog submissions, this is a function submission; its input is the semiprime, its output is the multiplier. ## Explanation ḋḃᵐD∧?:.×ḃs∈D∧ ḋ Prime decomposition (finds the two prime factors) ḃᵐ Convert each factor to binary D Name this value as D ∧? Restart with the user input :.× The output is something that can be multiplied by it ḃ to produce a number which, when expressed in binary s has a substring ∈D that is an element of D ∧ (suppress an implicit constraint that D is the output; it isn't)  Prolog's and Brachylog's evaluation order is set by the first constraint that can't immediately be deduced from the input. In this program, that's a constraint on the result of a multiplication, so the interpreter will aim to keep the operands of the multiplication as close to 0 as possible. We know one of the operands, and the other is the output, so we find the smallest output we can, which is exactly what we want. # PowerShell, 136 bytes param($n)$a=2..($n-1)|?{!($n%$_)}|%{[convert]::ToString($_,2)};for(){$b=[convert]::toString(++$m*$n,2);if($a|?{$b-like"*$_*"}){$m;exit}}


Try it online!

Very lengthy due to how conversion-to-binary works in PowerShell. :-/

Takes input $n, loops through 2 to $n-1 and pulls out the factors !($n%$_). Sends those into a loop |%{...} and converts each of them to a binary (base 2) string. Stores those binary strings into $a. Then we enter an infinite for(){...} loop. Each iteration, we increment ++$m, multiply that by $n, and convert that to a binary string, stored into $b. Then, if that string is regex -like any strings in $a, we output $m and exit.

# Perl 6, 66 bytes

->\n{first {(n*$_).base(2)~~/@(grep(n%%*,2..^n)».base(2))/},^∞}  Regex-based. Super slow, because it brute-forces the factors of n all over again at every regex match position of every number that is tried. Calculating the factors only once, improves performance but makes it 72 bytes: ->\n{my @f=grep(n%%*,2..^n)».base(2);first {(n*$_).base(2)~~/@f/},^∞}