Smallest multiplier that reveals a factor of a semiprime
05AB1E, 18 16 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!
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.
JavaScript (ES6), 96 95 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
.