Dengan semiprime N , temukan bilangan bulat positif terkecil m sehingga representasi biner dari salah satu dari dua faktor N dapat ditemukan dalam representasi biner N * m .

Contoh

Mari kita pertimbangkan semiprime N = 9799 .

Kami mencoba berbagai nilai m , mulai dari 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

Kami berhenti di sini karena representasi biner dari produk terakhir berisi 101001yang merupakan representasi biner dari 41 , salah satu dari dua faktor 9799 (yang lain adalah 239 ).

Jadi jawabannya adalah 11 .

Aturan dan catatan

• Mencoba bahkan nilai-nilai m adalah sia-sia. Mereka ditunjukkan dalam contoh di atas demi kelengkapan.
• Program Anda harus mendukung N apa pun yang N * m berada dalam kemampuan komputasi bahasa Anda.
• Anda diperbolehkan untuk pd N terlebih dahulu daripada mencoba setiap substring yang mungkin dari representasi biner dari N * m untuk melihat jika ternyata menjadi faktor N .
• Sebagaimana dibuktikan oleh MitchellSpector , m selalu ada.
• Ini adalah kode-golf, jadi jawaban tersingkat dalam byte menang. Celah standar dilarang.

Uji kasus

Kolom pertama adalah input. Kolom kedua adalah output yang diharapkan.

         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 byte

ff}.BY.B*TQPQ

Demonstrasi

Penjelasan:

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 byte

-2 byte terima kasih kepada Riley!

-1 byte terima kasih kepada Emigna!

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

Penjelasan:

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

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

Fungsi yang mengembalikan fungsi rekursif yang menggunakan fungsi rekursif yang menggunakan fungsi rekursif. Saya benar-benar mulai bertanya-tanya apakah .toString(2)rute akan lebih pendek ...

Tetapkan ke variabel mis. f=n=>...Dan panggil dengan sepasang parens ekstra f(9)(),. Jika itu tidak diizinkan ( pos meta berada di + 6 / -2), Anda dapat menggunakan versi 83 byte ini dengan doa standar:

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)

Kedua versi berfungsi untuk semua kecuali tiga kasus uji terakhir. Anda dapat mencoba kasus uji ini juga dengan mengubah x>>1ke (x-x%2)/2.

Utilitas Bash + Unix, 85 84 byte

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

Cobalah online!

Saya akan tunjukkan juga bahwa m selalu ada untuk semiprime n. Inilah alasannya:

Tulis n = pq, di mana p dan q adalah prima dan p <= q.

Biarkan b jumlah digit dalam representasi biner dari n-1. Kemudian, untuk setiap k antara 0 dan n-1 inklusif, p * (2 ^ b) + k dalam biner terdiri dari representasi biner dari p diikuti oleh b bit tambahan yang mewakili k.

Jadi angka p * (2 ^ b) + k untuk 0 <= k <= n-1, ketika ditulis dalam biner, semua dimulai dengan representasi biner dari p. Tetapi ini adalah n angka berurutan, jadi salah satunya harus merupakan kelipatan dari n.

Ini mengikuti bahwa kita memiliki beberapa mn dari n yang representasi binernya dimulai dengan representasi biner dari p.

Berdasarkan ini, seseorang dapat datang dengan batas atas untuk m dari 2 sqrt (n). (Seseorang mungkin bisa mendapatkan batas atas yang lebih ketat dari ini.)

Haskell, 161 byte

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

Pemeriksaan langsung. Faktor pertama, kemudian cari linear mulai dari 1 dan ambil nilai minimum untuk kedua faktor.

Butuh beberapa detik untuk testcase terakhir ( 1468255967), ghcilapor (15.34 secs, 18,610,214,160 bytes)di laptop saya.

Mathematica, 83 byte

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

Brachylog (2), 14 byte

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

Cobalah online!

Ada lebih dari satu cara untuk menulis ini dalam 14 byte di Brachylog, jadi saya mencari yang paling efisien. Seperti yang umum untuk pengiriman Brachylog, ini adalah pengiriman fungsi; inputnya adalah semiprime, outputnya adalah pengali.

Penjelasan

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

Urutan evaluasi Prolog dan Brachylog diatur oleh kendala pertama yang tidak dapat langsung disimpulkan dari input. Dalam program ini, itu adalah kendala pada hasil perkalian, sehingga penerjemah akan bertujuan untuk menjaga operan perkalian sedekat mungkin dengan 0. Kami tahu salah satu operan, dan yang lainnya adalah output, jadi kami menemukan output terkecil yang kami bisa, yang persis apa yang kami inginkan.

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}}

Cobalah online!

Sangat panjang karena cara kerja konversi-ke-biner di PowerShell. : - /

Mengambil input $n, loop melalui 2ke$n-1 dan tarikan keluar faktor !($n%$_). Mengirimkannya ke dalam loop |%{...}dan converts masing-masing ke 2string biner (basis ). Menyimpan string biner itu ke dalam $a.

Lalu kita memasuki for(){...}loop tak terbatas . Setiap iterasi, kami menambah ++$m, mengalikannya dengan $n, dan convertitu ke string biner, disimpan ke dalam $b. Kemudian, ifstring itu adalah regex -likesemua string $a, kita output $mdanexit .

Perl 6 , 66 byte

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

Berbasis Regex.

Super lambat, karena kasar memaksa faktor n lagi di setiap posisi pertandingan regex dari setiap nomor yang dicoba.

Menghitung faktor hanya sekali, meningkatkan kinerja tetapi membuatnya 72 byte:

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