Apakah ini nomor Loeschian?

33

Bilangan bulat positif kadalah angka Loeschian jika

  • kdapat dinyatakan sebagai i*i + j*j + i*juntuk i, jbilangan 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, juntuk yang diberikan ktidak unik. Sebagai contoh, 9juga dapat dihasilkan dengan i=3, j=0.

Karakterisasi setara lainnya dari angka-angka ini adalah:

  • kdapat dinyatakan i*i + j*j + i*juntuk i, jbilangan bulat non-negatif. (Untuk setiap pasangan bilangan bulat i, jada sepasang bilangan bulat non-negatif yang memberikan hal yang sama k)

  • Ada satu set kheksagon yang berdekatan yang membentuk tesselation pada kisi heksagonal (lihat ilustrasi untuk k = 4dan untuk k = 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
Luis Mendo
sumber
Terkait (seperti dicatat oleh @PeterTaylor)
Luis Mendo
perhatikan untuk algoritma brute force: jika Anda beralih ke √k Anda mengurangi kompleksitas algoritma dari O (n²) menjadi O (n), dengan mengorbankan beberapa byte c;
Rod
i, j non-negative integersatau 9 (i=-3, j=3)- yang mana itu?
Titus
1
@Itus Oh sekarang saya mengerti. Untuk setiap pasangan bilangan bulat i, j ada pasangan non-negatif yang memberikan k yang sama
Luis Mendo

Jawaban:

17

Jelly , 11 9 byte

ÆF‘%3,2ḄȦ

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

Teorema 16. Syarat yang diperlukan dan cukup dari bilangan bulat non-negatif untuk berada dalam bentuk a² + ab + b² adalah bahwa, dalam faktorisasi prima, semua bilangan prima selain 3 yang tidak dalam bentuk (6k +1) memiliki eksponen.

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

ÆF‘%3,2ḄȦ  Main link. Argument: n (integer)

ÆF         Yield the prime factorization of n, as prime-exponent pairs.
  ‘        Increment all primes and exponents, turning primes of the form 3k - 2
           into multiples of 3 and odd exponents into multiples of 2.
   %3,2    Reduce all incremented primes/exponents modulo 3/2.
           n is Löschian if and only if this does not result in a [0, 0] pair.
           Due to Jelly's form of vectorization, this yields [3, 2] if n = 1.
       Ḅ   Unbinary; convert each pair from base 2 to integer.
           Note that [x, y] = [0, 0] if and only if 2x + y = 0.
        Ȧ  All; return 1 if the result contains no zeroes, 0 otherwise.
Dennis
sumber
17

Retina , 66 63 45 43 36 byte

^()(\1(?<1>.\1))+(\1(.(?(4).\4)))*$

Terlepas 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)positif idan non-negatif j(karena kita tidak harus menangani input 0), dan itu n*nhanya jumlah dari nbilangan 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 nbilangan bulat ganjil pertama , kita dapat mencocokkan input persegi seperti ini:

(^.|..\1)+$

Pada iterasi pertama, ..\1tidak dapat bekerja, karena \1belum memiliki nilai. Jadi kita mulai dengan ^., menangkap satu karakter ke dalam grup 1. Pada iterasi berikutnya, ^.tidak lagi cocok karena jangkar, tetapi sekarang ..\1valid. 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 mendapatkan ijuga, sehingga kita dapat melipatgandakannya dengan j. Cara sederhana (tapi panjang) untuk melakukan ini adalah dengan menggunakan fakta bahwa pencocokan i*imembutuhkan iiterasi, sehingga kami telah menangkap ihal-hal dalam kelompok 1. Kita sekarang bisa menggunakan kelompok penyeimbang untuk mengekstrak ini i, 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 ikelompok penangkap pada akhirnya. Tentu saja angka iganjilnya adalah adil 2i-1. Ini memberi kita cara untuk menambah referensi maju hanya dengan 1 pada setiap iterasi. Itu bagian ini:

^()(\1(?<1>.\1))+

Ini ()hanya mendorong tangkapan kosong ke grup 1(menginisialisasii ke 0). Ini cukup setara dengan ^.|solusi sederhana di atas, tetapi menggunakan |dalam kasus ini akan sedikit rumit.

Kemudian kita memiliki loop utama (\1(?<1>.\1)). \1cocok dengan yang sebelumnya i, (?<1>.\1)lalu perbarui grup 1dengan i+1. Dari segi yang baru i , kami baru saja mencocokkan 2i-1karakter. Tepat seperti yang kita butuhkan.

Setelah selesai, kami telah mencocokkan beberapa kotak i*idan grup 1masih menyimpan ikarakter.

Bagian kedua lebih dekat dengan pencocokan kotak sederhana yang saya tunjukkan di atas. Mari kita abaikan backreference 1untuk saat ini:

(.(?(4).\1))*

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 .\1hanya ketika kami sudah menggunakan grup 4. Tetapi pada dasarnya ini persis sama. Ini memberi kita j*j.

Satu-satunya hal yang hilang adalah j*iistilah itu. Kami menggabungkan ini dengan j*jmenggunakan fakta bahwa j*jperhitungan masih membutuhkan jiterasi. Jadi untuk setiap iterasi, kami juga memajukan kursor idengan \1. Kita hanya perlu memastikan untuk tidak menuliskannya ke dalam grup 4, karena itu akan mengacaukan dengan pencocokan angka ganjil berturut-turut. Begitulah cara kami tiba di:

(\1(.(?(4).\1)))*
Martin Ender
sumber
2
Semakin banyak saya membaca ini, semakin saya tidak mengerti. Saya benar-benar ingin tahu bahwa banyak regex
Javier Diaz
@JavierDiaz Ada serangkaian posting yang menjelaskan referensi ke depan tentang Stack Overflow, berdasarkan Java regex. Contoh-contoh di sana mungkin sedikit lebih sederhana.
Martin Ender
13

CJam ( 16 15 bytes)

{mF{~\3%2=&},!}

Demo online

Ini adalah blok ("fungsi anonim") yang mengambil input pada tumpukan dan daun 0atau1 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.

Peter Taylor
sumber
Wow, karakterisasi yang bagus!
Luis Mendo
6

Python 2, 56 byte

lambda n:any(n==i*i%n+i/n*(i/n+i%n)for i in range(2*n*n))
orlp
sumber
6

Haskell, 42 byte

f k=or[k==i*i+j*j+i*j|i<-[0..k],j<-[0..i]]

Contoh penggunaan: f 501->False .

Mencoba semua kombinasi idari 0ke kdan jdari 0ke i. orkembali Truejika kesetaraank==i*i+j*j+i*j berlaku untuk setidaknya satu kombinasi.

@ flawr menemukan versi yang sedikit berbeda dengan jumlah byte yang sama:

f k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]
nimi
sumber
Aku tidak tahu tentang 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]?
flawr
@ flawr: tidak, tidak tahu bagaimana cara bermain golf versi Anda lebih jauh. Jika Anda tidak keberatan, saya akan menambahkannya ke jawaban saya sebagai versi alternatif.
nimi
5

Java 8, 81 byte

k->{for(int i=0,j;i<=k;i++)for(j=0;j<=k;)if(i*i+j*j+i*j++==k)return 1;return 0;};

implementasi yang sederhana dan naif. kebetulan kode yang sama dengan C # tetapi menggunakan ->daripada =>.

Justin
sumber
Tiga byte lebih sedikit karena Anda dapat menghilangkan kurung kurawal dan berakhir ;. MENGUTUK!
TheLethalCoder
@TheLethalCoder Sebenarnya saya tidak bisa, saya membuat kesalahan - jumlah byte yang sama dengan C #.
Justin
Membuat saya merasa lebih baik :)
TheLethalCoder
Ini sepertinya tidak menguji negatif iatau j.
Titus
4

Python, 67 byte

lambda k,r=range:any(i*i+j*j+i*j==k for i in r(k+1)for j in r(k+1))

https://repl.it/Cj6x

ahli atlasologi
sumber
4

Jelly , 15 14 13 12 byte

1 byte berkat mil.

²S+P
‘ṗ2’Ç€i

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

‘ṗ2’Ç€i   main chain, argument: z
‘ṗ2’      generate all pairs of numbers between 0 and z inclusive
    ǀ    apply the helper link to each pair
      i   find the index of z in the result

²S+P   helper link, argument: [x,y] (a pair of numbers)
²      compute [x*x, y*y]
 S     x*x+y*y
  +P   x*x+y*y+x*y
Biarawati Bocor
sumber
Terikat (untuk) sekarang ... :-)
Luis Mendo
Haruskah kita mengeksploitasi karakterisasi Peter ...?
Luis Mendo
@LuisMendo Itu tampaknya menarik, tetapi tampaknya itu akan lebih lama
Leaky Nun
Saya pikir Anda tidak perlu meratakannya. Tautan pembantu Anda sudah memetakan dari tupel ke bilangan bulat.
mil
@ Miles Itu pintar, terima kasih.
Leaky Nun
3

MATL , 14 13 byte

t:0hU&+HM&*+m

Cobalah online! Atau verifikasi semua kasus uji .

Output 1atau 0.

Penjelasan

t:    % Implicitly input number k. Duplicate. Generate vector [1 2 ...k]
0h    % Concatenate a 0. Gives [1 2 ... k 0]
U     % Square, element-wise. Gives [1 4 ... k^2 0]
&+    % Sum of all pairs from this vector. Gives a (k+1)×(k+1) matrix
HM    % Push [1 2 ... k 0] again
&*    % Product of all pairs from this vector. Gives a (k+1)×(k+1) matrix
+     % Add the two matrices
m     % True if k is a member of the resulting matrix. Implicitly display
Luis Mendo
sumber
Apakah Anda baru saja bermain golf Jelly?
Leaky Nun
@ LeakyNun Mari kita lihat berapa lama berlangsung. Mungkin saya akan sedikit menunda penjelasan kode :-P
Luis Mendo
Nggak. - - - - -
Leaky Nun
Giliranmu - - -
Leaky Nun
@ LeakyNun Aw :-( Sekarang saya bisa menambahkan penjelasan :-)
Luis Mendo
3

Python, 49 byte

lambda n:0in[(n-3*i*i+0j)**.5%1for i in range(n)]

Menggunakan bentuk kuadrat setara diberikan pada Oei dari n == 3*i*i+j*j. Periksa apakah n-3*i*ikuadrat sempurna untuk semua idengan 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 +0jmembuatnya menjadi bilangan kompleks untuk menghindari kesalahan pada akar kuadrat dari negatif.

Tidak
sumber
3

C (gcc), 71 69 byte

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;}
orlp
sumber
69 byte: 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;}.
owacoder
Ini sepertinya tidak menguji negatif iatau j.
Titus
@Itus Pertanyaannya menentukan non-negatif idan j.
orlp
positif k, tetapi tidak idan j. Lihatlah lebih dekat contoh-contohnya.
Titus
@Titus Mengutip dari tantangan: " kdapat dinyatakan sebagai i*i + j*j + i*juntuk bilangan bulat i, j non-negatif ." Anda melihat lebih dekat.
orlp
2

C #, 84 82 81 byte

k=>{for(int i=0,j;i<=k;++i)for(j=0;j<=k;)if(i*i+j*j+i*j++==k)return 1;return 0;};

Solusi naif. 1 = benar, 0 = salah

TheLethalCoder
sumber
2

VBA, 68 67 byte

Function L(N):For a=0To N:For b=0To a:L=L+(N=a^2+a*b+b^2):Next b,a

Pencarian 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 :

(-i) 2 + (-i) (- j) + (-j) 2 = i 2 + ij + j 2

(hasil yang sama seperti untuk i dan j )

(-i) 2 + (-i) j + j 2 = i 2 - ij + j 2

i 2 + i (-j) + (-j) 2 = i 2 - ij + j 2

(Jika yang negatif, tidak masalah yang mana), lalu

(ij) 2 + (ij) j + j 2 = (i 2 - 2ij + j 2 ) + (ij - j 2 ) + j 2 = i 2 - ij + j 2

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,aterima kasih kepada Taylor Scott.

Joffan
sumber
Ini sepertinya tidak menguji negatif iatau j.
Titus
Lihat poin pertama di bawah "Karakterisasi setara lainnya". Perhatikan bahwa semua kasus uji muncul dengan benar. Saya akan menambahkan pembenaran matematika untuk jawaban saya (jika saya bisa).
Joffan
Maaf salah saya. Mengetahui bahwa itu tidak perlu.
Titus
@Joffan Anda dapat menyingkat Next:NextkeNext b,a
Taylor Scott
@Joffan melihat solusi Anda lagi mungkin itu karena hilang :End Functiondi akhir solusi Anda
Taylor Scott
1

Javascript (menggunakan perpustakaan eksternal - Enumerable) (63 byte)

k=>_.Range(0,k+1).Any(i=>_.Range(0,k+1).Any(j=>i*i+j*j+i*j==k))

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

masukkan deskripsi gambar di sini

applejacks01
sumber
1

Perl 6 ,  52 51  50 byte

->\k{?first ->(\i,\j){k==i*i+j*j+i*j},(0..k X 0..k)}
->\k{?grep ->(\i,\j){k==i*i+j*j+i*j},(0..k X 0..k)}

{?grep ->(\i,\j){$_==i*i+j*j+i*j},(0..$_ X 0..$_)}

Penjelasan:

{
  # Turn the following into a Bool
  # ( Technically not necessary as a list of 1 or more values is truthy )
  ?

  # find all where the code block returns a truthy value
  grep

  # pointy block that takes one value (list of 2 values)
  # and gives each of the values in it a name
  ->
    $ ( \i, \j )
  {
    # return true if the definition matches
    $_ == i*i + j*j + i*j
  },

  # a list of 2 element lists (possible i and j values)
  ( 0..$_ X 0..$_ )
}

Uji:

use v6.c;
use Test;

my @true = 0, 1, 4, 7, 12, 13, 108, 109, 192, 516, 999;
my @false = 2, 5, 10, 42, 101, 102, 128, 150, 501, 1000;

plan (@true + @false) * 2;

my &is-loeschian = {?grep ->(\i,\j){$_==i*i+j*j+i*j},(0..$_ X 0..$_)}

for |(@true X True), |(@false X False) -> ( $input, $expected ) {
  my ($result,$seconds) = $input.&time-it;
  is $result, $expected, ~$input;
  cmp-ok $seconds, &[<], 60, "in $seconds seconds"
}

sub time-it ( $input ) {
  my $start = now;
  my $result = $input.&is-loeschian;
  my $finish = now;
  return ( $result, $finish - $start )
}
1..42
ok 1 - 0
ok 2 - in 0.00111763 seconds
ok 3 - 1
ok 4 - in 0.00076766 seconds
...
ok 19 - 516
ok 20 - in 0.19629727 seconds
ok 21 - 999
ok 22 - in 0.1126715 seconds
ok 23 - 2
ok 24 - in 0.0013301 seconds
ok 25 - 5
ok 26 - in 0.00186610 seconds
...
ok 37 - 150
ok 38 - in 0.83877554 seconds
ok 39 - 501
ok 40 - in 9.2968558 seconds
ok 41 - 1000
ok 42 - in 37.31434146 seconds
Brad Gilbert b2gills
sumber
Ini sepertinya tidak menguji negatif iatau j.
Titus
@Itus (0..$_ X 0..$_)menghasilkan daftar kosong jika $_kurang dari 0, jadi tidak perlu memeriksa negatif idan jkarena mereka tidak akan pernah negatif. Karena seharusnya hanya menghasilkan Trueangka Loeschian positif, saya tidak perlu melakukan sesuatu yang istimewa untuk kasus negatif.
Brad Gilbert b2gills
9 = (3*3)+(-3*-3)+(3*-3)adalah Loeschian positif dengan i=3, j=-3; TETAPI saya tahu bahwa setiap nomor Loeschian memiliki non-negatif idan j. Jadi tidak perlu mencari angka negatif. Jadi sebenarnya kita bisa menghapus komentar itu. Maaf telah mengganggu; salahku.
Titus
@Titus memodifikasi kode untuk {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.
Brad Gilbert b2gills
1

PowerShell v2 +, 63 56 55 byte

param($k)(0..$k|%{0..($i=$_)|%{$i*($i+$_)+$_*$_}})-eq$k

Mengambil input $k , loop ke atas dua kali (loop luar $i = 0 to $k, loop dalam $j = 0 to $i), setiap iterasi menghasilkan hasil i*i + j*j + i*j(disingkat menjadi i*(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

PS C:\Tools\Scripts\golfing> (1,4,7,12,13,108,109,192,516,999|%{.\loeschian-numbers.ps1 $_})-join','
1,4,7,12,13,108,109,192,516,999

PS C:\Tools\Scripts\golfing> (2,5,10,42,101,102,128,150,501,1000|%{.\loeschian-numbers.ps1 $_})-join','

PS C:\Tools\Scripts\golfing>
AdmBorkBork
sumber
1

Perl, 54 + 1 (-n bendera) = 55 byte

for$i(0..$_){for$j(0..$_){$i*$i+$j*$j+$i*$j-$_?1:say}}

Kebutuhan -n dan -M5.010bendera untuk dijalankan:

perl -nE 'for$i(0..$_){for$j(0..$_){$i*$i+$j*$j+$i*$j-$_?1:say}}'

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:

perl -pE '$_=(1 x$_)=~/^(.*)(??{$1x(-1+length$1)})(.*)(??{$2x(-1+length$2)})(??{$1x length$2})$/'

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)

Dada
sumber
1

Dyalog APL , 19 byte

⊢∊(∘.(×-⍨2*⍨+)⍨0,⍳)

Cek apakah k ∊ ( i + j ) ² - ij , untuk setiap 0 ≤ i , jk .

     aku s k
anggota dari
    ∘.semua kombinasi dari
        × i kali j
        -⍨ dikurangi dari
        2*⍨kuadrat
        + i ditambah j
     untuk semua i dan j dalam
    0,nol yang ditambahkan ke
    bilangan bulat 1 sampai k

1000 membutuhkan 3,3 detik pada M540 saya dan bahkan lebih sedikit di TryAPL .

Adm
sumber
1

Matlab, 53 52 byte

n=input('');[a b]=ndgrid(0:n);find((a+b).^2-a.*b==n)

Pencarian 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 findfungsi yang menghasilkan solusi 47 46 byte :

n=input('');[a b]=ndgrid(0:n);(a+b).^2-a.*b==n

Satu byte disimpan berkat @ flawr

pajonk
sumber
1
(a+b).^2-a.*b==nlebih pendek.
flawr
1

C, 66 byte

Panggil f()dengan nomor untuk menguji. Fungsi mengembalikan jumlah solusi yang ditemukannya.

q,r;f(n){for(r=q=0;q++<n*n;r+=n==q%n*(q%n+q/n)+q/n*q/n);return r;}

Cobalah di ideone .

owacoder
sumber
1

Mathematica, 44 byte

MemberQ[(+##)^2-##&@@@0~Range~#~Tuples~2,#]&

Fungsi tanpa nama mengambil integer sebagai input dan kembali Trueatau False. Perintah 0~Range~#~Tuples~2membuat semua pasangan integer yang terurut baik di antara 0maupun input #. Fungsi (+##)^2-##&menghitung kuadrat dari jumlah argumennya dikurangi produk dari argumennya; ketika dipanggil pada dua argumen idan j, ini persis i^2+j^2+ijseperti yang diinginkan. Jadi fungsi itu dipanggil pada semua tupel, dan kemudian MemberQ[...,#]memeriksa apakah input adalah salah satu nilai yang dihasilkan.

Greg Martin
sumber
1

ASP, 39 + 4 = 43 byte

o:-k=I*I+J*J+I*J;I=1..k;J=1..k.:-not o.

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:

clingo -ck=999

Sampel keluaran:

SATISFIABLE

Dicoba dengan 1000:

clingo -ck=1000

Sampel keluaran:

UNSATISFIABLE

Anda dapat mencobanya di browser Anda ; sayangnya, metode ini tidak menangani flag panggilan, jadi Anda perlu menambahkan baris #const k=999untuk membuatnya berfungsi.


Kode tidak dijelaskan & dijelaskan:

v(1..k).  % predicate v(X) holds for any X in [1..k]
o:- k=I*I+J*J+I*J ; v(I) ; v(J).  % o holds if k is Loeschian.
:- not o.  % discard models where o doesn't holds (make problem unsatisfiable)
aluriak
sumber
1

PHP, 70 byte

for(;$i++<$k=$argv[1];)for($j=$i+1;$j--;)$i*$i+$j*$j+$i*$j-$k?:die(1);

mengambil input dari argumen baris perintah; keluar dengan 1nomor Loeschian, dengan yang 0lain.
Jalankan dengan-nr .

kerusakan

for(;$i++<$k=$argv[1];)     # loop $i from 1 to $k
    for($j=$i+1;$j--;)      # loop $j from $i to 0
        $i*$i+$j*$j+$i*$j-$k?   # if $i,$j,$k do not satisfy the equation, do nothing
        :die(1);                # else exit with return code 1
                            # implicit: exit with code 0
Titus
sumber