Encuentra el producto punto de Rationals

31

Estaba cenando en la casa de un amigo y me sugirieron la idea de un "espacio vectorial de factor primo". En este espacio los enteros positivos se expresan como un vector tal que el n -ésimo elemento en el vector es el número de veces que el n º divisiones principales del número. (Tenga en cuenta que esto significa que nuestros vectores tienen un número infinito de términos). Por ejemplo, 20 es

2 0 1 0 0 0 ...

Porque su factorización prima es 2 * 2 * 5 .

Como la factorización prima es única, cada número corresponde a un vector.

Podemos agregar vectores agregando sus entradas por pares. Esto es lo mismo que multiplicar los números con los que están asociados. También podemos hacer una multiplicación escalar, que es similar a elevar el número asociado a una potencia.

El problema es que este espacio no es, de hecho, un espacio vectorial porque no hay inversos. Si continuamos y sumamos los inversos y cerramos el espacio vectorial, ahora tenemos una forma de expresar cada número racional positivo como un vector. Si mantenemos el hecho de que la suma de vectores representa la multiplicación. Entonces el inverso de un número natural es su recíproco.

Por ejemplo, el número 20 tenía el vector

2 0 1 0 0 0 ...

Entonces la fracción 1/20 es inversa

-2 0 -1 0 0 0 ...

Si quisiéramos encontrar el vector asociado con una fracción como 14/15 , encontraríamos 14

1 0 0 1 0 0 ...

y 1/15

0 -1 -1 0 0 0 ...

y multiplíquelos realizando la suma vectorial

1 -1 -1 1 0 0 ...

Ahora que tenemos un espacio vectorial, podemos modificarlo para formar un espacio interno del producto dándole un producto interno. Para hacer esto, robamos el producto interno que los espacios vectoriales se dan clásicamente. El producto interno de dos vectores se define como la suma de la multiplicación por pares de sus términos. Por ejemplo 20 · 14/15 se calcularía de la siguiente manera

20    =  2  0  1  0  0  0 ...
14/15 =  1 -1 -1  1  0  0 ...
         2  0 -1  0  0  0 ...  -> 1

Como otro ejemplo, el producto 2/19 · 4/19

2/19 = 1 0 0 0 0 0 0 -1 0 0 0 ...
4/19 = 2 0 0 0 0 0 0 -1 0 0 0 ...
       2 0 0 0 0 0 0  1 0 0 0 ... -> 3

Su tarea es implementar un programa que realice este producto punto. Debe tomar dos números racionales positivos a través de un par de enteros positivos (numerador y denominador) o de un tipo racional (no se permiten los flotantes, porque causan problemas con la precisión y la divisibilidad) y debe generar un número entero que represente el producto de punto de los dos entradas

Este es el por lo que las respuestas se puntuarán en bytes, con menos bytes mejor.

Casos de prueba

4 · 4 = 4
8 · 8 = 9
10 · 10 = 2
12 · 12 = 5
4 · 1/4 = -4
20 · 14/15 = 1
2/19 · 4/19 = 3
Asistente de trigo
fuente
Un vector no tiene una dimensión, un espacio vectorial sí.
Jonathan Frech
55
@ JonathanFrech Creo que es un poco pedante, pero he hecho el cambio.
Wheat Wizard
Generalmente se entiende que "números naturales" contiene 0, que no está representado en su sistema. Y estos no son vectores. Un espacio vectorial está sobre un campo, y esto está sobre un anillo, lo que haría de este un módulo. Y no es un espacio separado de los enteros, es el mismo espacio con una representación diferente.
Acumulación
66
@Acumulación "Números naturales" no es un término bien definido, dependiendo de a quién le pregunte puede contener o no cero. Tiene razón en que la "multiplicación escalar" en mi pregunta forma un conjunto G con un monoide en lugar de un grupo, pero eso se simplificó con el fin de hacer que la pregunta sea aceptable. No estoy seguro de qué hacer con su último comentario, seguro de que tiene la misma cardinalidad que los enteros, pero la acción es realmente lo que define un espacio, no su tamaño. Quizás te refieres a algo más específico que me estoy perdiendo. Si es así, estaría feliz de continuar esta discusión (en el chat podría ser lo mejor).
Wheat Wizard
2
Otra terminología: los espacios vectoriales generalmente requieren una multiplicación escalar de un campo, por lo que el uso de enteros no es suficiente. Eso es porque queremos que los vectores paralelos sean múltiplos entre sí, no solo que tengan algunos múltiplos en común. Por ejemplo, $ 4 $ y $ 8 $ son "vectores" paralelos en este espacio (ambos tienen la forma (a, 0, 0, ...)), pero tampoco es un múltiplo escalar (es decir, una potencia entera) de otro. Sin embargo, no hay muchos otros términos que pueda usar, que las personas en general conozcan. "Módulo libre sobre enteros" es lo mejor que puedo hacer.
Arthur

Respuestas:

4

MATL , 12 bytes

YF2:&Y)dwd*s

La entrada es una matriz [num1 den1 num2 den2].

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

Considere la entrada de ejemplo [20 1 14 15].

YF      % Implicit input: array of 4 numbers. Exponents of prime factorization.
        % Gives a matrix, where each row corresponds to one of the numbers in
        % the input array. Each row may contain zeros for non-present factors
        % STACK: [2 0 1 0
                  0 0 0 0
                  1 0 0 1
                  0 1 1 0]
2:&Y)   % Push a submatrix with the first two rows, then a submatrix with the
        % other two rows
        % STACK: [2 0 1 0
                  0 0 0 0],
                 [1 0 0 1
                  0 1 1 0]
d       % Consecutive difference(s) along each column
        % STACK: [2 0 1 0
                  0 0 0 0],
                 [-1 1 -1 1]
wd      % Swap, and do the same for the other submatrix
        % STACK: [-1 1 -1 1]
                 [-2 0 -1 0]
*       % Element-wise product
        % STACK: [2 0 -1 0]
s       % Sum. Implicit display
        % STACK: 1
Luis Mendo
fuente
4

C (gcc) , 99 + 32 = 131 bytes

  • El uso de una bandera compilador que requiere 32 bytes, -D=F(v,V,e)for(;v%p<1;V+=e)v/=p;.
T,p,A,C;f(a,b,c,d){T=0;for(p=2;a+b+c+d>4;p++){A=C=0;F(a,A,1)F(b,A,~0)F(c,C,1)F(d,C,~0)T+=A*C;}a=T;}

Pruébalo en línea!

Jonathan Frech
fuente
Creo que es mejor especificar explícitamente que -D=F(v,V,e)for(;v%p<1;V+=e)v/=p;se usa la bandera adicional (32 bytes) (entonces 99 + 32 = 131); de lo contrario, el código solo tiene poco sentido.
Bubbler
3

Python 2 , 110 bytes

l=input()
p=t=2
while~-max(l):r=i=0;exec"while l[i]%p<1:l[i]/=p;r+=1j**i\ni+=1\n"*4;t+=r*r;p+=1
print t.imag/2

Pruébalo en línea!

Toma entrada como [num1, num2, den1, den2]. Utiliza un número complejo rpara almacenar las entradas de primo ppara los dos racionales, y (r*r).imag/2para extraer su producto r.real*r.imagdentro de la suma total t. Sumando 1j**ipara i=0,1,2,3cada combinación de aumentar o disminuir la parte real o imaginaria para los cuatro números de entrada.

Bubbler ahorró 2 bytes combinando los valores iniciales p=t=2.

xnor
fuente
1
p=t=2en lugar de p=2;t=0desde entonces t.realse ignora de todos modos ( TIO ).
Bubbler
@Bubbler ¡Bonito, añadiendo!
xnor
1

JavaScript (Node.js) , 104 ... 100 94 bytes

F=(A,i=2)=>A.some(x=>x>1)&&([a,b,c,d]=A.map(G=(x,j)=>x%i?0:1+G(A[j]/=i,j)),a-b)*(c-d)+F(A,i+1)

Pruébalo en línea!

Pase los números como una matriz de [Num1, Den1, Num2, Den2].

Gracias por Arnauld por arreglar lo que falta F=sin bytes adicionales, y 2 bytes más menos.

Explicación y sin golf

function F(A, i = 2) {                 // Main function, recursing from i = 2
 if (A.some(function(x) {              // If not all numbers became 1:
  return x > 1;
 })) {
  var B = A.map(G = function(x, j) {   // A recursion to calculate the multiplicity
   if (x % i)
    return 0;
   else
    return 1 + G(A[j] /= i, j);        // ...and strip off all powers of i
  });
  return (B[0] - B[1]) * (B[2] - B[3]) // Product at i
   + F(A, i + 1);                      // Proceed to next factor. All composite factors 
 }                                     // will be skipped effectively
 else 
  return 0;                            // Implied in the short-circuit &&
}
Shieru Asakoto
fuente
1

J , 19 bytes

1#.*/@,:&([:-/_&q:)

Pruébalo en línea!

Explicación:

Un verbo diádico, los argumentos están a la izquierda y a la derecha

         &(        ) - for both arguments (which are lists of 2 integers)
               _&q:  - decompose each number to a list of prime exponents
           [:-/      - and find the difference of these lists
       ,:            - laminate the resulting lists for both args (to have the same length)
   */@               - multiply them
1#.                  - add up 
Galen Ivanov
fuente
1

Stax , 11 bytes

ä÷ß½♂←√:=Ü]

Ejecutar y depurarlo

La representación ascii correspondiente del mismo programa es esta.

{|nmMFE-~-,*+

Básicamente, obtiene los exponentes de la factorización prima para cada parte. Toma la diferencia de cada par, luego el producto, y finalmente suma todos los resultados.

recursivo
fuente
1

Python 2 , 133127 bytes

a=input();s=0;p=2;P=lambda n,i=0:n%p and(n,i)or P(n/p,i+1)
while~-max(a):a,(w,x,y,z)=zip(*map(P,a));s+=(w-x)*(y-z);p+=1
print s

Pruébalo en línea!

Robó la condición del bucle de la sumisión de xnor .

Gracias por el consejo de @mathmandan para cambiar la función a un programa (Sí, de hecho, guardó algunos bytes).

Solución obsoleta, incorrecta (124 bytes):

lambda w,x,y,z:sum((P(w,p)-P(x,p))*(P(y,p)-P(z,p))for p in[2]+range(3,w+x+y+z,2))
P=lambda n,p,i=1:n%p and i or P(n/p,p,i+1)
Bubbler
fuente
¿No pva a probar valores no primos como 9?
xnor
Vaya, lo arreglaré pronto.
Bubbler
3
Puede reemplazar returncon print, y también puede guardar los espacios de sangría si escribe como un programa en lugar de una función.
Mathmandan
@mathmandan Gracias por la información. Parece útil para mis otras presentaciones de Py2, aunque no estoy seguro para Py3 (se necesita más a eval()menos que la entrada de la función sea una cadena).
Bubbler
1

Haskell , 153 bytes

(2%)
n%m|all(<2)m=0|(k,[a,b,c,d])<-unzip[(,)=<<div x.max 1.(n*)$until((>0).mod x.(n^))(+1)1-1|x<-m]=(a-b)*(c-d)+[i|i<-[n..],all((>0).rem i)[2..i-1]]!!1%k

Pruébalo en línea! Ejemplo de uso para 20 · 14/15: (2%) [20,1,14,15].

Laikoni
fuente