El multiplicador más pequeño que revela un factor de semiprime

16

Dado un semiprime N , encuentre el número entero positivo más pequeño m tal que la representación binaria de uno de los dos factores de N se pueda encontrar en la representación binaria de N * m .

Ejemplo

Consideremos el semiprime N = 9799 .

Intentamos diferentes valores de m , comenzando en 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

Nos detenemos aquí porque la representación binaria del último producto contiene 101001cuál es la representación binaria de 41 , uno de los dos factores de 9799 (el otro es 239 ).

ejemplo

Entonces la respuesta sería 11 .

Reglas y notas

  • Intentar incluso valores de m no tiene sentido. Se mostraron en el ejemplo anterior en aras de la integridad.
  • Su programa debe admitir cualquier N para el que N * m esté dentro de las capacidades informáticas de su idioma.
  • Se le permite factorizar N antemano en lugar de tratar cada posible subcadena de la representación binaria de N * m para ver si resulta ser un factor de N .
  • Como lo demuestra MitchellSpector , m siempre existe.
  • Este es el código de golf, por lo que gana la respuesta más corta en bytes. Las lagunas estándar están prohibidas.

Casos de prueba

La primera columna es la entrada. La segunda columna es la salida 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
code-golf primes binary Arnauld
fuente
Hmm, huelo un algoritmo similar a los que usamos en tu desafío de secuencia de Blackjack ...
ETHproductions
@ETHproductions Hmm, ¿en serio? Honestamente, se supone que no tienen ninguna relación.
Arnauld
Bueno, son principalmente similares en que necesita verificar cada subcadena contigua para una propiedad específica. Aparte de eso, realmente no están relacionados.
ETHproductions
"y probablemente animado" - Lo siento. No nos importa la velocidad de nuestro código.
John Dvorak
@ JanDvorak Bastante justo. Remoto.
Arnauld

Respuestas:

6

Pyth, 13 bytes

ff}.BY.B*TQPQ

Demostración

Explicación:

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
fuente
6

05AB1E , 18 16 15 bytes

-2 bytes gracias a Riley!

-1 byte gracias a Emigna!

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

Explicación:

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

Pruébalo en línea!

Okx
fuente
¹Ñ¦¨båOdebería funcionar en lugar de verificar cada subcadena.
Riley
@Riley gracias por ver eso!
Okx
2
Puede guardar otro byte reemplazando ¼y ¾con N.
Emigna
@Emigna No sabía sobre ese truco, ¡gracias!
Okx
4

JavaScript (ES6), 96 95 80 bytes

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)

Una función que devuelve una función recursiva que usa una función recursiva que usa una función recursiva. Realmente estoy empezando a preguntarme si la .toString(2)ruta sería más corta ...

Asignar a un ejemplo variables f=n=>...y llamada con un par extra de parens, f(9)(). Si eso no está permitido (la meta publicación está en + 6 / -2), puede usar esta versión de 83 bytes con invocación estándar:

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)

Ambas versiones funcionan para todos menos los últimos tres casos de prueba. También puede probar estos casos de prueba cambiando x>>1a (x-x%2)/2.

ETHproducciones
fuente
No estoy seguro de si hay realmente un consenso al respecto (estamos en + 6 / -2 en el momento de la publicación), pero en lo que a mí respecta, el primer formato de entrada está bien.
Arnauld
3

Bash + Unix utilities, 85 84 bytes

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

Pruébalo en línea!

También señalaré que m siempre existe para cualquier semiprime n. Este es el por qué:

Escriba n = pq, donde p y q son primos y p <= q.

Sea b el número de dígitos en la representación binaria de n-1. Entonces, para cualquier k entre 0 y n-1 inclusive, p * (2 ^ b) + k en binario consiste en la representación binaria de p seguida de b bits adicionales que representan k.

Entonces, los números p * (2 ^ b) + k para 0 <= k <= n-1, cuando se escriben en binario, todos comienzan con la representación binaria de p. Pero estos son n números consecutivos, por lo que uno de ellos debe ser un múltiplo de n.

Se deduce que tenemos un mn múltiple de n cuya representación binaria comienza con la representación binaria de p.

En base a esto, se puede llegar a un límite superior para m de 2 sqrt (n). (Probablemente se pueda obtener un límite superior mucho más ajustado que este).

Mitchell Spector
fuente
2

Haskell, 161 bytes

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

Verificación sencilla. Factoriza primero, luego busca linealmente comenzando en 1 y toma el mínimo del valor para ambos factores.

Toma unos segundos para el último caso de prueba ( 1468255967), ghciinforma(15.34 secs, 18,610,214,160 bytes) en mi computadora portátil.

ThreeFx
fuente
2

Mathematica, 83 bytes

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

Brachylog (2), 14 bytes

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

Pruébalo en línea!

Hay más de una forma de escribir esto en 14 bytes en Brachylog, por lo que elegí el más eficiente. Como es común para los envíos de Brachylog, este es un envío de función; su entrada es el semiprime, su salida es el multiplicador.

Explicación

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

El orden de evaluación de Prolog y Brachylog se establece mediante la primera restricción que no puede deducirse inmediatamente de la entrada. En este programa, eso es una restricción en el resultado de una multiplicación, por lo que el intérprete tratará de mantener los operandos de la multiplicación lo más cerca posible de 0. Conocemos uno de los operandos, y el otro es la salida, por lo que encontramos la salida más pequeña que podemos, que es exactamente lo que queremos.


fuente
1

PowerShell , 136 bytes

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

Pruébalo en línea!

Muy extenso debido a cómo funciona la conversión a binario en PowerShell. : - /

Toma de entrada $n, bucles a través 2de $n-1y saca los factores !($n%$_). Envía esos en un bucle |%{...}y converts cada uno de ellos a una 2cadena binaria (base ). Almacena esas cadenas binarias en$a .

Luego entramos en un for(){...}bucle infinito . Cada iteración, incrementamos ++$m, multiplicamos eso por $n, y converteso a una cadena binaria, almacenada en $b. Entonces, ifesa cadena es regex -likecualquier cadena en $a, sacamos $my exit.

AdmBorkBork
fuente
0

Perl 6 , 66 bytes

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

Basado en expresiones regulares.

Súper lento, porque fuerza bruta los factores de n nuevamente en cada posición de coincidencia de expresiones regulares de cada número que se intenta.

Calcular los factores solo una vez mejora el rendimiento, pero lo convierte en 72 bytes:

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