Codegolf — Наименьший Множитель, Показывающий Коэффициент Полупростого Числа.

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

Пример

Рассмотрим полупростые Н = 9799.

Мы пробуем разные значения м, начиная с 1:

 
          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
 
 

На этом мы останавливаемся, поскольку двоичное представление последнего произведения содержит 101001 which is the binary representation of 41, один из двух факторов 9799 (другой из них 239).

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

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

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

Тестовые случаи

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

#код-гольф #простые числа #двоичный код

Пиф, 13 байт

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

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

Объяснение:

05AB1E, 18 16 15 байт

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

-1 байт спасибо Эмигне!

Объяснение:

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

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

Функция, возвращающая рекурсивную функцию, использующую рекурсивную функцию, использующую рекурсивную функцию. Я действительно начинаю задаваться вопросом, может ли -like route would be shorter...

Присвойте переменной, например. if and call with an extra pair of parens, $b . Если это не разрешено ( мета-пост находится на уровне +6/-2), вы можете использовать эту 83-байтовую версию со стандартным вызовом:

Обе версии работают для всех тестовых случаев, кроме трех последних. Вы также можете попробовать эти тестовые примеры, изменив $n к ++$m .

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

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

Отмечу также, что 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). (Вероятно, можно получить гораздо более точную верхнюю границу, чем эта.)

Хаскель, 161 байт

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

Для последнего тестового примера требуется несколько секунд ( 2 ), convert отчеты |%{...} on my laptop.

Математика, 83 байта

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

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

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

Объяснение

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

PowerShell, 136 байт

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

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

Принимает ввод param($n)$a=2..($n-1)|?{!($n%$_)}|%{[convert]::ToString($_,2)};for(){$b=[convert]::toString(++$m*$n,2);if($a|?{$b-like"*$_*"}){$m;exit}} , loops through ḋḃᵐ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) to ḋḃᵐD∧?:.×ḃs∈D∧ and pulls out the factors 1//.x_/;FreeQ[Fold[#+##&]/@Subsequences@IntegerDigits[x#,2],d_/;1<d<#&&d∣#]:>x+1& . Отправляет их в цикл (15.34 secs, 18,610,214,160 bytes) and ghci преобразует каждый из них в двоичный (базовый 1468255967 ) string. Stores those binary strings into 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 .

Затем мы входим в бесконечность for((;;m++)){ dc -e2o$[$1*m]n|egrep -q $(dc "-e2o`factor $1`nBEPn")&&break;} echo $m loop. Each iteration, we increment (x-x%2)/2 , умножьте это на x>>1 , and 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) это в двоичную строку, хранящуюся в f(9)() . Then, f=n=>... эта строка является регулярным выражением .toString(2) any strings in 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) , мы выводим [ # 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 and [N¹*b¹Ñ¦¨båOiNq .

Перл 6, 66 байт

На основе регулярных выражений.

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

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