Find the dot product of Rationals

Question

I was at a friend's house for dinner and they suggested the idea of a "Prime-factor vector space". In this space the positive integers are expressed as a vector such that the nth element in the vector is the number of times the nth prime divides the number. (Note that this means that our vectors have an infinite number of terms.) For example 20 is

2 0 1 0 0 0 ...

Because its prime factorization is 2 * 2 * 5.

Since prime factorization is unique each number corresponds to one vector.

We can add vectors by pairwise adding their entries. This is the same as multiplying the numbers they are associated with. We can also do scalar multiplication, which is akin to raising the associated number to a power.

The problem is that this space is not in fact a vector space because there are no inverses. If we go ahead and add the inverses and close the vector space we now have a way of expressing every positive rational number as a vector. If we keep the fact that vector addition represents multiplication. Then the inverse of a natural number is its reciprocal.

For example the number 20 had the vector

2 0 1 0 0 0 ...

So the fraction 1/20 is its inverse

-2 0 -1 0 0 0 ...

If we wanted to find the vector associated with a fraction like 14/15 we would find 14

1 0 0 1 0 0 ...

and 1/15

0 -1 -1 0 0 0 ...

and multiply them by performing vector addition

1 -1 -1 1 0 0 ...

Now that we have a vector space we can modify it to form an inner product space by giving it an inner product. To do this we steal the inner product that vector spaces are given classically. The inner product of two vectors is defined as the sum of the pairwise multiplication of their terms. For example 20 · 14/15 would be calculated as follows

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

As another example the product 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

Your task is to implement a program that performs this dot product. It should take two positive rational numbers via either a pair of positive integers (numerator and denominator) or a rational type (floats are not allowed, because they cause problems with precision and divisibility) and should output a integer representing the dot product of the two inputs.

This is code-golf so answers will be scored in bytes with fewer bytes being better.

Test Cases

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

Answer 1

MATL, 12 bytes

YF2:&Y)dwd*s

Input is an array [num1 den1 num2 den2].

Try it online! Or verify all test cases.

Explanation

Consider example input [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

Answer 2

C (gcc), 99+32 = 131 bytes

• Using a compiler flag requiring 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;}

Try it online!

Answer 3

Jelly, 12 11 bytes

ÆEz0_2/€P€S

Try it online!

Answer 4

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

Try it online!

Takes input like [num1, num2, den1, den2]. Uses a complex number r to store the entries for prime p for the two rationals, and (r*r).imag/2 to extract their product r.real*r.imag within overall the sum t. Adding 1j**i for i=0,1,2,3 does each combination of incrementing or decrementing the real or imaginary part for the four input numbers.

Bubbler saved 2 bytes combining the initial values p=t=2.

Answer 5

Wolfram Language (Mathematica), 55 bytes

Dot@@PadRight[SparseArray[Rule@@@FactorInteger@#]&/@#]&

Try it online!

Answer 6

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

Try it online!

Stole the loop condition from xnor's submission.

Thanks for the advice by @mathmandan to change the function into a program (Yes, it indeed saved some bytes).

Obsolete, incorrect solution (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)

Answer 7

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)

Try it online!

Pass the numbers as an array of [Num1, Den1, Num2, Den2].

Thanks for Arnauld for fixing the missing F= with no extra bytes, and 2 more bytes less.

Explanation & 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 &&
}

Answer 8

J, 19 bytes

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

Try it online!

Explanation:

A dyadic verb, arguments are on both left hand and right hand side

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

Answer 9

Stax, 11 bytes

ä÷ß½♂←√:=Ü]

Run and debug it

The corresponding ascii representation of the same program is this.

{|nmMFE-~-,*+

Basically, it gets the prime factorization's exponents for each part. It takes the difference of each pair, then the product, and finally sums all the results.

Answer 10

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

Try it online! Example usage for 20 · 14/15: (2%) [20,1,14,15].