Trouvez le produit scalaire de Rationals

31

J'étais chez un ami pour le dîner et ils ont suggéré l'idée d'un "espace vectoriel à facteur premier". Dans cet espace, les entiers positifs sont exprimés comme un vecteur de telle sorte que le n ème élément dans le vecteur soit le nombre de fois que le n e premier divise le nombre. (Notez que cela signifie que nos vecteurs ont un nombre infini de termes.) Par exemple, 20 est

2 0 1 0 0 0 ...

Parce que sa factorisation première est 2 * 2 * 5 .

Puisque la factorisation première est unique, chaque nombre correspond à un vecteur.

Nous pouvons ajouter des vecteurs en ajoutant par paire leurs entrées. Cela revient à multiplier les nombres auxquels ils sont associés. Nous pouvons également faire une multiplication scalaire, ce qui revient à élever le nombre associé à une puissance.

Le problème est que cet espace n'est pas en fait un espace vectoriel car il n'y a pas d'inverses. Si nous allons de l'avant et ajoutons les inverses et fermons l'espace vectoriel, nous avons maintenant un moyen d'exprimer chaque nombre rationnel positif comme un vecteur. Si l'on garde le fait que l'addition vectorielle représente la multiplication. L'inverse d'un nombre naturel est alors sa réciproque.

Par exemple, le nombre 20 avait le vecteur

2 0 1 0 0 0 ...

La fraction 1/20 est donc son inverse

-2 0 -1 0 0 0 ...

Si nous voulions trouver le vecteur associé à une fraction comme 14/15, nous trouverions 14

1 0 0 1 0 0 ...

et 1/15

0 -1 -1 0 0 0 ...

et les multiplier en effectuant l'addition de vecteurs

1 -1 -1 1 0 0 ...

Maintenant que nous avons un espace vectoriel, nous pouvons le modifier pour former un espace de produit intérieur en lui donnant un produit intérieur. Pour ce faire, nous volons le produit intérieur que les espaces vectoriels sont donnés de façon classique. Le produit intérieur de deux vecteurs est défini comme la somme de la multiplication par paire de leurs termes. Par exemple, 20 · 14/15 serait calculé comme suit

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

Comme autre exemple, le produit 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

Votre tâche consiste à implémenter un programme qui exécute ce produit scalaire. Il doit prendre deux nombres rationnels positifs via une paire d'entiers positifs (numérateur et dénominateur) ou un type rationnel (les flottants ne sont pas autorisés, car ils posent des problèmes de précision et de divisibilité) et doit générer un entier représentant le produit scalaire des deux. contributions.

Il s'agit de donc les réponses seront notées en octets avec moins d'octets mieux.

Cas de test

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
Assistant de blé
la source
Un vecteur n'a pas de dimension, un espace vectoriel en a.
Jonathan Frech
5
@JonathanFrech Je pense que c'est un peu pédant, mais j'ai fait le changement.
Wheat Wizard
Les "nombres naturels" sont généralement compris comme contenant 0, qui n'est pas représenté dans votre système. Et ce ne sont pas des vecteurs. Un espace vectoriel est sur un champ, et c'est sur un anneau, ce qui en ferait un module. Et ce n'est pas un espace séparé des entiers, c'est le même espace avec une représentation différente.
Accumulation
6
@Acccumulation "Nombres naturels" n'est pas un terme bien défini, selon qui vous le demandez peut ou non contenir zéro. Vous avez raison de dire que la «multiplication scalaire» dans ma question forme un ensemble G avec un monoïde plutôt qu'un groupe, mais cela a été simplifié afin de rendre la question agréable au goût. Je ne sais pas quoi faire de votre dernier commentaire, sûr qu'il a la même cardinalité que les entiers, mais l'action est vraiment ce qui définit un espace et non sa taille. Peut-être voulez-vous dire quelque chose de plus précis qui me manque. Si c'est le cas, je serais heureux de poursuivre cette discussion (dans le chat, c'est peut-être mieux)
Wheat Wizard
2
Une autre terminologie nit-pick: les espaces vectoriels sont généralement requis pour avoir une multiplication scalaire à partir d'un champ, donc il ne suffit pas d'utiliser des entiers. C'est parce que nous voulons que les vecteurs parallèles soient des multiples les uns des autres, pas seulement des multiples en commun. Par exemple, $ 4 $ et $ 8 $ sont des "vecteurs" parallèles dans cet espace (ils sont tous les deux de la forme (a, 0, 0, ...)), mais ni l'un ni l'autre n'est un multiple scalaire (c'est-à-dire une puissance entière) du autre. Il n'y a pas vraiment beaucoup d'autres termes que vous pourriez utiliser, cependant, qui seraient connus des gens en général. "Module gratuit sur les entiers" est le meilleur que je puisse faire.
Arthur

Réponses:

4

MATL , 12 octets

YF2:&Y)dwd*s

L'entrée est un tableau [num1 den1 num2 den2].

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Considérez l'exemple d'entrée [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
la source
4

C (gcc) , 99 + 32 = 131 octets

  • L' utilisation d' un indicateur de compilation nécessitant 32 octets, -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;}

Essayez-le en ligne!

Jonathan Frech
la source
Je pense qu'il vaut mieux spécifier explicitement que l'indicateur supplémentaire -D=F(v,V,e)for(;v%p<1;V+=e)v/=p;(32 octets) est utilisé (donc 99 + 32 = 131); sinon, le code à lui seul n'a pas de sens.
Bubbler
3

Python 2 , 110 octets

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

Essayez-le en ligne!

Prend l'entrée comme [num1, num2, den1, den2]. Utilise un nombre complexe rpour stocker les entrées de prime ppour les deux rationnels et (r*r).imag/2pour extraire leur produit r.real*r.imagdans la somme globale t. L'addition 1j**ide i=0,1,2,3fait chaque combinaison d'incrémentation ou de décrémentation de la partie réelle ou imaginaire pour les quatre nombres d'entrée.

Bubbler a enregistré 2 octets en combinant les valeurs initiales p=t=2.

Xnor
la source
1
p=t=2au lieu de p=2;t=0puisque t.realest de toute façon ignoré ( TIO ).
Bubbler
@Bubbler Nice one, ajoutant!
xnor
1

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

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)

Essayez-le en ligne!

Passez les nombres sous forme de tableau de [Num1, Den1, Num2, Den2].

Merci pour Arnauld d'avoir corrigé les disparus F=sans octets supplémentaires, et 2 octets de moins.

Explication & non 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
la source
1

J , 19 octets

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

Essayez-le en ligne!

Explication:

Un verbe dyadique, les arguments sont à la fois à gauche et à droite

         &(        ) - 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
la source
1

Stax , 11 octets

ä÷ß½♂←√:=Ü]

Exécuter et déboguer

La représentation ascii correspondante du même programme est la suivante.

{|nmMFE-~-,*+

Fondamentalement, il obtient les exposants de la factorisation principale pour chaque partie. Il prend la différence de chaque paire, puis le produit, et résume enfin tous les résultats.

récursif
la source
1

Python 2 , 133 127 octets

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

Essayez-le en ligne!

A volé la condition de boucle de la soumission de xnor .

Merci pour les conseils de @mathmandan de changer la fonction en programme (Oui, il a en effet économisé quelques octets).

Solution obsolète et incorrecte (124 octets):

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)
Barboteur
la source
Ne pva pas tester des valeurs non premières comme 9?
xnor
Oups, je vais le réparer bientôt.
Bubbler
3
Vous pouvez remplacer returnpar print, et vous pouvez également enregistrer les espaces d'indentation si vous écrivez en tant que programme au lieu d'une fonction.
mathmandan
@mathmandan Merci pour l'info. Semble utile pour mes autres soumissions Py2, mais pas sûr pour Py3 (cela prend plus, eval()sauf si l'entrée de fonction elle-même est une chaîne).
Bubbler le
1

Haskell , 153 octets

(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

Essayez-le en ligne! Exemple d' utilisation pour 20 · 14/15: (2%) [20,1,14,15].

Laikoni
la source