Qvolume integer

31

Ini adalah pengetahuan kuno bahwa setiap bilangan bulat non-negatif dapat ditulis ulang sebagai jumlah dari empat bilangan bulat kuadrat. Misalnya angka 1 dapat dinyatakan sebagai 02+02+02+12 . Atau, secara umum, untuk bilangan bulat n -negatif , ada bilangan bulat a,b,c,d sedemikian rupa

n=a2+b2+c2+d2

Joseph-Louis Lagrange membuktikan ini pada 1700-an dan karenanya sering disebut Teorema Lagrange .

Ini kadang-kadang dibahas dalam kaitannya dengan angka empat - tipe angka yang ditemukan oleh William Hamilton pada 1800-an, yang direpresentasikan sebagai

w+xi+yj+zk
mana w,x,y,z adalah bilangan real, dan i,j dan k adalah unit imajiner berbeda yang tidak berkembang biak secara komutatif. Secara khusus, itu dibahas dalam kaitannya dengan mengkuadratkan setiap komponen dari angka empat
w2+x2+y2+z2
Kuantitas ini kadang-kadang disebutnorma, atau norma kuadrat, atau jugakuadran. Beberapabukti moderndari Teorema Lagrange menggunakan angka empat.

Rudolf Lipschitz mempelajari angka empat dengan hanya komponen integer, yang disebut angka empat Lipschitz. Dengan menggunakan quadrance, kita dapat membayangkan bahwa setiap angka empat Lipschitz dapat dianggap memiliki teman dalam bilangan bulat. Misalnya angka empat 0+0i+0j+1k dapat dianggap terkait dengan bilangan bulat 1=02+02+02+12 . Juga, jika kita mundur, maka setiap bilangan bulat dapat dianggap memiliki teman di angka empat Lipschitz.

Tetapi ada detail menarik dari teorema Lagrange - penjumlahannya tidak unik. Setiap integer mungkin memiliki beberapa set empat kotak yang berbeda yang dapat dijumlahkan untuk membuatnya. Misalnya, angka 1 dapat diekspresikan dalam 4 cara menggunakan bilangan bulat non-negatif (marilah kita hanya mempertimbangkan non-negatif untuk tantangan ini):

1=02+02+02+12
1=02+02+12+02
1=02+12+02+02
1=12+02+02+02

Puncak selalu kuadrat dari 0, atau 1, tetapi mereka bisa berada di posisi yang berbeda dalam ekspresi.

Untuk tantangan ini, mari kita juga "menyortir" puncak kita yang terendah ke tertinggi, untuk menghilangkan duplikat, sehingga kita dapat mempertimbangkan, untuk latihan ini, bahwa 1 hanya memiliki satu cara untuk direpresentasikan sebagai jumlah dari empat kotak:

1=02+02+02+12

Contoh lain adalah angka 42, yang dapat dinyatakan dalam empat cara (sekali lagi, hanya mempertimbangkan non-negatif a, b, c, d, dan menghilangkan pengaturan komponen duplikat)

42=02+12+42+52
42=12+12+22+62
42=12+32+42+42
42=22+22+32+52

Bagaimana jika kita membayangkan masing-masing cara mengekspresikan bilangan bulat yang terkait dengan angka empat tertentu? Maka kita dapat mengatakan nomor 42 dikaitkan dengan empat angka empat ini:

0+1i+4j+5k
1+1i+2j+6k
1+3i+4j+4k
2+2i+3j+5k

ijkxyz(x,y,z)

(1,4,5),(1,2,6),(3,4,4),(2,3,5)

x,y,z

0+0i+0j+1k(1,2,4)(3,4,6) menghasilkan lebar, panjang, dan tinggi 2, 2, dan 2, memberikan volume 8.

nnw+xi+yj+zkw<=x<=y<=z

nn

Contoh:

input -> output
0 -> 0
1 -> 0
31 -> 4
32 -> 0
42 -> 8
137 -> 96
1729 -> 10032

Ini adalah kode-golf, jumlah byte terkecil yang menang.

jangan cerah
sumber
apa yang harus saya tambahkan? saya bermaksud menunjukkan bahwa jumlah byte terkecil akan menang
jangan terang
3
Anda lupa tag kode-golf, saya membantu Anda menambahkannya
Perwujudan Ketidaktahuan
1
Ini adalah tantangan yang bagus tetapi akan lebih baik jika IMHO itu sedikit kurang verbose. Waspadalah terhadap tautan yang tidak relevan (saya tidak mengatakan bahwa semua tautan Anda tidak relevan, tetapi hanya beberapa di antaranya yang benar-benar membawa informasi yang bermakna untuk tantangan, sementara yang lain hanya mengganggu).
Arnauld
1
Ya, tetapi mengapa hanya mengambil i, j, k sebagai ruang 3D tetapi bukan ruang 4D?
tsh
1
@ tsh karena Quaternions tidak selalu mewakili ruang Euclidean 4 dimensi. Hamilton menemukan mereka saat mencari cara untuk bekerja dengan ruang 3 dimensi. Mungkin saja untuk melakukan versi 4d tetapi saya sedang mempertimbangkan penggunaannya di ruang 3d ketika saya mengajukan pertanyaan
don bright

Jawaban:

13

Bahasa Wolfram (Mathematica) , 67 58 byte

Volume@BoundingRegion[Rest/@PowersRepresentations[#,4,2]]&

Cobalah online!

                         ...&   Pure function:
PowersRepresentations[#,4,2]    Get the sorted reprs. of # as sums of 4 2nd powers
Rest/@                         Drop the first coordinate of each
BoundingRegion[...]            Find the bounding region, a Cuboid[] or Point[].
                               By default Mathematica finds an axis-aligned cuboid.
Volume                         Find volume; volume of a Point[] is 0.
lirtosiast
sumber
4
wow, saya tidak tahu bahwa sesuatu seperti PowersRepresentations akan dibangun dalam bahasa. Aku benar-benar berpikir tentang membuat tantangan untuk menunjukkan cara-cara yang berbeda untuk menjumlahkan bilangan bulat sebagai empat kotak tetapi saya senang saya tidak melakukannya.
don bright
4
Lol, Mathematica bahkan memiliki builtin untuk menentukan kambing dalam sebuah gambar , jadi memiliki builtin untuk ini benar-benar tidak mengejutkan saya. xD
Kevin Cruijssen
8

Jelly , 17 byte

Żœċ4²S⁼ɗƇ⁸ZḊṢ€I§P

Cobalah online! (Cukup lambat - buat cukup cepat untuk semua kasus uji dengan pemimpin½ )

Bagaimana?

Żœċ4²S⁼ɗƇ⁸ZḊṢ€I§P - Link: non-negative integer, n    e.g. 27
Ż                 - zero-range                            [0,1,2,...,27]
   4              - literal four                          4
 œċ               - combinations with replacement         [[0,0,0,0],[0,0,0,1],...,[0,0,0,27],[0,0,1,1],[0,0,1,2],...,[27,27,27,27]]
        Ƈ         - filter keep those for which:          e.g.: [0,1,1,5]
       ɗ          -   last three links as a dyad:
    ²             -     square (vectorises)                     [0,1,1,25]
     S            -     sum                                     27
      ⁼  ⁸        -     equal to? chain's left argument, n      1
                  -                                       -> [[0,1,1,5],[0,3,3,3],[1,1,3,4]]
          Z       - transpose                             [[0,0,1],[1,3,1],[1,3,3],[5,3,4]]
           Ḋ      - dequeue                               [[1,3,1],[1,3,3],[5,3,4]]
            Ṣ€    - sort each                             [[1,1,3],[1,3,3],[3,4,5]]
              I   - incremental differences (vectorises)  [[ 0,2 ],[ 2,0 ],[ 1,1 ]]
               §  - sum each                              [2,2,2]
                P - product                               8
Jonathan Allan
sumber
6

Haskell , 132 123 byte

z=zipWith
(!)=foldr1.z
h n=[0..n]
f n|p<-[[c,b,a]|a<-h n,b<-h a,c<-h b,d<-h c,a^2+b^2+c^2+d^2==n]=product$z(-)(max!p)$min!p

Cobalah online!

Solusi yang sangat mudah. Brute paksa semua solusi yang mungkin dengan mengulangi semua nilai dari 0 hingga n (terlalu banyak cara tetapi bytecount lebih pendek). Saya menampilkan titik sebagai daftar sehingga kita dapat menggunakan (!)operator sihir @ Lynn . Operator itu runtuh setiap dimensi dengan fungsi di sisi kiri sehingga max!pmengembalikan daftar ukuran 3 yang terdiri dari maksimum di sepanjang setiap dimensi dan min!pmelakukan hal yang sama untuk minimum. Kemudian kami hanya menemukan ukuran minimum di setiap dimensi (dengan mengurangi nilai min dari maks dengan z(-)) dan mengalikannya bersama.

Terima kasih banyak kepada @Lynn karena melepas 9 byte dengan sihir lipat zip!

pengguna1472751
sumber
1
Saya mencukur beberapa byte dengan membiarkan transposisi mendukung beberapa zipWithlogika. 123 byte
Lynn
5

Sledgehammer 0.2, 12 byte

⡌⢎⣟⡊⢘⣚⡏⡨⠍⠁⡇⠨

Gunakan dengan Mathematica 11.2 dan Sledgehammer versi ini , yang ada sebelum tantangan. Lihat edit riwayat untuk versi yang berfungsi di versi 0.3, yang memiliki GUI dan menghasilkan ekspresi Mathematica.

Ini mendorong input ke stack dan memanggil urutan perintah

{intLiteral[4], intLiteral[2], call["PowersRepresentations", 3], call["Thread", 1], call["Rest", 1], call["Thread", 1], call["BoundingRegion", 1], call["Volume", 1]}

yang setara dengan mengevaluasi kode Wolfram berikut yang berasal dari jawaban Bahasa Wolfram saya :

Volume[BoundingRegion[Thread@Rest@Thread@PowersRepresentations[#, 4, 2]]]&

Cobalah online!

lirtosiast
sumber
apakah ini memerlukan mathatica untuk mengujinya?
don bright
@don cerah Ya, repositori memiliki instruksi. Ini adalah pekerjaan yang sedang berlangsung sehingga belum terlalu ramah pengguna. Setelah menjalankan setup.wls Anda dapat menguji dengan wolframscript atau interactive_app.wls.
lirtosiast
2
@Downgoat Ya. Saya berencana untuk mengimplementasikan perpustakaan golf, tetapi saat ini dekompres ke Mathematica biasa.
lirtosiast
2
@pipe Versi yang lebih lama seharusnya berfungsi (sekarang saya sudah memikirkannya, kodenya persis sama pada satu versi yang lebih lama), tetapi saya harus mengunduhnya dan menjalankan pengaturan lagi. (Perubahan sejak itu sebagian besar telah menulis GUI dan kode refactoring tanpa perubahan besar dalam fungsionalitas.) Karena jawaban ini terpendek, tampaknya penting untuk membuktikan kelayakannya, jadi saya akan melakukannya besok pagi.
lirtosiast
1
adakah yang bisa menjalankan ini? Saya agak ingin memverifikasi itu berfungsi sebelum memberikannya tanda centang ol '.
don cerah
4

Python 2 , 138 byte

q=lambda n,x=0,*t:[t]*(n==0)if t[3:]else q(n-x*x,x,x,*t)+q(n,x+1,*t+(0,)*(x>n))
p=1
for l in zip(*q(input()))[:3]:p*=max(l)-min(l)
print p

Cobalah online!

Secara rekursif menghasilkan angka empat yang diurutkan terbalik dengan norma yang diberikan, kemudian mengambil produk antara maksimum dan minimum dari semua nilai yang mungkin dalam tiga indeks pertama.

itertools mungkin memiliki kesempatan jika itu tidak menggunakan nama yang sangat panjang seperti itertools.combinations_with_replacement

Python 2 , 161 byte

from itertools import*
n=input();p=1
for l in zip(*[t[1:]for t in combinations_with_replacement(range(n+1),4)if sum(x*x for x in t)==n]):p*=max(l)-min(l)
print p

Cobalah online!

Inilah sebabnya mengapa itertoolstidak pernah jawabannya .

Tidak
sumber
3

JavaScript (ES6),  148  143 byte

n=>(r=[[],[],[]]).map(a=>p*=a.length+~a.indexOf(1),(g=(s,k=0,a=[])=>a[3]?s||r.map(r=>r[a.pop()]=p=1):g(s-k*k,k,[...a,++k],k>s||g(s,k,a)))(n))|p

Cobalah online!

Berkomentar

r

r = [ [], [], [] ]

x1x+1yz

1

Langkah 1

rg

g = (              // g is a recursive function taking:
  s,               // s   = current sum, initially set to the input n
  k = 0,           // k   = next value to be squared
  a = []           // a[] = list of selected values
) =>               //
  a[3] ?           // if we have 4 values in a[]:
    s ||           //   if s is equal to zero (we've found a valid sum of 4 squares):
      r.map(r =>   //     for each array r[] in r[]:
        r[a.pop()] //       pop the last value from a[]
        = p = 1    //       and set the corresponding value in r[] to 1
                   //       (also initialize p to 1 for later use in step 2)
      )            //     end of map()
  :                // else:
    g(             //   do a recursive call:
      s - k * k,   //     subtract k² from s
      k,           //     pass k unchanged
      [...a, ++k], //     increment k and append it to a[]
      k > s ||     //     if k is less than or equal to s:
        g(s, k, a) //       do another recursive call with s and a[] unchanged
    )              //   end of outer recursive call

Langkah 2

p

r.map(a =>         // for each array a[] in r[]:
  p *=             //   multiply p by:
    a.length +     //     the length of a[]
    ~a.indexOf(1)  //     minus 1, minus the index of the first 1 in a[]
) | p              // end of map(); return p
Arnauld
sumber
2

C # (Visual C # Interactive Compiler) , 229 byte

a=>{uint b=0,c=~0U,d,e,f=0,g=0,h=0,i=c,j=c,k=c;for(;b*b<=a;b++)for(c=b;c*c<=a;c++)for(d=c;d*d<=a;d++)for(e=d;e*e<=a;e++)if(b*b+c*c+d*d+e*e==a){f=c>f?c:f;g=d>g?d:g;h=e>h?e:h;i=c<i?c:i;j=d<j?d:j;k=e<k?e:k;}return(f-i)*(g-j)*(h-k);}

Cobalah online!

Perwujudan Ketidaktahuan
sumber
1

Haskell , 108 byte

n%i=sum[maximum[t!!i*b|t<-mapM([0..n]<$f)[0..3],sum(map(^2)t)==n,scanr1 max t==t]|b<-[-1,1]]
f n=n%0*n%1*n%2

Cobalah online! (waktu habis pada kasus uji yang lebih besar)

Ada beberapa optimasi aneh di sini. Untuk menghitung maximum l-minimum ldaftar lelemen pada posisi yang diberikan, ternyata lebih pendek dalam konteks untuk mengonversi keduanya menjadi maksimal dengan meniadakan istilah kedua:, maximum l+maximum(map((-1)*))latau setara sum[maximum$map(b*)l||b<-[-1,1]].

Untuk melipatgandakan tiga dimensi, ternyata lebih pendek untuk hanya menulis produk f n=n%0*n%1*n%2daripada menggunakan segala jenis loop. Di sini, n%iadalah perbedaan antara inilai koordinat min dan maks dari nilai 'th, yang diekstraksi dengan pengindeksan !!i.

Untuk menghasilkan empat tupel yang valid, kami mengambil daftar empat angka dari [0..n]kuadrat yang dijumlahkan ndan dalam urutan menurun. Kami memeriksa penyortiran terbalik tdengan scanr1 max t==t, yang melihat apakah maksimum berjalannya terbalik itu sendiri, karena Haskell tidak memiliki jenis bawaan tanpa impor yang mahal. Saya mencoba berbagai cara untuk secara rekursif menghasilkan empat-tupel seperti dalam jawaban Python saya, tetapi mereka semua lebih lama dari cara brute-force menghasilkan-dan-filter ini.

Tidak
sumber