Учитывая полупростую N найдите наименьшее натуральное число m, такое, что двоичное представление одного из двух факторов N можно найти в двоичном представлении N * m .

пример

Давайте рассмотрим полупростую N = 9799 .

Мы пробуем разные значения m , начиная с 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

Мы остановимся здесь, потому что двоичное представление последнего продукта содержит 101001двоичное представление 41 , один из двух факторов 9799 (другой является 239 ).

Таким образом, ответ будет 11 .

Правила и примечания

• Пытаясь даже значения m бессмысленно. Они были показаны в вышеприведенном примере для полноты картины.
• Ваша программа должна поддерживать любой N, для которого N * m соответствует вычислительным возможностям вашего языка.
• Вам разрешено заранее разложить N на множители, вместо того, чтобы пробовать каждую возможную подстроку двоичного представления N * m, чтобы увидеть, оказывается ли она фактором N .
• Как доказано MitchellSpector , m всегда существует.
• Это код-гольф, поэтому выигрывает самый короткий ответ в байтах. Стандартные лазейки запрещены.

Контрольные примеры

Первый столбец является входным. Второй столбец - ожидаемый результат.

         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 байт

ff}.BY.B*TQPQ

демонстрация

Объяснение:

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 байт

-2 байта благодаря Райли!

-1 байт благодаря Emigna!

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

Объяснение:

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

Попробуйте онлайн!

JavaScript (ES6), 96 95 80 байт

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)

Функция, которая возвращает рекурсивную функцию, которая использует рекурсивную функцию, которая использует рекурсивную функцию. Я действительно начинаю задаваться вопросом, будет ли .toString(2)маршрут короче ...

Присвоить переменной , например , f=n=>...и вызов с дополнительной парой скобок, f(9)(). Если это недопустимо ( метапост в + 6 / -2), вы можете использовать эту 83-байтовую версию со стандартным вызовом:

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)

Обе версии работают для всех, кроме трех последних тестовых случаев. Вы можете попробовать эти тестовые случаи , а также путем изменения x>>1к (x-x%2)/2.

Утилиты Bash + Unix, 85 84 байта

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

Попробуйте онлайн!

Я также укажу, что m всегда существует для любого полупростого n. Вот почему:

Напишите n = pq, где p и q простые и p <= q.

Пусть b количество цифр в двоичном представлении n-1. Тогда для любого k от 0 до n-1 включительно p * (2 ^ b) + k в двоичном коде состоит из двоичного представления p, за которым следует b дополнительных битов, представляющих k.

Таким образом, числа p * (2 ^ b) + k для 0 <= k <= n-1, когда они записаны в двоичном формате, все начинаются с двоичного представления p. Но это n последовательных чисел, поэтому одно из них должно быть кратным n.

Отсюда следует, что у нас есть кратное mn от n, двоичное представление которого начинается с двоичного представления p.

Исходя из этого, можно придумать верхнюю оценку для m 2 sqrt (n). (Вероятно, можно получить более жесткий верхний предел, чем этот.)

Haskell, 161 байт

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

Простая проверка. Сначала фактор, затем линейный поиск, начиная с 1, и возьмите минимум значения для обоих факторов.

Занимает несколько секунд для последнего теста ( 1468255967), ghciсообщает (15.34 secs, 18,610,214,160 bytes)на моем ноутбуке.

Mathematica, 83 байта

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

Брахилог (2), 14 байт

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

Попробуйте онлайн!

Существует более одного способа записать это в 14 байт в Brachylog, поэтому я выбрал наиболее эффективный. Как обычно для представлений Brachylog, это представление функции; его вход - полупростая, его выход - множитель.

объяснение

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

Порядок оценки Пролога и Брахилога устанавливается первым ограничением, которое не может быть немедленно выведено из входных данных. В этой программе это ограничение на результат умножения, поэтому интерпретатор будет стремиться к тому, чтобы операнды умножения были как можно ближе к 0. Мы знаем один из операндов, а другой - вывод, поэтому мы находим наименьший выход, который можем, и это именно то, что мы хотим.

PowerShell , 136 байт

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

Попробуйте онлайн!

Очень долго из-за того, как преобразование в двоичный код работает в PowerShell. : - /

Принимает входные $n, петли через 2к $n-1и вытаскивает факторы !($n%$_). Отправляет их в цикл |%{...}и convertпомещает каждый из них в двоичную (базовую 2) строку. Сохраняет эти двоичные строки в $a.

Затем мы входим в бесконечный for(){...}цикл. Каждую итерацию мы увеличиваем ++$m, умножаем на $nи convertна двоичную строку, сохраненную в $b. Затем, ifэта строка является регулярным выражением -likeлюбой строки $a, мы выводим $mи exit.

Perl 6 , 66 байт

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

Regex основе.

Очень медленный, потому что он грубо заставляет факторы n снова и снова в каждой позиции совпадения регулярных выражений каждого пробного числа.

Вычисление коэффициентов только один раз повышает производительность, но составляет 72 байта:

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