Bestimmen Sie bei einem Halbwert N die kleinste positive ganze Zahl m , sodass die binäre Darstellung eines der beiden Faktoren von N in der binären Darstellung von N * m gefunden werden kann .

Beispiel

Betrachten wir das Semiprime N = 9799 .

Wir versuchen verschiedene Werte von m , beginnend mit 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

Wir hören hier auf, weil die binäre Darstellung des letzten Produkts 101001die binäre Darstellung von 41 enthält , einer der beiden Faktoren von 9799 (der andere ist 239 ).

Die Antwort wäre also 11 .

Regeln und Notizen

• Versuche gerade Werte von ist sinnlos, m zu . Sie wurden der Vollständigkeit halber im obigen Beispiel gezeigt.
• Ihr Programm muss jedes N unterstützen, für das N * m innerhalb der Rechenkapazitäten Ihrer Sprache liegt.
• Es ist Ihnen gestattet, N vorher zu faktorisieren, anstatt jede mögliche Teilzeichenfolge der Binärdarstellung von N * m zu testen, um festzustellen , ob sich herausstellt, dass es sich um einen Faktor von handelt N handelt .
• Wie von MitchellSpector bewiesen , m immer vorhanden.
• Das ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes. Standardlücken sind verboten.

Testfälle

Die erste Spalte ist die Eingabe. Die zweite Spalte ist die erwartete Ausgabe.

         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

Pyth, 13 Bytes

ff}.BY.B*TQPQ

Demonstration

Erläuterung:

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 , 18 16 15 Bytes

-2 Bytes danke an Riley!

-1 Byte danke an Emigna!

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

Erläuterung:

[                   # 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

Probieren Sie es online!

JavaScript (ES6), 96 95 80 Byte

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)

Eine Funktion, die eine rekursive Funktion zurückgibt, die eine rekursive Funktion verwendet, die eine rekursive Funktion verwendet. Ich beginne mich wirklich zu fragen, ob die .toString(2)Strecke kürzer sein würde ...

Weisen Sie eine Variable zu, z. B., f=n=>...und rufen Sie mit einem zusätzlichen Paar von Parens auf f(9)(). Wenn dies nicht zulässig ist (der Meta-Post befindet sich bei + 6 / -2), können Sie diese 83-Byte-Version mit Standardaufruf verwenden:

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)

Beide Versionen funktionieren mit Ausnahme der letzten drei Testfälle für alle. Sie können diese Testfälle auch versuchen , durch eine Änderung x>>1zu (x-x%2)/2.

Bash + Unix Dienstprogramme, 85 84 Bytes

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

Probieren Sie es online!

Ich werde auch darauf hinweisen, dass m für jedes Semiprime n immer existiert. Hier ist der Grund:

Schreibe n = pq, wobei p und q Primzahl sind und p <= q.

Sei b die Anzahl der Stellen in der Binärdarstellung von n-1. Dann besteht p * (2 ^ b) + k in der Binärdarstellung von p für ein beliebiges k zwischen 0 und n-1 einschließlich aus der Binärdarstellung von p, gefolgt von b zusätzlichen Bits, die k darstellen.

Also beginnen die Zahlen p * (2 ^ b) + k für 0 <= k <= n-1, wenn sie in Binärschrift geschrieben sind, alle mit der Binärdarstellung von p. Da es sich jedoch um n aufeinanderfolgende Zahlen handelt, muss eine davon ein Vielfaches von n sein.

Daraus folgt, dass wir ein Vielfaches von n haben, dessen binäre Darstellung mit der binären Darstellung von p beginnt.

Basierend darauf kann man eine Obergrenze für m von 2 sqrt (n) finden. (Man kann wahrscheinlich eine viel engere Obergrenze als diese bekommen.)

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

Einfache Prüfung. Zuerst Faktor, dann linear ab 1 suchen und für beide Faktoren das Minimum des Wertes nehmen.

Dauert ein paar Sekunden für den letzten Testfall ( 1468255967), ghciberichtet (15.34 secs, 18,610,214,160 bytes)mein 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∧

Probieren Sie es online!

Es gibt mehr als einen Weg, dies in 14 Bytes in Brachylog zu schreiben, also habe ich mich für den effizientesten entschieden. Wie bei Brachylog-Übermittlungen üblich, handelt es sich um eine Funktionsübermittlung. Sein Eingang ist das Semiprime, sein Ausgang ist der Multiplikator.

Erläuterung

ḋḃᵐ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)

Die Auswertungsreihenfolge von Prolog und Brachylog wird durch die erste Einschränkung festgelegt, die nicht sofort aus der Eingabe abgeleitet werden kann. In diesem Programm ist dies eine Einschränkung für das Ergebnis einer Multiplikation. Der Interpreter versucht daher, die Operanden der Multiplikation so nahe wie möglich an 0 zu halten. Wir kennen einen der Operanden und der andere ist die Ausgabe, also finden wir die kleinste Ausgabe, die wir können, genau das, was wir wollen.

PowerShell , 136 Byte

param($n)$a=2..($n-1)|?{!($n%$_)}|%{[convert]::ToString($_,2)};for(){$b=[convert]::toString(++$m*$n,2);if($a|?{$b-like"*$_*"}){$m;exit}}

Probieren Sie es online!

Sehr langwierig, da die Konvertierung in eine Binärdatei in PowerShell funktioniert. : - /

Nimmt die Eingabe $n, Schleifen durch 2zu $n-1und holt die Faktoren !($n%$_). Sendet diese in eine Schleife|%{...} und converts jeder von ihnen zu einer binären (Basis- 2) Zeichenfolge. Speichert diese binären Zeichenfolgen in $a.

Dann betreten wir eine for(){...}Endlosschleife. Jede Iteration, erhöhen wir ++$mmultiplizieren , dass durch $n, und convertdas auf eine binäre Zeichenfolge, gespeichert in $b. Dann ist ifdiese Zeichenfolge regex -likealle Zeichenfolgen $a, die wir ausgeben $mund exit.

Perl 6 , 66 Bytes

->\n{first {(n*$_).base(2)~~/@(grep(n%%*,2..^n)».base(2))/},^∞}

Regex-basiert.

Super langsam, weil es die Faktoren von n brachial erzwingt bei jeder Regex-Match-Position jeder Zahl, die ausprobiert wird, erneut brutal .

Das einmalige Berechnen der Faktoren verbessert die Leistung, macht sie jedoch zu 72 Byte:

->\n{my @f=grep(n%%*,2..^n)».base(2);first {(n*$_).base(2)~~/@f/},^∞}