Dodatnia liczba całkowita k
jest liczbą Loeschiana, jeśli
k
może być wyrażonai*i + j*j + i*j
zai
,j
liczb 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
, j
dla danego k
nie są unikatowe. Na przykład, 9
mogą być również generowane z i=3
, j=0
.
Inne równoważne cechy charakterystyczne tych liczb to:
k
może być wyrażonai*i + j*j + i*j
zai
,j
nieujemne liczby całkowite. (Dla każdej pary liczb całkowitychi
,j
istnieje parę liczb całkowitych nieujemnych, który daje takie samek
)Istnieje zestaw
k
ciągłych sześciokątów, które tworzą mozaikę na sześciokątnej siatce (patrz ilustracje pok = 4
i dlak = 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 1000
lub 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
źródło
i, j non-negative integers
lub9 (i=-3, j=3)
- który to jest?Odpowiedzi:
Galaretka ,
119 bajtówWypró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.
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
źródło
Siatkówka ,
6663454336 bajtówPomimo 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)
dodatniei
i nieujemnej
(ponieważ nie musimy obsługiwać danych wejściowych0
), in*n
jest to tylko suma pierwszychn
nieparzystych 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
n
nieparzystych liczb całkowitych, możemy dopasować kwadratowe dane wejściowe w następujący sposób:Przy pierwszej iteracji
..\1
nie może działać, ponieważ\1
nie ma jeszcze wartości. Zaczniemy więc od^.
uchwycenia pojedynczej postaci w grupie1
. W kolejnych iteracjach^.
nie pasuje już z powodu zakotwiczenia, ale teraz..\1
jest 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*i
musimy również uzyskaći
, abyśmy mogli go pomnożyćj
. Prostym (ale długim) sposobem na zrobienie tego jest skorzystanie z faktu, że dopasowywaniei*i
wymagai
iteracji, aby uchwycići
rzeczy w grupie1
. 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ż
i
grupę przechwytującą na końcu. Oczywiściei
ta nieparzysta liczba jest po prostu2i-1
. To daje nam sposób na zwiększenie referencji do przodu tylko o 1 na każdej iteracji. To jest ta część:To
()
po prostu popycha puste przechwytywanie do grupy1
(inicjowaniei
do0
). 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))
.\1
dopasowuje poprzedniei
,(?<1>.\1)
a następnie aktualizuje grupę za1
pomocąi+1
. Jeśli chodzi o nowei
, właśnie dopasowaliśmy2i-1
postacie. Właśnie tego potrzebujemy.Kiedy skończyliśmy, dopasowaliśmy trochę kwadratu,
i*i
a grupa1
nadal trzymai
postacie.Druga część jest bliższa prostemu dopasowaniu do kwadratu, który pokazałem powyżej. Zignorujmy na razie odwołanie do
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.\1
tylko wtedy, gdy już korzystaliśmy z grupy4
. Ale w rzeczywistości jest dokładnie tak samo. To nam dajej*j
.Brakuje tylko
j*i
terminu. Łączymy to zj*j
faktem, żej*j
obliczenia wciąż wymagająj
iteracji. Więc dla każdej iteracji przesuwamy kursori
o\1
. Musimy tylko upewnić się, że nie zapisujesz tego w grupie4
, ponieważ byłoby to bałaganem przy dopasowywaniu kolejnych liczb nieparzystych. W ten sposób dochodzimy do:źródło
CJam (
1615 bajtów)Demo online
Jest to blok („funkcja anonimowa”), który pobiera dane wejściowe ze stosu i opuszcza
0
lub1
stos. 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ść.
źródło
Python 2, 56 bajtów
źródło
Haskell, 42 bajty
Przykład użycia:
f 501
->False
.Próbuje wszystkich kombinacji
i
od0
dok
ij
od0
doi
.or
zwraca,True
jeśli równość obowiązujek==i*i+j*j+i*j
dla co najmniej jednej kombinacji.@flawr znalazł nieco inną wersję z tą samą liczbą bajtów:
źródł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]
?Java 8, 81 bajtów
prosta, naiwna realizacja. przypadkowo ten sam kod co C #, ale używa
->
raczej niż=>
.źródło
;
. CHOLERNY!i
lubj
.Python, 67 bajtów
https://repl.it/Cj6x
źródło
Galaretka ,
15141312 bajtów1 bajt dzięki milom.
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
źródło
Meduza ,
5643412928 bajtów2 bajty dzięki Zgarbowi
Wypróbuj online!
Widelec mojej odpowiedzi na żelki .
źródło
MATL ,
1413 bajtówWypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wyjścia
1
lub0
.Wyjaśnienie
źródło
Python, 49 bajtów
Wykorzystuje równoważną formę kwadratową podaną w OEIS dla
n == 3*i*i+j*j
. Sprawdź, czyn-3*i*i
jest to idealny kwadrat dla dowolnegoi
, 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.+0j
Sprawia, że liczbę zespoloną, aby uniknąć błędu na pierwiastek kwadratowy z negatywu.źródło
C (gcc),
7169 bajtówźródło
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
lubj
.i
ij
.k
, ale niei
ij
. Przyjrzyj się przykładom.k
można wyrazić jaki*i + j*j + i*j
dla liczb całkowitychi, j
nieujemnych ”. Państwo przyjrzeć się bliżej.C #,
848281 bajtówNaiwne rozwiązanie. 1 = prawda, 0 = fałsz
źródło
VBA,
6867 bajtówWyszukiwanie 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 :
(taki sam wynik jak dla i i j )
(jeśli jeden jest negatywny, nie ma znaczenia, który z nich), a następnie
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,a
dzięki Taylor Scott.źródło
i
lubj
.Next:Next
doNext b,a
:End Function
na końcu twojego rozwiązaniaJavaScript (przy użyciu zewnętrznej biblioteki - Enumerable) (63 bajty)
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
źródło
Perl 6 ,
52 5150 bajtówWyjaśnienie:
Test:
źródło
i
lubj
.(0..$_ X 0..$_)
produkuje pustą listę, jeśli$_
jest mniejsza niż0
, więc nie ma potrzeby sprawdzania negatywnychi
ij
ponieważ nigdy nie będą ujemne. Ponieważ ma on produkować tylkoTrue
dla dodatniej liczby Loeschiana, nie muszę robić nic specjalnego dla przypadku ujemnego.9 = (3*3)+(-3*-3)+(3*-3)
jest pozytywnym Loeschianinemi=3, j=-3
; ALE przeczytałem, że każda liczba Loeschiana ma nieujemnei
ij
. Poszukiwanie liczb ujemnych nie jest konieczne. Więc właściwie moglibyśmy usunąć te komentarze. Przepraszam za podsłuch; moja wina.{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.PowerShell v2 +,
635655 bajtówPobiera dane wejściowe
$k
, dwukrotnie zapętla w górę (pętla zewnętrzna, pętla$i = 0 to $k
wewnętrzna$j = 0 to $i
), każda iteracja generuje wyniki*i + j*j + i*j
(skracany doi*(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
źródło
Perl, 54 + 1 (
-n
flaga) = 55 bajtówPotrzeby
-n
i-M5.010
flagi do uruchomienia: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:
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)
źródło
Dyalog APL , 19 bajtów
Sprawdza, czy k ∊ ( i + j ) ² - ij , dla dowolnego 0 ≤ i , j ≤ k .
⊢
jest k∊
członkiem∘.
wszystkich kombinacji×
i razy j-⍨
odejmowanych od2*⍨
kwadratu+
i plus j⍨
dla wszystkich i i j w0,
zera poprzedzonych⍳
liczbami całkowitymi od 1 do k1000 zajmuje 3,3 sekundy na moim M540, a jeszcze mniej na TryAPL .
źródło
Matlab,
5352 bajtyProste 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ę
find
funkcji, co daje rozwiązanie4746 bajtów :Jeden bajt zapisany dzięki @flawr
źródło
(a+b).^2-a.*b==n
jest krótszy.C, 66 bajtów
Zadzwoń
f()
pod numer, aby przetestować. Funkcja zwraca liczbę znalezionych rozwiązań.Wypróbuj na ideone .
źródło
Mathematica, 44 bajty
Nienazwana funkcja przyjmująca liczbę całkowitą jako dane wejściowe i zwracająca
True
lubFalse
. Polecenie0~Range~#~Tuples~2
tworzy wszystkie uporządkowane pary liczb całkowitych zarówno pomiędzy, jak0
i na wejściu#
. Funkcja(+##)^2-##&
oblicza kwadrat sumy swoich argumentów minus iloczyn jej argumentów; po wywołaniu dwóch argumentówi
ij
jest to dokładnie takie, jakiei^2+j^2+ij
jest pożądane. Ta funkcja jest wywoływana we wszystkich krotkach, a następnieMemberQ[...,#]
sprawdza, czy dane wejściowe są jedną z wartości wynikowych.źródło
ASP, 39 + 4 = 43 bajty
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:Próbka wyjściowa:
Próbowałem z 1000:
Próbka wyjściowa:
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:
źródło
PHP, 70 bajtów
pobiera dane wejściowe z argumentu wiersza poleceń; wychodzi z
1
dla liczby Loeschiana, z0
innym.Biegnij z
-nr
.awaria
źródło