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 . Atau, secara umum, untuk bilangan bulat -negatif , ada bilangan bulat sedemikian rupa
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
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 dapat dianggap terkait dengan bilangan bulat . 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):
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:
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)
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:
menghasilkan lebar, panjang, dan tinggi 2, 2, dan 2, memberikan volume 8.
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.
sumber
Jawaban:
Bahasa Wolfram (Mathematica) ,
6758 byteCobalah online!
sumber
Jelly , 17 byte
Cobalah online! (Cukup lambat - buat cukup cepat untuk semua kasus uji dengan pemimpin
½
)Bagaimana?
sumber
Haskell ,
132123 byteCobalah 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 sehinggamax!p
mengembalikan daftar ukuran 3 yang terdiri dari maksimum di sepanjang setiap dimensi danmin!p
melakukan hal yang sama untuk minimum. Kemudian kami hanya menemukan ukuran minimum di setiap dimensi (dengan mengurangi nilai min dari maks denganz(-)
) dan mengalikannya bersama.Terima kasih banyak kepada @Lynn karena melepas 9 byte dengan sihir lipat zip!
sumber
zipWith
logika. 123 byteSledgehammer 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
yang setara dengan mengevaluasi kode Wolfram berikut yang berasal dari jawaban Bahasa Wolfram saya :
Cobalah online!
sumber
Python 2 , 138 byte
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 sepertiitertools.combinations_with_replacement
Python 2 , 161 byte
Cobalah online!
Inilah sebabnya mengapa
itertools
tidak pernah jawabannya .sumber
JavaScript (ES6),
148143 byteCobalah online!
Berkomentar
Langkah 1
Langkah 2
sumber
C # (Visual C # Interactive Compiler) , 229 byte
Cobalah online!
sumber
05AB1E , 18 byte
Cobalah online!
Port of Jonathan Jonathan menjawab Jelly .
sumber
Haskell , 108 byte
Cobalah online! (waktu habis pada kasus uji yang lebih besar)
Ada beberapa optimasi aneh di sini. Untuk menghitung
maximum l-minimum l
daftarl
elemen pada posisi yang diberikan, ternyata lebih pendek dalam konteks untuk mengonversi keduanya menjadi maksimal dengan meniadakan istilah kedua:,maximum l+maximum(map((-1)*))l
atau setarasum[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%2
daripada menggunakan segala jenis loop. Di sini,n%i
adalah perbedaan antarai
nilai 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 dijumlahkann
dan dalam urutan menurun. Kami memeriksa penyortiran terbalikt
denganscanr1 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.sumber