Temukan produk titik Rationals

31

Saya berada di rumah seorang teman untuk makan malam dan mereka menyarankan ide "ruang vektor faktor Utama". Dalam ruang ini bilangan bulat positif dinyatakan sebagai vektor sehingga elemen ke- n dalam vektor adalah berapa kali bilangan ke- n membagi angka tersebut. (Perhatikan bahwa ini berarti vektor kita memiliki jumlah syarat yang tak terbatas.) Misalnya 20 adalah

2 0 1 0 0 0 ...

Karena faktorisasi utamanya adalah 2 * 2 * 5 .

Karena faktorisasi prima adalah unik, setiap angka berhubungan dengan satu vektor.

Kami dapat menambahkan vektor dengan menambahkan entri secara berpasangan. Ini sama dengan mengalikan angka yang dikaitkan dengan mereka. Kita juga bisa melakukan perkalian skalar, yang mirip dengan menaikkan angka terkait ke suatu kekuatan.

Masalahnya adalah bahwa ruang ini sebenarnya bukan ruang vektor karena tidak ada invers. Jika kita teruskan dan menambahkan invers dan menutup ruang vektor, kita sekarang memiliki cara untuk mengekspresikan setiap bilangan rasional positif sebagai vektor. Jika kita menjaga fakta bahwa penambahan vektor mewakili perkalian. Maka kebalikan dari bilangan alami adalah kebalikannya.

Misalnya angka 20 memiliki vektor

2 0 1 0 0 0 ...

Jadi pecahan 1/20 adalah kebalikannya

-2 0 -1 0 0 0 ...

Jika kita ingin menemukan vektor yang terkait dengan fraksi seperti 14/15 kita akan menemukan 14

1 0 0 1 0 0 ...

dan 1/15

0 -1 -1 0 0 0 ...

dan gandakan dengan melakukan penambahan vektor

1 -1 -1 1 0 0 ...

Sekarang kita memiliki ruang vektor, kita dapat memodifikasinya untuk membentuk ruang produk dalam dengan memberikannya produk dalam. Untuk melakukan ini, kami mencuri produk dalam bahwa ruang vektor diberikan secara klasik. Produk dalam dari dua vektor didefinisikan sebagai jumlah dari perkalian berpasangan dari istilah mereka. Misalnya 20 · 14/15 akan dihitung sebagai berikut

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

Sebagai contoh lain produk 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

Tugas Anda adalah mengimplementasikan program yang menjalankan produk titik ini. Ini harus mengambil dua bilangan rasional positif melalui sepasang bilangan bulat positif (pembilang dan penyebut) atau tipe rasional (pelampung tidak diperbolehkan, karena mereka menyebabkan masalah dengan presisi dan keterbagian) dan harus menghasilkan bilangan bulat yang mewakili produk titik dari keduanya. input.

Ini adalah kode-golf sehingga jawaban akan dicetak dalam byte dengan lebih sedikit byte yang lebih baik.

Uji Kasus

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 Wisaya Gandum
sumber
Vektor tidak memiliki dimensi, ruang vektor tidak.
Jonathan Frech
5
@JonathanFrech Saya pikir ini agak terlalu berlebihan, tapi saya sudah membuat perubahan.
Wheat Wizard
"Angka alami" secara umum dipahami mengandung 0, yang tidak terwakili dalam sistem Anda. Dan ini bukan vektor. Ruang vektor berada di atas bidang, dan ini di atas cincin, yang akan menjadikan ini modul. Dan ini bukan ruang terpisah dari bilangan bulat, ini adalah ruang yang sama dengan representasi yang berbeda.
Akumulasi
6
@Akumulasi "Angka alamiah" bukan istilah yang didefinisikan dengan baik, tergantung pada siapa Anda bertanya mungkin atau mungkin tidak mengandung nol. Anda benar bahwa "perkalian skalar" dalam pertanyaan saya membentuk G-set dengan monoid daripada grup, tetapi itu disederhanakan untuk tujuan membuat pertanyaan itu enak. Saya tidak yakin apa yang harus dibuat dari komentar terakhir Anda, yakin itu memiliki kardinalitas yang sama dengan bilangan bulat, tetapi aksinya benar-benar menentukan ruang bukan ukurannya. Mungkin maksud Anda sesuatu yang lebih spesifik yang saya lewatkan. Jika demikian, saya akan senang melanjutkan diskusi ini (dalam obrolan mungkin yang terbaik).
Wheat Wizard
2
Terminologi lain pilihan: Ruang vektor umumnya dipersyaratkan untuk memiliki perkalian skalar dari suatu bidang, jadi hanya menggunakan bilangan bulat saja tidak cukup. Itu karena kami ingin vektor paralel menjadi kelipatan satu sama lain, bukan hanya memiliki beberapa kesamaan. Sebagai contoh, $ 4 $ dan $ 8 $ adalah "vektor" paralel dalam ruang ini (keduanya berupa lain. Namun, sebenarnya tidak banyak istilah lain yang dapat Anda gunakan, yang akan diketahui orang secara umum. "Modul gratis di atas bilangan bulat" adalah yang terbaik yang bisa saya lakukan.
Arthur

Jawaban:

4

MATL , 12 byte

YF2:&Y)dwd*s

Input adalah sebuah array [num1 den1 num2 den2].

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Pertimbangkan contoh 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
Luis Mendo
sumber
4

C (gcc) , 99 + 32 = 131 byte

  • Menggunakan flag compiler yang membutuhkan 32 byte -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;}

Cobalah online!

Jonathan Frech
sumber
Saya pikir lebih baik untuk secara eksplisit menentukan bahwa bendera tambahan -D=F(v,V,e)for(;v%p<1;V+=e)v/=p;(32 byte) digunakan (jadi 99 + 32 = 131); jika tidak, kode itu sendiri tidak masuk akal.
Bubbler
3

Python 2 , 110 byte

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

Cobalah online!

Mengambil input seperti [num1, num2, den1, den2]. Menggunakan bilangan kompleks runtuk menyimpan entri untuk prima puntuk dua rasional, dan (r*r).imag/2untuk mengekstraksi produk mereka r.real*r.imagdalam jumlah keseluruhan t. Menambahkan 1j**iuntuk i=0,1,2,3apakah setiap kombinasi menambah atau mengurangi bagian nyata atau imajiner untuk empat angka input.

Bubbler menyimpan 2 byte dengan menggabungkan nilai awal p=t=2.

Tidak
sumber
1
p=t=2alih-alih p=2;t=0sejak t.realitu diabaikan saja ( TIO ).
Bubbler
@ Lubbler Bagus, tambah!
xnor
1

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

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)

Cobalah online!

Pass angka-angka sebagai array [Num1, Den1, Num2, Den2].

Terima kasih untuk Arnauld karena memperbaiki yang hilang F=tanpa byte tambahan, dan 2 byte lebih sedikit.

Penjelasan & 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
sumber
1

J , 19 byte

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

Cobalah online!

Penjelasan:

Sebuah kata kerja diad, argumen ada di sisi kiri dan kanan

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

Stax , 11 byte

ä÷ß½♂←√:=Ü]

Jalankan dan debug itu

Representasi ascii yang sesuai dari program yang sama adalah ini.

{|nmMFE-~-,*+

Pada dasarnya, ia mendapat eksponen faktorisasi utama untuk setiap bagian. Dibutuhkan perbedaan dari masing-masing pasangan, kemudian produk, dan akhirnya merangkum semua hasil.

rekursif
sumber
1

Python 2 , 133 127 byte

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

Cobalah online!

Mencuri kondisi loop dari pengajuan xnor .

Terima kasih atas saran dari @mathmandan untuk mengubah fungsi menjadi program (Ya, itu memang menghemat beberapa byte).

Usang, solusi salah (124 byte):

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
sumber
Apakah tidak pakan menguji nilai non-prime seperti 9?
xnor
Ups, saya akan segera memperbaikinya.
Bubbler
3
Anda dapat menggantinya returndengan print, dan Anda juga dapat menyimpan ruang lekukan jika Anda menulis sebagai program alih-alih fungsi.
mathmandan
@mathmandan Terima kasih atas informasinya. Tampak berguna untuk pengiriman Py2 saya yang lain, tidak yakin untuk Py3 (butuh tambahan eval()kecuali fungsi input itu sendiri adalah sebuah string).
Bubbler
1

Haskell , 153 byte

(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

Cobalah online! Contoh penggunaan untuk 20 · 14/15: (2%) [20,1,14,15].

Laikoni
sumber