Biorąc pod uwagę półpierwszą N , znajdź najmniejszą dodatnią liczbę całkowitą m, tak że reprezentacja binarna jednego z dwóch czynników N znajduje się w reprezentacji binarnej N * m .

Przykład

Rozważmy semiprime N = 9799 .

Próbujemy różnych wartości m , zaczynając od 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

Zatrzymujemy się tutaj, ponieważ binarna reprezentacja ostatniego produktu zawiera 101001binarną reprezentację 41 , jeden z dwóch czynników 9799 (drugi to 239 ).

Tak więc odpowiedź brzmiałaby 11 .

Zasady i notatki

• Próba parzystych wartości m jest bezcelowa. Zostały one pokazane w powyższym przykładzie ze względu na kompletność.
• Twój program musi obsługiwać każdy N, dla którego N * m mieści się w zakresie możliwości obliczeniowych twojego języka.
• Są dozwolone na czynniki N wcześniej zamiast próbować każdą możliwą podciąg z binarnej reprezentacji n * m , aby zobaczyć, jeśli okaże się, że współczynnik N .
• Jak udowodnił MitchellSpector , m zawsze istnieje.
• To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach. Standardowe luki są zabronione.

Przypadki testowe

Pierwsza kolumna to dane wejściowe. Druga kolumna to oczekiwany wynik.

         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 bajtów

ff}.BY.B*TQPQ

Demonstracja

Wyjaśnienie:

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 bajtów

-2 bajty dzięki Riley!

-1 bajt dzięki Emignie!

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

Wyjaśnienie:

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

Wypróbuj online!

JavaScript (ES6), 96 95 80 bajtów

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)

Funkcja, która zwraca funkcję rekurencyjną, która wykorzystuje funkcję rekurencyjną, która korzysta z funkcji rekurencyjnej. Naprawdę zaczynam się zastanawiać, czy .toString(2)trasa byłaby krótsza ...

Przypisanie do zmiennej np f=n=>...i rozmowy z dodatkową parą parens, f(9)(). Jeśli nie jest to dozwolone ( meta post ma wartość + 6 / -2), możesz użyć tej 83-bajtowej wersji ze standardowym wywołaniem:

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)

Obie wersje działają dla wszystkich oprócz trzech ostatnich przypadków testowych. Możesz także wypróbować te przypadki testowe, zmieniając x>>1na (x-x%2)/2.

Narzędzia Bash + Unix, 85 84 bajtów

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

Wypróbuj online!

Zwrócę również uwagę, że m zawsze istnieje dla każdego semiprime n. Dlatego:

Napisz n = pq, gdzie p i q są liczbami pierwszymi, a p <= q.

Niech b liczba cyfr w reprezentacji binarnej n-1. Następnie, dla dowolnego k od 0 do n-1 włącznie, p * (2 ^ b) + k binarnie składa się z binarnej reprezentacji p, po której następuje b dodatkowych bitów reprezentujących k.

Tak więc liczby p * (2 ^ b) + k dla 0 <= k <= n-1, gdy są zapisywane binarnie, wszystkie zaczynają się od binarnej reprezentacji p. Ale to n kolejnych liczb, więc jedna z nich musi być wielokrotnością n.

Wynika z tego, że mamy wielokrotny mn n, którego reprezentacja binarna zaczyna się od reprezentacji binarnej p.

Na tej podstawie można wyznaczyć górną granicę dla m 2 sqrt (n). (Prawdopodobnie można uzyskać znacznie ściślejszą górną granicę).

Haskell, 161 bajtów

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

Prosta kontrola. Najpierw czynnik, a następnie wyszukaj liniowo, zaczynając od 1 i weź minimum wartości dla obu czynników.

Ostatnia testcase ( 1468255967) zajmuje kilka sekund , ghciraporty (15.34 secs, 18,610,214,160 bytes)na moim laptopie.

Mathematica, 83 bajty

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

Brachylog (2), 14 bajtów

ḋḃᵐD∧?:.×ḃs∈D∧

Wypróbuj online!

Jest więcej niż jeden sposób na napisanie tego w 14 bajtach w Brachylog, więc wybrałem najbardziej wydajny. Jak to zwykle bywa z przesyłaniem Brachylog, jest to przesyłanie funkcji; jego wejście jest półpierwszym, jego wyjściem jest mnożnik.

Wyjaśnienie

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

Kolejność oceny Prologa i Brachyloga jest ustalana przez pierwsze ograniczenie, którego nie można od razu wywnioskować z danych wejściowych. W tym programie jest to ograniczenie wyniku mnożenia, więc interpreter będzie dążył do utrzymania argumentów mnożenia tak blisko 0, jak to możliwe. Znamy jeden z operandów, a drugi to wynik, więc znajdujemy najmniejsze wyjście, jakie możemy, dokładnie tego chcemy.

PowerShell , 136 bajtów

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

Wypróbuj online!

Bardzo długi ze względu na sposób konwersji do pliku binarnego w programie PowerShell. : - /

Trwa wejściowych $n, poprzez pętle 2do $n-1i wyciąga czynników !($n%$_). Wysyła je do pętli, |%{...}a convertkażdy z nich do ciągu binarnego (podstawowego 2). Przechowuje te ciągi binarne w $a.

Następnie wchodzimy w nieskończoną for(){...}pętlę. Każdą iterację zwiększamy ++$m, mnożymy to przez $ni convertprzez ciąg binarny, w którym są przechowywane $b. Następnie iften ciąg znaków jest wyrażeniem regularnym w -likedowolnym ciągu $a, wysyłamy $mi exit.

Perl 6 , 66 bajtów

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

Oparty na regeksie.

Super wolno, ponieważ brutalnie wymusza od nowa czynniki n przy każdej pozycji dopasowania wyrażenia regularnego każdej wypróbowanej liczby.

Obliczanie współczynników tylko raz, poprawia wydajność, ale czyni ją 72 bajtami:

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