Bilangan bulat positif k
adalah angka Loeschian jika
k
dapat dinyatakan sebagaii*i + j*j + i*j
untuki
,j
bilangan bulat.
Misalnya, angka Loeschian positif pertama adalah: 1
( i=1
, j=0
); 3
( i=j=1
); 4
( i=2
, j=0
); 7
( i=2
, j=1
); 9
( i=-3
, j=3
); ... Perhatikan bahwa i
, j
untuk yang diberikan k
tidak unik. Sebagai contoh, 9
juga dapat dihasilkan dengan i=3
, j=0
.
Karakterisasi setara lainnya dari angka-angka ini adalah:
k
dapat dinyatakani*i + j*j + i*j
untuki
,j
bilangan bulat non-negatif. (Untuk setiap pasangan bilangan bulati
,j
ada sepasang bilangan bulat non-negatif yang memberikan hal yang samak
)Ada satu set
k
heksagon yang berdekatan yang membentuk tesselation pada kisi heksagonal (lihat ilustrasi untukk = 4
dan untukk = 7
). (Karena properti ini, angka-angka ini menemukan aplikasi dalam jaringan komunikasi seluler ).Lihat lebih banyak penokohan di halaman OEIS urutan.
Tantangan
Dengan bilangan bulat positif , hasilkan hasil yang benar jika itu adalah angka Loeschian , atau hasil yang salah.
Program atau fungsi harus menangani (katakan dalam waktu kurang dari satu menit) input hingga 1000
, atau hingga batasan tipe data.
Golf kode. Kemenangan terpendek.
Uji kasus
Angka-angka berikut harus menampilkan hasil yang benar:
1, 4, 7, 12, 13, 108, 109, 192, 516, 999
Angka-angka berikut harus menampilkan hasil palsu:
2, 5, 10, 42, 101, 102, 128, 150, 501, 1000
sumber
i, j non-negative integers
atau9 (i=-3, j=3)
- yang mana itu?Jawaban:
Jelly ,
119 byteCobalah online! atau verifikasi semua kasus uji .
Latar Belakang
Dalam hasil Dasar pada bentuk kuadratik biner a² + ab + b² , penulis membuktikan teorema berikut tentang bilangan Löschian.
Sebagaimana dicatat pada halaman OEIS yang relevan , karena semua bilangan bulat adalah kongruen dengan 0 , 1 atau 2 modulo 3 , angka 3 adalah satu-satunya prima yang kongruen dengan 0 , dan semua angka dalam bentuk (6k + 1) adalah kongruen dengan 1 , teorema dapat dinyatakan sebagai alternatif sebagai berikut.
Sebuah bilangan bulat non-negatif n adalah nomor Löschian jika dan hanya jika semua faktor prima dari n yang kongruen dengan 2 Modulo 3 bahkan eksponen.
Bagaimana itu bekerja
sumber
Retina ,
6663454336 byteTerlepas dari judul yang mengatakan Retina, ini hanyalah .NET biasa yang menerima representasi nomor Loeschian yang unary .
Input 999 dan 1000 baik dalam waktu satu detik.
Cobalah online! (Baris pertama memungkinkan suite tes yang dipisahkan dengan linefeed, dan dua baris berikutnya mengurus konversi menjadi unary untuk kenyamanan.)
Penjelasan
Solusi didasarkan pada klasifikasi bahwa input dapat ditulis sebagai
i*i + j*(i + j)
positifi
dan non-negatifj
(karena kita tidak harus menangani input0
), dan itun*n
hanya jumlah darin
bilangan bulat ganjil pertama . Bermain golf ini adalah latihan yang menarik dalam referensi ke depan."Referensi ke depan" adalah ketika Anda meletakkan referensi di dalam grup yang dimaksud. Tentu saja itu tidak berfungsi ketika grup digunakan pertama kali, karena tidak ada yang harus direferensikan lagi, tetapi jika Anda menempatkan ini dalam satu lingkaran, maka backreference mendapatkan tangkapan iterasi sebelumnya setiap kali. Ini pada gilirannya, mari kita membangun tangkapan yang lebih besar dengan setiap iterasi. Ini dapat digunakan untuk membuat pola yang sangat ringkas untuk hal-hal seperti angka segitiga, kuadrat, dan angka Fibonacci.
Sebagai contoh, menggunakan fakta bahwa kuadrat hanya jumlah dari
n
bilangan bulat ganjil pertama , kita dapat mencocokkan input persegi seperti ini:Pada iterasi pertama,
..\1
tidak dapat bekerja, karena\1
belum memiliki nilai. Jadi kita mulai dengan^.
, menangkap satu karakter ke dalam grup1
. Pada iterasi berikutnya,^.
tidak lagi cocok karena jangkar, tetapi sekarang..\1
valid. Ini cocok dengan dua karakter lebih banyak dari iterasi sebelumnya dan memperbarui penangkapan. Dengan cara ini kami mencocokkan peningkatan angka ganjil, mendapatkan kotak setelah setiap iterasi.Sayangnya, kita tidak bisa menggunakan teknik ini apa adanya. Setelah mencocokkan
i*i
, kita perlu mendapatkani
juga, sehingga kita dapat melipatgandakannya denganj
. Cara sederhana (tapi panjang) untuk melakukan ini adalah dengan menggunakan fakta bahwa pencocokani*i
membutuhkani
iterasi, sehingga kami telah menangkapi
hal-hal dalam kelompok1
. Kita sekarang bisa menggunakan kelompok penyeimbang untuk mengekstrak inii
, tapi seperti saya katakan itu mahal.Sebagai gantinya, saya menemukan cara yang berbeda untuk menulis "jumlah bilangan bulat ganjil berturut-turut" ini yang juga menghasilkan
i
kelompok penangkap pada akhirnya. Tentu saja angkai
ganjilnya adalah adil2i-1
. Ini memberi kita cara untuk menambah referensi maju hanya dengan 1 pada setiap iterasi. Itu bagian ini:Ini
()
hanya mendorong tangkapan kosong ke grup1
(menginisialisasii
ke0
). Ini cukup setara dengan^.|
solusi sederhana di atas, tetapi menggunakan|
dalam kasus ini akan sedikit rumit.Kemudian kita memiliki loop utama
(\1(?<1>.\1))
.\1
cocok dengan yang sebelumnyai
,(?<1>.\1)
lalu perbarui grup1
dengani+1
. Dari segi yang barui
, kami baru saja mencocokkan2i-1
karakter. Tepat seperti yang kita butuhkan.Setelah selesai, kami telah mencocokkan beberapa kotak
i*i
dan grup1
masih menyimpani
karakter.Bagian kedua lebih dekat dengan pencocokan kotak sederhana yang saya tunjukkan di atas. Mari kita abaikan backreference
1
untuk saat ini:Ini pada dasarnya sama dengan
(^.|..\4)*
, kecuali bahwa kita tidak dapat memanfaatkannya^
karena kita tidak di awal string. Alih-alih, kami menggunakan persyaratan, untuk mencocokkan tambahan.\1
hanya ketika kami sudah menggunakan grup4
. Tetapi pada dasarnya ini persis sama. Ini memberi kitaj*j
.Satu-satunya hal yang hilang adalah
j*i
istilah itu. Kami menggabungkan ini denganj*j
menggunakan fakta bahwaj*j
perhitungan masih membutuhkanj
iterasi. Jadi untuk setiap iterasi, kami juga memajukan kursori
dengan\1
. Kita hanya perlu memastikan untuk tidak menuliskannya ke dalam grup4
, karena itu akan mengacaukan dengan pencocokan angka ganjil berturut-turut. Begitulah cara kami tiba di:sumber
CJam (
1615 bytes)Demo online
Ini adalah blok ("fungsi anonim") yang mengambil input pada tumpukan dan daun
0
atau1
pada stack. Ia menggunakan karakterisasi bahwa suatu bilangan adalah Loeschian jika tidak memiliki faktor prima sama dengan 2 mod 3 dengan multiplisitas ganjil.Terima kasih kepada Dennis untuk penghematan satu byte.
sumber
Python 2, 56 byte
sumber
Haskell, 42 byte
Contoh penggunaan:
f 501
->False
.Mencoba semua kombinasi
i
dari0
kek
danj
dari0
kei
.or
kembaliTrue
jika kesetaraank==i*i+j*j+i*j
berlaku untuk setidaknya satu kombinasi.@ flawr menemukan versi yang sedikit berbeda dengan jumlah byte yang sama:
sumber
or
, keren =) Mungkin Anda memiliki ide bagaimana untuk golf ungkapan ini alternatif:f k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]
?Java 8, 81 byte
implementasi yang sederhana dan naif. kebetulan kode yang sama dengan C # tetapi menggunakan
->
daripada=>
.sumber
;
. MENGUTUK!i
atauj
.Python, 67 byte
https://repl.it/Cj6x
sumber
Jelly ,
15141312 byte1 byte berkat mil.
Cobalah online!
Periksa testcases yang lebih kecil .
Sebuah saran saat menguji untuk jumlah besar (lebih dari 50): jangan.
Kebenaran adalah angka positif. Falsey adalah nol.
Penjelasan
sumber
Ubur-ubur ,
5643412928 byte2 byte berkat Zgarb
Cobalah online!
Garpu jawaban Jelly saya .
sumber
MATL ,
1413 byteCobalah online! Atau verifikasi semua kasus uji .
Output
1
atau0
.Penjelasan
sumber
Python, 49 byte
Menggunakan bentuk kuadrat setara diberikan pada Oei dari
n == 3*i*i+j*j
. Periksa apakahn-3*i*i
kuadrat sempurna untuk semuai
dengan mengambil akar kuadratnya dan memeriksa apakah itu bilangan bulat, yaitu sama dengan 0 modulo 1. Perhatikan bahwa Python menghitung akar kuadrat dari kuadrat sempurna dengan tepat, tanpa kesalahan floating point. Itu+0j
membuatnya menjadi bilangan kompleks untuk menghindari kesalahan pada akar kuadrat dari negatif.sumber
C (gcc),
7169 bytesumber
i,j,r;f(n){for(r=i=n+1;i--;)for(j=n;j--;)r*=n!=i*i+j*j+i*j;return!r;}
.i
atauj
.i
danj
.k
, tetapi tidaki
danj
. Lihatlah lebih dekat contoh-contohnya.k
dapat dinyatakan sebagaii*i + j*j + i*j
untuk bilangan bulati, j
non-negatif ." Anda melihat lebih dekat.C #,
848281 byteSolusi naif. 1 = benar, 0 = salah
sumber
VBA,
6867 bytePencarian naif, mulai melambat sedikit untuk n = 1000. Excel mengakui zero return sebagai falsy, semua return lainnya adalah true.
Perhatikan bahwa investigasi negatif i dan j tidak diperlukan, karena diberikan i> j> = 0 :
(hasil yang sama seperti untuk i dan j )
(Jika yang negatif, tidak masalah yang mana), lalu
Dan karena keduanya (ij) dan j adalah non-negatif, setiap generasi nomor Loeschian yang melibatkan angka negatif dapat dicapai dengan menggunakan angka non-negatif.
Menyimpan satu byte,
Next:Next
->Next b,a
terima kasih kepada Taylor Scott.sumber
i
atauj
.Next:Next
keNext b,a
:End Function
di akhir solusi AndaJavascript (menggunakan perpustakaan eksternal - Enumerable) (63 byte)
Tautan ke perpustakaan: https://github.com/mvegh1/Enumerable Code penjelasan: Buat rentang bilangan bulat dari 0 hingga k (sebut ini rentang "i"), dan uji jika ada "i" yang memenuhi predikat tertentu. Predikat itu menciptakan rentang dari 0 hingga k (sebut ini rentang "j"), dan menguji apakah ada "j" yang memenuhi predikat tertentu. Predikat itu adalah formula loeschian
sumber
Perl 6 ,
52 5150 bytePenjelasan:
Uji:
sumber
i
atauj
.(0..$_ X 0..$_)
menghasilkan daftar kosong jika$_
kurang dari0
, jadi tidak perlu memeriksa negatifi
danj
karena mereka tidak akan pernah negatif. Karena seharusnya hanya menghasilkanTrue
angka Loeschian positif, saya tidak perlu melakukan sesuatu yang istimewa untuk kasus negatif.9 = (3*3)+(-3*-3)+(3*-3)
adalah Loeschian positif dengani=3, j=-3
; TETAPI saya tahu bahwa setiap nomor Loeschian memiliki non-negatifi
danj
. Jadi tidak perlu mencari angka negatif. Jadi sebenarnya kita bisa menghapus komentar itu. Maaf telah mengganggu; salahku.{grep ->(\i,\j){$_==i*i+j*j+i*j},(-$_..$_ X -$_..$_)}(9)
menghasilkan((-3,0),(-3,3),(0,-3),(0,3),(3,-3),(3,0))
. Jujur saya mungkin hanya mengadaptasinya dari jawaban lain.PowerShell v2 +,
635655 byteMengambil input
$k
, loop ke atas dua kali (loop luar$i = 0 to $k
, loop dalam$j = 0 to $i
), setiap iterasi menghasilkan hasili*i + j*j + i*j
(disingkat menjadii*(i+j) + j*j
). Hasil-hasil tersebut dirangkum dalam parens, dan diteruskan sebagai larik ke-eq$k
. Ini bertindak sebagai filter untuk memilih hanya elemen yang sama dengan input. Menghasilkan nol (angka kembali) untuk benar, atau tidak ada (kosong) untuk falsey. Proses1000
dalam waktu sekitar 15 detik pada mesin saya.Uji Kasus
sumber
Perl, 54 + 1 (
-n
bendera) = 55 byteKebutuhan
-n
dan-M5.010
bendera untuk dijalankan:Outputs beberapa barang jika nomor tersebut adalah nomor Loeschian, dan tidak ada yang sebaliknya.
Implementasi ini cukup membosankan, jadi inilah yang lain, untuk 87 byte, berbasis regex, hanya untuk mata:
Berhati-hatilah dengan yang satu ini, karena pengulangan akan menggunakan banyak memori, jadi jangan mencoba untuk menguji angka terlalu besar! (terutama angka yang bukan Loeschians)
sumber
Dyalog APL , 19 byte
Cek apakah k ∊ ( i + j ) ² - ij , untuk setiap 0 ≤ i , j ≤ k .
⊢
aku s k∊
anggota dari∘.
semua kombinasi dari×
i kali j-⍨
dikurangi dari2*⍨
kuadrat+
i ditambah j⍨
untuk semua i dan j dalam0,
nol yang ditambahkan ke⍳
bilangan bulat 1 sampai k1000 membutuhkan 3,3 detik pada M540 saya dan bahkan lebih sedikit di TryAPL .
sumber
Matlab,
5352 bytePencarian sederhana atas semua kemungkinan.
Output array kosong sebagai falsy dan vektor tidak kosong sebagai nilai sebenarnya.
Mempertimbangkan matriks all-nol sebagai matriks falsy dan not-all-zero sebagai kebenaran, kita dapat menyingkirkan
find
fungsi yang menghasilkan solusi4746 byte :Satu byte disimpan berkat @ flawr
sumber
(a+b).^2-a.*b==n
lebih pendek.C, 66 byte
Panggil
f()
dengan nomor untuk menguji. Fungsi mengembalikan jumlah solusi yang ditemukannya.Cobalah di ideone .
sumber
Mathematica, 44 byte
Fungsi tanpa nama mengambil integer sebagai input dan kembali
True
atauFalse
. Perintah0~Range~#~Tuples~2
membuat semua pasangan integer yang terurut baik di antara0
maupun input#
. Fungsi(+##)^2-##&
menghitung kuadrat dari jumlah argumennya dikurangi produk dari argumennya; ketika dipanggil pada dua argumeni
danj
, ini persisi^2+j^2+ij
seperti yang diinginkan. Jadi fungsi itu dipanggil pada semua tupel, dan kemudianMemberQ[...,#]
memeriksa apakah input adalah salah satu nilai yang dihasilkan.sumber
ASP, 39 + 4 = 43 byte
Keluaran: masalahnya memuaskan iff k adalah Loeschian.
Answer Set Programming adalah bahasa yang logis, mirip dengan prolog. Saya menggunakan implementasi Potassco di sini , clingo .
Input diambil dari parameter (
-ck=
panjangnya 4 byte). Contoh panggilan:Sampel keluaran:
Dicoba dengan 1000:
Sampel keluaran:
Anda dapat mencobanya di browser Anda ; sayangnya, metode ini tidak menangani flag panggilan, jadi Anda perlu menambahkan baris
#const k=999
untuk membuatnya berfungsi.Kode tidak dijelaskan & dijelaskan:
sumber
PHP, 70 byte
mengambil input dari argumen baris perintah; keluar dengan
1
nomor Loeschian, dengan yang0
lain.Jalankan dengan
-nr
.kerusakan
sumber