Finden Sie das Skalarprodukt von Rationals

31

Ich war zum Abendessen bei einem Freund und sie schlugen die Idee eines "Prime-Factor-Vector-Space" vor. In diesem Raum werden die positiven ganzen Zahlen als ein Vektor ausgedrückt, so dass das n- te Element im Vektor die Häufigkeit ist, mit der die n- te Primzahl die Zahl teilt. (Beachten Sie, dass dies bedeutet, dass unsere Vektoren eine unendliche Anzahl von Begriffen haben.) Zum Beispiel 20 ist

2 0 1 0 0 0 ...

Weil seine Primfaktorisierung 2 * 2 * 5 ist .

Da die Primfaktorisierung eindeutig ist, entspricht jede Zahl einem Vektor.

Wir können Vektoren hinzufügen, indem wir ihre Einträge paarweise hinzufügen. Dies entspricht dem Multiplizieren der ihnen zugeordneten Zahlen. Wir können auch eine Skalarmultiplikation durchführen, die einer Potenzierung der zugehörigen Zahl entspricht.

Das Problem ist, dass dieser Raum kein Vektorraum ist, weil es keine Inversen gibt. Wenn wir die Inversen addieren und den Vektorraum schließen, haben wir jetzt die Möglichkeit, jede positive rationale Zahl als Vektor auszudrücken. Wenn wir die Tatsache beibehalten, dass die Vektoraddition eine Multiplikation darstellt. Dann ist die Umkehrung einer natürlichen Zahl ihre Umkehrung.

Zum Beispiel hatte die Zahl 20 den Vektor

2 0 1 0 0 0 ...

Der Bruch 1/20 ist also umgekehrt

-2 0 -1 0 0 0 ...

Wenn wir den mit einem Bruch wie 14/15 assoziierten Vektor finden wollten, würden wir 14 finden

1 0 0 1 0 0 ...

und 1/15

0 -1 -1 0 0 0 ...

und multiplizieren Sie sie durch Vektoraddition

1 -1 -1 1 0 0 ...

Jetzt, da wir einen Vektorraum haben, können wir ihn modifizieren, um einen inneren Produktraum zu bilden, indem wir ihm ein inneres Produkt geben. Dazu stehlen wir das innere Produkt, dass Vektorräume klassisch gegeben sind. Das innere Produkt zweier Vektoren ist definiert als die Summe der paarweisen Multiplikation ihrer Terme. Zum Beispiel würde 20 · 14/15 wie folgt berechnet

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

Als weiteres Beispiel das Produkt 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

Ihre Aufgabe ist es, ein Programm zu implementieren, das dieses Skalarprodukt ausführt. Es sollten zwei positive rationale Zahlen über ein Paar positiver Ganzzahlen (Zähler und Nenner) oder einen rationalen Typ (Gleitkommazahlen sind nicht zulässig, da sie Probleme mit der Genauigkeit und Teilbarkeit verursachen) und eine ganze Zahl ausgegeben werden, die das Skalarprodukt der beiden darstellt Eingänge.

Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Testfälle

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
code-golf math number-theory linear-algebra factoring Weizen-Assistent
quelle
Ein Vektor hat keine Dimension, ein Vektorraum schon.
Jonathan Frech
5
@ JonathanFrech Ich denke, es ist ein bisschen umständlich, aber ich habe die Änderung vorgenommen.
Weizen-Assistent
Unter "natürlichen Zahlen" versteht man allgemein eine 0, die in Ihrem System nicht vorhanden ist. Und das sind keine Vektoren. Ein Vektorraum ist über einem Feld und dies ist über einem Ring, was dies zu einem Modul machen würde. Und es ist kein separater Raum von den ganzen Zahlen, es ist der gleiche Raum mit einer anderen Darstellung.
Akkumulation
6
@Akkumulation "Natürliche Zahlen" ist kein genau definierter Begriff, abhängig davon, wen Sie fragen, ob er Null enthält oder nicht. Sie haben Recht, dass die "Skalarmultiplikation" in meiner Frage eine G-Menge mit einem Monoid anstelle einer Gruppe bildet, dies wurde jedoch vereinfacht, um die Frage schmackhaft zu machen. Ich bin mir nicht sicher, was ich aus Ihrem letzten Kommentar machen soll, sicher, dass er die gleiche Kardinalität wie die ganzen Zahlen hat, aber die Aktion ist wirklich das, was einen Raum definiert, nicht seine Größe. Vielleicht meinen Sie etwas Konkretes, das mir fehlt. Wenn ja, würde ich diese Diskussion gerne fortsetzen (am besten im Chat).
Wheat Wizard
2
Eine andere Terminologie: Vektorräume müssen im Allgemeinen skalar multipliziert werden, sodass die Verwendung von ganzen Zahlen nicht ausreicht. Das liegt daran, dass parallele Vektoren ein Vielfaches voneinander sein sollen und nicht nur ein Vielfaches gemeinsam haben sollen. Zum Beispiel sind $ 4 $ und $ 8 $ parallele "Vektoren" in diesem Raum (sie haben beide die Form (a, 0, 0, ...)), aber keines ist ein skalares Vielfaches (dh eine ganzzahlige Potenz) von andere. Es gibt jedoch nicht wirklich viele andere Begriffe, die den Menschen allgemein bekannt sind. "Freies Modul über die ganzen Zahlen" ist das Beste, was ich tun kann.
Arthur

Antworten:

4

MATL , 12 Bytes

YF2:&Y)dwd*s

Die Eingabe ist ein Array [num1 den1 num2 den2].

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Betrachten Sie die Beispieleingabe [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
quelle
4

C (gcc) , 99 + 32 = 131 Bytes

  • Verwenden eines Compiler-Flags, das 32 Byte erfordert -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;}

Probieren Sie es online!

Jonathan Frech
quelle
Ich denke, es ist besser, explizit anzugeben, dass das zusätzliche Flag -D=F(v,V,e)for(;v%p<1;V+=e)v/=p;(32 Byte) verwendet wird (also 99 + 32 = 131); ansonsten macht der code alleine wenig sinn.
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

Probieren Sie es online!

Nimmt Eingaben wie [num1, num2, den1, den2]. Verwendet eine komplexe Zahl r, um die Einträge für Primzahlen pfür die beiden Rationen zu speichern und (r*r).imag/2ihr Produkt r.real*r.imaginnerhalb der Gesamtsumme zu extrahieren t. Addieren 1j**ifür i=0,1,2,3bewirkt jede Kombination des Inkrementierens oder Dekrementierens des Real- oder Imaginärteils für die vier eingegebenen Zahlen.

Bubbler speicherte 2 Bytes, die die Anfangswerte kombinierten p=t=2.

xnor
quelle
1
p=t=2statt p=2;t=0da t.realwird sowieso ignoriert ( TIO ).
Bubbler
@Bubbler Netter, fügte hinzu!
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)

Probieren Sie es online!

Übergeben Sie die Zahlen als Array von [Num1, Den1, Num2, Den2].

Vielen Dank für Arnauld, dass er das Fehlen F=ohne zusätzliche Bytes behoben hat und 2 weitere Bytes weniger.

Erklärung & ungolfed

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
quelle
1

J , 19 Bytes

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

Probieren Sie es online!

Erläuterung:

Als dyadisches Verb stehen die Argumente sowohl auf der linken als auch auf der rechten Seite

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

Stax , 11 Bytes

ä÷ß½♂←√:=Ü]

Führen Sie es aus und debuggen Sie es

Dies ist die entsprechende ASCII-Darstellung desselben Programms.

{|nmMFE-~-,*+

Grundsätzlich werden die Exponenten der Primfaktorisierung für jeden Teil ermittelt. Es wird die Differenz jedes Paares, dann des Produkts und schließlich die Summe aller Ergebnisse berechnet.

rekursiv
quelle
1

Python 2 , 133 127 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

Probieren Sie es online!

Die Schleifenbedingung wurde aus xnors Vorlage gestohlen .

Vielen Dank für den Rat von @mathmandan, die Funktion in ein Programm umzuwandeln (Ja, es hat tatsächlich einige Bytes gespart).

Veraltete, falsche Lösung (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
quelle
Wird man keine pNicht-Primzahlen wie 9 testen?
Xnor
Ups, ich werde es bald beheben.
Bubbler
3
Sie können ersetzen returnmit print, und Sie können auch die Vertiefung Räume sparen , wenn Sie als ein Programm statt einer Funktion schreiben.
Mathmandan
@mathmandan Danke für die Info. Sieht für meine anderen Py2-Einsendungen nützlich aus, obwohl ich nicht sicher bin, ob es sich bei Py3 um eine zusätzliche eval()Eingabe handelt (es sei denn, die Funktionseingabe selbst ist eine Zeichenfolge).
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

Probieren Sie es online! Beispiel für die Verwendung für 20 · 14/15: (2%) [20,1,14,15].

Laikoni
quelle