Najmniejszy mnożnik, który odsłania czynnik semiprime

16

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

przykład

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
Arnauld
źródło
Hmm,
wyczuwam
@ETHproductions Hmm, naprawdę? Szczerze mówiąc, mają być całkowicie niezwiązani.
Arnauld
Są one głównie podobne, ponieważ musisz sprawdzić każdy ciągły podciąg dla określonej właściwości. Poza tym naprawdę są dość niezwiązani.
ETHprodukcje
„i prawdopodobnie zachęcony” - przepraszam. Nie dbamy o szybkość naszego kodu.
John Dvorak
@JanDvorak Wystarczająco fair. Oddalony.
Arnauld

Odpowiedzi:

6

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.
isaacg
źródło
6

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!

Okx
źródło
¹Ñ¦¨båOpowinien działać zamiast sprawdzać każdy podciąg.
Riley
@Riley dzięki za wykrycie tego!
Okx
2
Można zapisać kolejny bajt zastąpienie ¼i ¾z N.
Emigna
@Emigna Nie wiedziałem o tej sztuczce, dzięki!
Okx
4

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.

ETHprodukcje
źródło
Nie jestem pewien, czy naprawdę istnieje konsensus w tej sprawie (jesteśmy w momencie dodawania + 6 / -2 ), ale jeśli o mnie chodzi, pierwszy format wejściowy jest w porządku.
Arnauld
3

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

Mitchell Spector
źródło
2

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.

ThreeFx
źródło
2

Mathematica, 83 bajty

1//.x_/;FreeQ[Fold[#+##&]/@Subsequences@IntegerDigits[x#,2],d_/;1<d<#&&d∣#]:>x+1&
Martin Ender
źródło
2

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.


źródło
1

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.

AdmBorkBork
źródło
0

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/},^∞}
smls
źródło