Dado um N semiprime , encontre o menor número inteiro positivo m, de modo que a representação binária de um dos dois fatores de N possa ser encontrada na representação binária de N * m .
Exemplo
Vamos considerar o semiprime N = 9799 .
Tentamos diferentes valores de m , começando em 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
Paramos aqui porque a representação binária do último produto contém 101001
qual é a representação binária de 41 , um dos dois fatores de 9799 (o outro sendo 239 ).
Então a resposta seria 11 .
Regras e notas
- Tentar valores iguais de m não faz sentido. Eles foram mostrados no exemplo acima por uma questão de integridade.
- Seu programa deve suportar qualquer N para o qual N * m esteja dentro dos recursos de computação do seu idioma.
- Você está autorizado a fatorar N antemão ao invés de tentar cada possível substring da representação binária de N * m para ver se ele acaba por ser um fator de N .
- Conforme comprovado pelo MitchellSpector , m sempre existe.
- Isso é código-golfe, então a resposta mais curta em bytes vence. As brechas padrão são proibidas.
Casos de teste
A primeira coluna é a entrada. A segunda coluna é a saída esperada.
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
Respostas:
Pitão, 13 bytes
Demonstração
Explicação:
fonte
05AB1E ,
181615 bytes-2 bytes graças a Riley!
-1 byte graças a Emigna!
Explicação:
Experimente online!
fonte
¹Ñ¦¨båO
deve funcionar em vez de verificar cada substring.¼
e¾
porN
.JavaScript (ES6),
969580 bytesUma função que retorna uma função recursiva que usa uma função recursiva que usa uma função recursiva. Estou realmente começando a me perguntar se a
.toString(2)
rota seria mais curta ...Atribua a uma variável, por exemplo,
f=n=>...
e chame com um par extra de parêntesesf(9)()
,. Se isso não for permitido (a meta postagem está em + 6 / -2), você pode usar esta versão de 83 bytes com invocação padrão:Ambas as versões funcionam para todos, exceto os três últimos casos de teste. Você também pode tentar esses casos de teste, alterando
x>>1
para(x-x%2)/2
.fonte
Utilitários Bash + Unix,
8584 bytesExperimente online!
Vou apontar também que m sempre existe para qualquer n semiprime. Aqui está o porquê:
Escreva n = pq, onde p e q são primos ep <= q.
Seja b o número de dígitos na representação binária de n-1. Então, para qualquer k entre 0 e n-1 inclusive, p * (2 ^ b) + k em binário consiste na representação binária de p seguida de b bits adicionais representando k.
Portanto, os números p * (2 ^ b) + k para 0 <= k <= n-1, quando escritos em binário, todos começam com a representação binária de p. Mas esses são n números consecutivos, portanto, um deles deve ser um múltiplo de n.
Segue-se que temos um mn múltiplo de n cuja representação binária começa com a representação binária de p.
Com base nisso, pode-se chegar a um limite superior para m de 2 sqrt (n). (Pode-se provavelmente obter um limite superior muito mais apertado do que isso.)
fonte
Haskell, 161 bytes
Verificação direta. Fatore primeiro, depois pesquise linearmente começando em 1 e use o mínimo do valor para os dois fatores.
Leva alguns segundos para o último testcase (
1468255967
),ghci
relata(15.34 secs, 18,610,214,160 bytes)
no meu laptop.fonte
Mathematica, 83 bytes
fonte
Braquilog (2), 14 bytes
Experimente online!
Há mais de uma maneira de escrever isso em 14 bytes no Brachylog, então eu fui o mais eficiente. Como é comum para envios de Brachylog, este é um envio de função; sua entrada é a semiprime, sua saída é o multiplicador.
Explicação
A ordem de avaliação de Prolog e Brachylog é definida pela primeira restrição que não pode ser deduzida imediatamente da entrada. Neste programa, isso é uma restrição ao resultado de uma multiplicação; portanto, o intérprete procurará manter os operandos da multiplicação o mais próximo possível de 0. Conhecemos um dos operandos e o outro é a saída; portanto, encontramos a menor saída possível, que é exatamente o que queremos.
fonte
PowerShell , 136 bytes
Experimente online!
Muito demorado devido ao funcionamento da conversão em binário no PowerShell. : - /
Recebe entrada
$n
, passa2
para$n-1
e retira os fatores!($n%$_)
. Envia aqueles para um loop|%{...}
econvert
s cada um deles para uma2
string binária (base ). Armazena essas cadeias binárias em$a
.Então entramos em um
for(){...}
loop infinito . Cada iteração, incrementamos++$m
, multiplica isso por$n
econvert
para uma string binária, armazenada em$b
. Então,if
essa string é regex em-like
qualquer string$a
, produzimos$m
eexit
.fonte
Perl 6 , 66 bytes
Baseado em Regex.
Super lento, porque força brutal os fatores de n novamente em cada posição de correspondência de expressão regular de cada número que é tentado.
O cálculo dos fatores apenas uma vez melhora o desempenho, mas aumenta 72 bytes:
fonte