31
\$\begingroup\$

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 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
\$\endgroup\$
  • \$\begingroup\$ A vector does not have a dimension, a vector space does. \$\endgroup\$ – Jonathan Frech Feb 22 '18 at 22:47
  • 5
    \$\begingroup\$ @JonathanFrech I think it's a little bit pedantic, but I've made the change. \$\endgroup\$ – Sriotchilism O'Zaic Feb 22 '18 at 22:49
  • \$\begingroup\$ "Natural numbers" is generally understood to contain 0, which isn't represented in your system. And these aren't vectors. A vector space is over a field, and this is over a ring, which would make this a module. And it isn't a separate space from the integers, it's the same space with a different representation. \$\endgroup\$ – Acccumulation Feb 22 '18 at 23:51
  • 6
    \$\begingroup\$ @Acccumulation "Natural numbers" is not a well defined term, depending on who you ask it may or may not contain zero. You are correct that the "scalar multiplication" in my question forms a G-set with a monoid rather than a group, but that was simplified for the purposes of making the question palatable. I'm not sure what to make of your last comment, sure it has the same cardinality as the integers, but the action is really what defines a space not it's size. Perhaps you mean something more specific that I am missing. If so I'd be happy to continue this discussion (in chat might be best). \$\endgroup\$ – Sriotchilism O'Zaic Feb 23 '18 at 0:24
  • 2
    \$\begingroup\$ Another terminology nit-pick: Vector spaces are generally requred to have scalar multiplication from a field, so just using integers is not enough. That's because we want parallel vectors to be multiples of one another, not just have some multiple in common. For instance, $4$ and $8$ are parallel "vectors" in this space (they are both of the form (a, 0, 0,...)), but neither is a scalar multiple (i.e. an integer power) of the other. There aren't really many other terms you could use, though, that would be known to people in general. "Free module over the integers" is the best I can do. \$\endgroup\$ – Arthur Feb 23 '18 at 12:06

10 Answers 10

4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I think it's better to explicitly specify that the additional flag -D=F(v,V,e)for(;v%p<1;V+=e)v/=p; (32 bytes) is used (so 99+32=131); otherwise the code alone makes little sense. \$\endgroup\$ – Bubbler Feb 23 '18 at 0:49
3
\$\begingroup\$

Jelly, 12 11 bytes

ÆEz0_2/€P€S

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ p=t=2 instead of p=2;t=0 since t.real is ignored anyway (TIO). \$\endgroup\$ – Bubbler Feb 24 '18 at 8:19
  • \$\begingroup\$ @Bubbler Nice one, adding! \$\endgroup\$ – xnor Feb 24 '18 at 8:22
2
\$\begingroup\$

Wolfram Language (Mathematica), 55 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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 &&
}
\$\endgroup\$
1
\$\begingroup\$

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 
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Isn't p going to test non-prime values like 9? \$\endgroup\$ – xnor Feb 23 '18 at 1:53
  • \$\begingroup\$ Oops, I'll fix it soon. \$\endgroup\$ – Bubbler Feb 23 '18 at 2:06
  • 3
    \$\begingroup\$ You can replace return with print, and you can also save the indentation spaces if you write as a program instead of a function. \$\endgroup\$ – mathmandan Feb 23 '18 at 16:54
  • \$\begingroup\$ @mathmandan Thanks for the info. Looks useful for my other Py2 submissions, not sure for Py3 though (it takes extra eval() unless the function input itself is a string). \$\endgroup\$ – Bubbler Feb 24 '18 at 7:49
1
\$\begingroup\$

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].

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.