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

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.

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)))*

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ść.

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))

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]

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ż =>.

Python, 67 bajtów

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

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

Meduza , 56 43 41 29 28 bajtów

2 bajty dzięki Zgarbowi

p
n    <
+`/
`1*
/
+
&*r&;>i

Wypróbuj online!

Widelec mojej odpowiedzi na żelki .

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

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.

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

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

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) ² + (-i) (- j) + (-j) ² = i ² + ij + j ²

(taki sam wynik jak dla i i j )

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

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

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

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

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.

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

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

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>

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)

Dyalog APL , 19 bajtów

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

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

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

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

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 .

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.

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)

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