Czy to numer Loeschian?

33

Dodatnia liczba całkowita kjest liczbą Loeschiana, jeśli

  • kmoże być wyrażona i*i + j*j + i*jza i, jliczb całkowitych.

Na przykład pierwsze dodatnie liczby Loeschiana to: 1( i=1, j=0); 3( i=j=1); 4( i=2, j=0); 7( i=2, j=1); 9( i=-3, j=3); ... Zauważ, że i, jdla danego knie są unikatowe. Na przykład, 9mogą być również generowane z i=3, j=0.

Inne równoważne cechy charakterystyczne tych liczb to:

  • kmoże być wyrażona i*i + j*j + i*jza i, jnieujemne liczby całkowite. (Dla każdej pary liczb całkowitych i, jistnieje parę liczb całkowitych nieujemnych, który daje takie same k)

  • Istnieje zestaw kciągłych sześciokątów, które tworzą mozaikę na sześciokątnej siatce (patrz ilustracje po k = 4i dla k = 7). (Ze względu na tę właściwość liczby te znajdują zastosowanie w mobilnych sieciach komunikacji komórkowej .)

  • Zobacz więcej charakteryzacji na stronie OEIS sekwencji.

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą , wyprowadzaj prawdziwy wynik, jeśli jest to liczba Loeschiana , lub wynik fałszu w przeciwnym razie.

Program lub funkcja powinna obsługiwać (powiedzmy w mniej niż minutę) dane wejściowe do 1000lub do ograniczeń typu danych.

Kod golfa. Najkrótsze wygrane.

Przypadki testowe

Poniższe liczby powinny dać prawdziwy wynik:

1, 4, 7, 12, 13, 108, 109, 192, 516, 999

Poniższe liczby powinny dać wynik fałszowania:

2, 5, 10, 42, 101, 102, 128, 150, 501, 1000
Luis Mendo
źródło
Powiązane (jak zauważył @PeterTaylor)
Luis Mendo
uwaga dla algorytmu brutalnej siły: jeśli wykonasz iterację do √k, zredukujesz złożoność algorytmu z O (n²) do O (n), kosztem niektórych bajtów c;
Rod
i, j non-negative integerslub 9 (i=-3, j=3)- który to jest?
Tytus
1
@Titus Oh teraz widzę. Dla każdej pary liczb całkowitych i, j istnieje para nieujemna, która daje to samo k
Luis Mendo

Odpowiedzi:

17

Galaretka , 11 9 bajtów

ÆF‘%3,2ḄȦ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

W elementarnych wynikach binarnej postaci kwadratowej a² + ab + b² autor udowadnia następujące twierdzenie o liczbach Löschiana.

Twierdzenie 16. Koniecznym i wystarczającym warunkiem każdej nieujemnej liczby całkowitej, która ma być w postaci a² + ab + b², jest to, że w jej rozkładzie na czynniki pierwsze wszystkie liczby inne niż 3 , które nie są w postaci (6k + 1), mają nawet wykładniki.

Jak zauważono na odpowiedniej stronie OEIS , ponieważ wszystkie liczby całkowite są zgodne z 0 , 1 lub 2 modulo 3 , liczba 3 jest jedyną liczbą pierwszą, która jest zgodna z 0 , a wszystkie liczby postaci (6k + 1) są zgodne z 1 , twierdzenie to można sformułować alternatywnie w następujący sposób.

Nieujemna liczba całkowita n jest liczbą Löschiana tylko wtedy, gdy wszystkie czynniki pierwsze n zgodne z 2 modulo 3 mają nawet wykładniki wykładnicze.

Jak to działa

Æ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
źródło
17

Siatkówka , 66 63 45 43 36 bajtów

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

Pomimo tytułu Retina, jest to zwykły regex .NET, który akceptuje jednoargumentowe przedstawienie liczb Loeschiana.

Wejścia 999 i 1000 zajmują znacznie mniej niż sekundę.

Wypróbuj online! (Pierwszy wiersz włącza pakiet testowy oddzielony od linii, a kolejne dwa zajmują się konwersją na unary dla wygody).

Wyjaśnienie

Rozwiązanie opiera się na klasyfikacji, według której dane wejściowe można zapisać jako i*i + j*(i + j)dodatnie ii nieujemne j(ponieważ nie musimy obsługiwać danych wejściowych 0), i n*njest to tylko suma pierwszych nnieparzystych liczb całkowitych. Gra w golfa była ciekawym ćwiczeniem w referencjach.

„Odwołanie do przodu” ma miejsce, gdy umieścisz odsyłacz wsteczny w grupie, do której się odnosi. Oczywiście to nie działa, gdy grupa jest używana za pierwszym razem, ponieważ nie ma jeszcze żadnych odnośników, ale jeśli umieścisz to w pętli, wówczas odniesienie wsteczne pobierze za każdym razem poprzednią iterację. To z kolei pozwala budować większe przechwytywanie z każdą iteracją. Może to być wykorzystane do stworzenia bardzo zwartych wzorów dla takich rzeczy, jak liczby trójkątne, kwadraty i liczby Fibonacciego.

Jako przykład, wykorzystując fakt, że kwadraty są tylko sumami pierwszych nnieparzystych liczb całkowitych, możemy dopasować kwadratowe dane wejściowe w następujący sposób:

(^.|..\1)+$

Przy pierwszej iteracji ..\1nie może działać, ponieważ \1nie ma jeszcze wartości. Zaczniemy więc od ^.uchwycenia pojedynczej postaci w grupie 1. W kolejnych iteracjach ^.nie pasuje już z powodu zakotwiczenia, ale teraz ..\1jest poprawny. Dopasowuje dwa znaki więcej niż w poprzedniej iteracji i aktualizuje przechwytywanie. W ten sposób dopasowujemy rosnące liczby nieparzyste, uzyskując kwadrat po każdej iteracji.

Niestety nie możemy obecnie korzystać z tej techniki. Po dopasowaniu i*imusimy również uzyskać i, abyśmy mogli go pomnożyć j. Prostym (ale długim) sposobem na zrobienie tego jest skorzystanie z faktu, że dopasowywanie i*iwymaga iiteracji, aby uchwycić irzeczy w grupie 1. Możemy teraz użyć grup bilansujących, aby to wyodrębnić i, ale tak jak powiedziałem, jest to drogie.

Zamiast tego wymyśliłem inny sposób na zapisanie tej „sumy kolejnych nieparzystych liczb całkowitych”, która daje również igrupę przechwytującą na końcu. Oczywiście ita nieparzysta liczba jest po prostu 2i-1. To daje nam sposób na zwiększenie referencji do przodu tylko o 1 na każdej iteracji. To jest ta część:

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

To ()po prostu popycha puste przechwytywanie do grupy 1(inicjowanie ido 0). Jest to prawie równoważne z ^.|powyższym prostym rozwiązaniem, ale użycie |w tym przypadku byłoby nieco trudniejsze.

Następnie mamy główną pętlę (\1(?<1>.\1)). \1dopasowuje poprzednie i, (?<1>.\1)a następnie aktualizuje grupę za 1pomocą i+1. Jeśli chodzi o nowe i , właśnie dopasowaliśmy 2i-1postacie. Właśnie tego potrzebujemy.

Kiedy skończyliśmy, dopasowaliśmy trochę kwadratu, i*ia grupa 1nadal trzyma ipostacie.

Druga część jest bliższa prostemu dopasowaniu do kwadratu, który pokazałem powyżej. Zignorujmy na razie odwołanie do 1:

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

Jest to w zasadzie to samo co (^.|..\4)*, z tym wyjątkiem, że nie możemy z nich skorzystać, ^ponieważ nie jesteśmy na początku łańcucha. Zamiast tego używamy warunkowego, aby dopasować dodatkowe .\1tylko wtedy, gdy już korzystaliśmy z grupy 4. Ale w rzeczywistości jest dokładnie tak samo. To nam daje j*j.

Brakuje tylko j*iterminu. Łączymy to z j*jfaktem, że j*jobliczenia wciąż wymagają jiteracji. Więc dla każdej iteracji przesuwamy kursor io \1. Musimy tylko upewnić się, że nie zapisujesz tego w grupie 4, ponieważ byłoby to bałaganem przy dopasowywaniu kolejnych liczb nieparzystych. W ten sposób dochodzimy do:

(\1(.(?(4).\1)))*
Martin Ender
źródło
2
Im więcej razy to czytam, tym mniej rozumiem. Naprawdę chcę wiedzieć, że wiele wyrażeń regularnych
Javier Diaz
@JavierDiaz Istnieje szereg postów wyjaśniających odniesienia do przodu na temat przepełnienia stosu, opartych na wyrażeniach regularnych Java. Przykłady są prawdopodobnie nieco prostsze.
Martin Ender,
13

CJam ( 16 15 bajtów)

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

Demo online

Jest to blok („funkcja anonimowa”), który pobiera dane wejściowe ze stosu i opuszcza 0lub 1stos. Wykorzystuje charakterystykę, że liczba to Loeschian iff, nie ma ona współczynnika liczby podstawowej równej 2 mod 3 z nieparzystą wielokrotnością.

Dzięki Dennisowi za jednobajtową oszczędność.

Peter Taylor
źródło
Wow, fajna charakterystyka!
Luis Mendo,
6

Python 2, 56 bajtów

lambda n:any(n==i*i%n+i/n*(i/n+i%n)for i in range(2*n*n))
orlp
źródło
6

Haskell, 42 bajty

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

Przykład użycia: f 501-> False.

Próbuje wszystkich kombinacji iod 0do ki jod 0do i. orzwraca, Truejeśli równość obowiązuje k==i*i+j*j+i*jdla co najmniej jednej kombinacji.

@flawr znalazł nieco inną wersję z tą samą liczbą bajtów:

f k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]
nimi
źródło
Nie wiedziałem o or, super =) Być może masz pomysł jak golf tej alternatywnej frazowanie: f k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]?
flawr
@flawr: nie, nie mam pojęcia, jak zagrać w golfa w dalszej wersji. Jeśli nie masz nic przeciwko, dodam to do mojej odpowiedzi jako alternatywną wersję.
nimi
5

Java 8, 81 bajtów

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;};

prosta, naiwna realizacja. przypadkowo ten sam kod co C #, ale używa ->raczej niż =>.

Justin
źródło
Trzy bajty mniej, ponieważ można pominąć nawiasy klamrowe i zakończenie ;. CHOLERNY!
TheLethalCoder
@TheLethalCoder Właściwie nie mogę, popełniłem błąd - ta sama liczba bajtów, co C #.
Justin
I tak sprawia, że ​​czuję się lepiej :)
TheLethalCoder
To nie wydaje się testować negatywnie ilub j.
Tytus
4

Galaretka , 15 14 13 12 bajtów

1 bajt dzięki milom.

²S+P
‘ṗ2’Ç€i

Wypróbuj online!

Sprawdź mniejsze przypadki testowe .

Kilka rad podczas testowania na duże liczby (większe niż 50): nie.

Prawda jest liczbą dodatnią. Falsey wynosi zero.

Wyjaśnienie

‘ṗ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
Leaky Nun
źródło
Tied (for) now ... :-)
Luis Mendo
Czy powinniśmy wykorzystać charakterystykę Piotra ...?
Luis Mendo,
@LuisMendo To wydaje się interesujące, ale wydaje się, że byłoby dłużej
Leaky Nun
Nie sądzę, że musisz go spłaszczyć. Twój link pomocnika już mapuje od krotek do liczb całkowitych.
mile
@miles To sprytne, dzięki.
Leaky Nun
3

MATL , 14 13 bajtów

t:0hU&+HM&*+m

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjścia 1lub 0.

Wyjaśnienie

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
źródło
Czy właśnie grałeś w golfa w galaretkę?
Leaky Nun
@LeakyNun Zobaczmy, jak długo to trwa. Może nieco opóźnię wyjaśnienie kodu :-P
Luis Mendo
Nie. - - - - -
Leaky Nun
Twoja kolej - - -
Leaky Nun
@LeakyNun Aw :-( Teraz mogę dodać wyjaśnienie :-)
Luis Mendo
3

Python, 49 bajtów

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

Wykorzystuje równoważną formę kwadratową podaną w OEIS dla n == 3*i*i+j*j. Sprawdź, czy n-3*i*ijest to idealny kwadrat dla dowolnego i, biorąc jego pierwiastek kwadratowy i sprawdzając, czy jest liczbą całkowitą, tj. Równa się 0 modulo 1. Zauważ, że Python dokładnie oblicza pierwiastki kwadratowe z doskonałych kwadratów, bez błędu zmiennoprzecinkowego. +0jSprawia, że liczbę zespoloną, aby uniknąć błędu na pierwiastek kwadratowy z negatywu.

xnor
źródło
3

C (gcc), 71 69 bajtów

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
źródło
69 bajtów: 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,
To nie wydaje się testować negatywnie ilub j.
Tytus
@Titus Pytanie dyktuje nieujemne ii j.
orlp
pozytywne k, ale nie ii j. Przyjrzyj się przykładom.
Tytus
@Titus Cytując wyzwanie: kmożna wyrazić jak i*i + j*j + i*jdla liczb całkowitych i, j nieujemnych ”. Państwo przyjrzeć się bliżej.
orlp
2

C #, 84 82 81 bajtów

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;};

Naiwne rozwiązanie. 1 = prawda, 0 = fałsz

TheLethalCoder
źródło
2

VBA, 68 67 bajtów

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

Wyszukiwanie naiwne, zaczynając nieco zwalniać dla n = 1000. Excel rozpoznaje zerowy zwrot jako fałsz, wszystkie pozostałe zwroty jako prawdziwe.

Zauważ, że badanie ujemnych i i j nie jest potrzebne, ponieważ biorąc pod uwagę i> j> = 0 :

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

(taki sam wynik jak dla i i j )

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

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

(jeśli jeden jest negatywny, nie ma znaczenia, który z nich), a następnie

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

A ponieważ zarówno (ij), jak i j są nieujemne, każde generowanie liczb Loeschiana obejmujące liczbę ujemną można osiągnąć za pomocą liczb nieujemnych.


Zapisano bajt Next:Next-> Next b,adzięki Taylor Scott.

Joffan
źródło
To nie wydaje się testować negatywnie ilub j.
Tytus
Zobacz pierwszy punkt w części „Inne równoważne charakterystyki”. Pamiętaj, że wszystkie przypadki testowe działają poprawnie. Dodam matematyczne uzasadnienie do mojej odpowiedzi (jeśli mogę).
Joffan
Wybacz, moja wina. Przeczytałem, że to nie jest konieczne.
Tytus
@Joffan można skondensować Next:NextdoNext b,a
Taylor Scott
@Joffan znów patrzy na twoje rozwiązanie, może dlatego, że brakuje go :End Functionna końcu twojego rozwiązania
Taylor Scott
1

JavaScript (przy użyciu zewnętrznej biblioteki - Enumerable) (63 bajty)

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

Link do biblioteki: https://github.com/mvegh1/Enumerable Objaśnienie kodu: Utwórz zakres liczb całkowitych od 0 do k (nazwij to zakresem „i”) i sprawdź, czy jakieś „i” spełnia określone orzeczenie. Predykat tworzy zakres od 0 do k (nazwij to zakresem „j”) i sprawdza, czy jakieś „j” spełnia określone orzeczenie. Ten predykat to formuła loeschiańska

enter image description here

applejacks01
źródło
1

Perl 6 ,  52 51  50 bajtów

->\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..$_)}

Wyjaśnienie:

{
  # 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..$_ )
}

Test:

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
źródło
To nie wydaje się testować negatywnie ilub j.
Tytus
@Titus (0..$_ X 0..$_)produkuje pustą listę, jeśli $_jest mniejsza niż 0, więc nie ma potrzeby sprawdzania negatywnych ii jponieważ nigdy nie będą ujemne. Ponieważ ma on produkować tylko Truedla dodatniej liczby Loeschiana, nie muszę robić nic specjalnego dla przypadku ujemnego.
Brad Gilbert b2gills,
9 = (3*3)+(-3*-3)+(3*-3)jest pozytywnym Loeschianinem i=3, j=-3; ALE przeczytałem, że każda liczba Loeschiana ma nieujemne ii j. Poszukiwanie liczb ujemnych nie jest konieczne. Więc właściwie moglibyśmy usunąć te komentarze. Przepraszam za podsłuch; moja wina.
Tytus
@Titus modyfikuje kod w celu uzyskania {grep ->(\i,\j){$_==i*i+j*j+i*j},(-$_..$_ X -$_..$_)}(9)wyników ((-3,0),(-3,3),(0,-3),(0,3),(3,-3),(3,0)). Szczerze mówiąc, prawdopodobnie właśnie dostosowałem go do innych odpowiedzi.
Brad Gilbert b2gills
1

PowerShell v2 +, 63 56 55 bajtów

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

Pobiera dane wejściowe $k, dwukrotnie zapętla w górę (pętla zewnętrzna, pętla $i = 0 to $kwewnętrzna $j = 0 to $i), każda iteracja generuje wynik i*i + j*j + i*j(skracany do i*(i+j) + j*j). Wyniki te są enkapsulowane w parens i przekazywane jako tablica do -eq$k. Działa to jak filtr do wybierania tylko elementów, które są równe wejściowi. Zwraca wartość niezerową (liczba z powrotem) dla prawdy lub nic (pustą) dla falsey. Procesy1000 w ciągu około 15 sekund na moim komputerze.

Przypadki testowe

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
źródło
1

Perl, 54 + 1 (-n flaga) = 55 bajtów

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

Potrzeby -ni-M5.010 flagi do uruchomienia:

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

Wysyła niektóre rzeczy, jeśli liczba jest liczbą Loeschiana, i nic poza tym.

Ta implementacja jest dość nudna, więc oto kolejna, dla 87 bajtów, oparta na wyrażeniach regularnych, tylko dla oczu:

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

Ostrożnie z tym, ponieważ powrót będzie zużywał dużo pamięci, więc nie próbuj testować liczb zbyt dużych! (szczególnie liczby, które nie są Loeschianami)

Dada
źródło
1

Dyalog APL , 19 bajtów

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

Sprawdza, czy k ∊ ( i + j ) ² - ij , dla dowolnego 0 ≤ i , jk .

    jest k
członkiem
    ∘.wszystkich kombinacji
        × i razy j
        -⍨ odejmowanych od
        2*⍨kwadratu
        + i plus j
     dla wszystkich i i j w
    0,zera poprzedzonych
    liczbami całkowitymi od 1 do k

1000 zajmuje 3,3 sekundy na moim M540, a jeszcze mniej na TryAPL .

Adám
źródło
1

Matlab, 53 52 bajty

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

Proste wyszukiwanie wszystkich możliwości.
Zwraca pustą tablicę jako fałsz, a niepusty wektor jako wartość prawdziwości.

Uznając matrycę zera zerowego za falsy i macierz zera zerowego za prawdę, możemy pozbyć się findfunkcji, co daje rozwiązanie 47 46 bajtów :

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

Jeden bajt zapisany dzięki @flawr

pajonk
źródło
1
(a+b).^2-a.*b==njest krótszy.
flawr
1

C, 66 bajtów

Zadzwoń f()pod numer, aby przetestować. Funkcja zwraca liczbę znalezionych rozwiązań.

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;}

Wypróbuj na ideone .

owacoder
źródło
1

Mathematica, 44 bajty

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

Nienazwana funkcja przyjmująca liczbę całkowitą jako dane wejściowe i zwracająca Truelub False. Polecenie 0~Range~#~Tuples~2tworzy wszystkie uporządkowane pary liczb całkowitych zarówno pomiędzy, jak 0i na wejściu #. Funkcja (+##)^2-##&oblicza kwadrat sumy swoich argumentów minus iloczyn jej argumentów; po wywołaniu dwóch argumentów ii jjest to dokładnie takie, jakie i^2+j^2+ijjest pożądane. Ta funkcja jest wywoływana we wszystkich krotkach, a następnie MemberQ[...,#]sprawdza, czy dane wejściowe są jedną z wartości wynikowych.

Greg Martin
źródło
1

ASP, 39 + 4 = 43 bajty

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

Wyjście: problem jest satysfakcjonujący, jeśli K jest Loeschian.

Programowanie zestawu odpowiedzi jest językiem logicznym, podobnym do prologu. Używam tutaj implementacji Potassco , clingo .

Dane wejściowe są pobierane z parametrów ( -ck=ma długość 4 bajtów). Przykład połączenia:

clingo -ck=999

Próbka wyjściowa:

SATISFIABLE

Próbowałem z 1000:

clingo -ck=1000

Próbka wyjściowa:

UNSATISFIABLE

Możesz spróbować w przeglądarce ; niestety ta metoda nie obsługuje flag wywołań, więc musisz dodać linię #const k=999, aby działała.


Kod niepoznany i wyjaśniony:

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
źródło
1

PHP, 70 bajtów

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

pobiera dane wejściowe z argumentu wiersza poleceń; wychodzi z 1dla liczby Loeschiana, z 0innym.
Biegnij z-nr .

awaria

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
Tytus
źródło