16
\$\begingroup\$

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).

example

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

9 Answers 9

6
\$\begingroup\$

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.
\$\endgroup\$
6
\$\begingroup\$

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!

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Arnauld
    Feb 21, 2017 at 16:57
3
\$\begingroup\$

Bash + Unix utilities, 85 84 bytes

for((;;m++)){ dc -e2o$[$1*m]n|egrep -q $(dc "-e2o`factor $1`nBEPn")&&break;}
echo $m

Try it online!


I'll point out also that m always exists for any semiprime n. Here's why:

Write n=pq, where p and q are prime and p <= q.

Let b the number of digits in the binary representation of n-1. Then, for any k between 0 and n-1 inclusive, p*(2^b)+k in binary consists of the binary representation of p followed by b additional bits representing k.

So the numbers p*(2^b)+k for 0 <= k <= n-1, when written in binary, all start with the binary representation of p. But these are n consecutive numbers, so one of them must be a multiple of n.

It follows that we have a multiple mn of n whose binary representation starts with the binary representation of p.

Based on this, one can come up with an upper bound for m of 2 sqrt(n). (One can probably get a much tighter upper bound than this.)

\$\endgroup\$
0
2
\$\begingroup\$

Haskell, 161 bytes

import Data.List
(!)=mod
a#b|a!b==0=b|0<1=a#(b+1)
g 0=[]
g n=g(n`div`2)++show(n!2)
(a%b)c|g b`isInfixOf`g(a*c)=c|0<1=a%b$c+1
f n=min(n%(n#2)$1)$n%(n`div`(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.

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 83 bytes

1//.x_/;FreeQ[Fold[#+##&]/@Subsequences@IntegerDigits[x#,2],d_/;1<d<#&&d∣#]:>x+1&
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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/},^∞}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.