Eine positive ganze Zahl k
ist eine Loeschsche Zahl, wenn
k
ausgedrückt werden kann alsi*i + j*j + i*j
füri
,j
ganze Zahlen sind .
Zum Beispiel sind die ersten positiven Loeschschen Zahlen: 1
( i=1
, j=0
); 3
( i=j=1
); 4
( i=2
, j=0
); 7
( i=2
, j=1
); 9
( i=-3
, j=3
); ... Beachten Sie, dass i
, j
für eine gegebene k
sind nicht eindeutig. Beispielsweise 9
kann auch mit i=3
, erzeugt werden j=0
.
Andere äquivalente Charakterisierungen dieser Zahlen sind:
k
ausgedrückt werden kann alsi*i + j*j + i*j
füri
,j
nicht negative ganze Zahlen. (Für jedes Paar von ganzen Zahleni
,j
gibt es ein Paar von nicht-negativen ganzen Zahlen , die die gleiche gibtk
)Es gibt eine Reihe
k
zusammenhängender Sechsecke, die auf einem sechseckigen Gitter eine Tesselation bilden (siehe Abbildungen fürk = 4
und fürk = 7
). (Aufgrund dieser Eigenschaft finden diese Nummern Anwendung in Mobilfunknetzen .)Weitere Charakterisierungen finden Sie auf der OEIS-Seite der Sequenz.
Die Herausforderung
Geben Sie bei einer positiven Ganzzahl ein wahres Ergebnis aus, wenn es sich um eine Loeschsche Zahl handelt , oder ein falsches Ergebnis, wenn dies nicht der Fall ist.
Das Programm oder die Funktion sollte Eingaben bis zu 1000
oder bis zu Datentypbeschränkungen verarbeiten (beispielsweise in weniger als einer Minute) .
Code Golf. Kürzeste Siege.
Testfälle
Die folgenden Zahlen sollten ein wahres Ergebnis liefern:
1, 4, 7, 12, 13, 108, 109, 192, 516, 999
Die folgenden Zahlen sollten ein falsches Ergebnis ausgeben:
2, 5, 10, 42, 101, 102, 128, 150, 501, 1000
quelle
i, j non-negative integers
oder9 (i=-3, j=3)
- welches ist es?Antworten:
Jelly ,
119 BytesProbieren Sie es online! oder überprüfen Sie alle Testfälle .
Hintergrund
In Elementarergebnissen zur binären quadratischen Form a² + ab + b² beweist der Autor den folgenden Satz über Löschsche Zahlen.
Wie auf der entsprechenden OEIS-Seite vermerkt , ist die Zahl 3 die einzige Primzahl, die mit 0 kongruent ist , und alle Zahlen der Form (6k + 1) sind mit kongruent , da alle Ganzzahlen mit 0 , 1 oder 2 Modulo 3 kongruent sind In 1 kann der Satz alternativ wie folgt angegeben werden.
Eine nicht negative ganze Zahl n ist genau dann eine Lösch'sche Zahl, wenn alle Primfaktoren von n , die zu 2 modulo 3 kongruent sind, gerade Exponenten haben.
Wie es funktioniert
quelle
Retina ,
6663454336 BytesTrotz des Titels "Retina" ist dies nur eine einfache .NET-Regex, die unäre Darstellungen von Loeschschen Zahlen akzeptiert .
Die Eingaben 999 und 1000 dauern weniger als eine Sekunde.
Probieren Sie es online! (Die erste Zeile aktiviert eine durch Zeilenvorschub getrennte Testsuite, und die nächsten beiden Zeilen kümmern sich der Einfachheit halber um die Konvertierung in Unary.)
Erläuterung
Die Lösung basiert auf der Klassifizierung, dass die Eingabe als
i*i + j*(i + j)
positivi
und nicht negativ geschrieben werden kannj
(da wir keine Eingabe verarbeiten müssen0
), und dasn*n
ist nur die Summe der erstenn
ungeraden ganzen Zahlen. Golfen war eine interessante Übung in Vorwärtsreferenzen.Eine "Vorwärtsreferenz" ist, wenn Sie eine Rückwärtsreferenz in die Gruppe einfügen, auf die sie verweist. Dies funktioniert natürlich nicht, wenn die Gruppe zum ersten Mal verwendet wird, da noch keine Rückverweise vorhanden sind. Wenn Sie dies jedoch in eine Schleife einfügen, erhält die Rückverweisung jedes Mal die Erfassung der vorherigen Iteration. Auf diese Weise können Sie mit jeder Iteration ein größeres Capture erstellen. Dies kann verwendet werden, um sehr kompakte Muster für Dinge wie Dreieckszahlen, Quadrate und Fibonacci-Zahlen herzustellen.
Anhand der Tatsache, dass Quadrate nur Summen der ersten
n
ungeraden Ganzzahlen sind, können wir beispielsweise eine Quadrateingabe wie die folgende zuordnen:..\1
Kann bei der ersten Iteration nicht funktionieren, da\1
noch kein Wert vorhanden ist. Also fangen wir damit an^.
, ein einzelnes Zeichen in einer Gruppe festzuhalten1
. Bei nachfolgenden Iterationen werden^.
aufgrund des Ankers keine Übereinstimmungen mehr gefunden, sondern sind jetzt..\1
gültig. Es entspricht zwei Zeichen mehr als die vorherige Iteration und aktualisiert die Erfassung. Auf diese Weise passen wir steigende ungerade Zahlen an und erhalten nach jeder Iteration ein Quadrat.Leider können wir diese Technik nicht so verwenden, wie sie ist. Nach dem Matching
i*i
müssen wir auch bekommeni
, damit wir es multiplizieren könnenj
. Ein einfache (aber lange) Weg , dies zu tun , ist die Tatsache zunutze zu machen , dass Anpassungi*i
nimmti
Iterationen, so dass wir aufgenommen habeni
Dinge in der Gruppe1
. Wir könnten jetzt Bilanzkreise verwenden , um dies zu extrahiereni
, aber wie gesagt, das ist teuer.Stattdessen habe ich mir eine andere Methode ausgedacht, um diese "Summe aufeinanderfolgender ungerader Ganzzahlen" zu schreiben
i
, die sich am Ende auch in einer Erfassungsgruppe ergibt . Natürlich ist diei
ungerade Zahl gerade2i-1
. Dies gibt uns die Möglichkeit, die Vorwärtsreferenz bei jeder Iteration nur um 1 zu erhöhen. Das ist dieser Teil:Dadurch wird
()
nur ein leeres Capture auf die Gruppe1
verschoben (Initialisierungi
auf0
). Dies entspricht^.|
in etwa der oben beschriebenen einfachen Lösung, ist jedoch|
in diesem Fall etwas schwieriger.Dann haben wir die Hauptschleife
(\1(?<1>.\1))
.\1
Entspricht der vorherigeni
und(?<1>.\1)
aktualisiert die Gruppe1
miti+1
. In Bezug auf das Neuei
haben wir nur2i-1
Charaktere gefunden. Genau das, was wir brauchen.Wenn wir fertig sind, haben wir ein Quadrat gefunden
i*i
und die Gruppe enthält1
nochi
Zeichen.Der zweite Teil ist näher an der einfachen quadratischen Übereinstimmung, die ich oben gezeigt habe. Ignorieren wir zunächst den Rückverweis auf
1
:Dies ist im Grunde dasselbe wie
(^.|..\4)*
, außer dass wir es nicht nutzen können,^
weil wir nicht am Anfang der Zeichenkette stehen. Stattdessen verwenden wir eine Bedingung, die.\1
nur dann mit der zusätzlichen übereinstimmt, wenn wir bereits group verwendet haben4
. Tatsächlich ist dies jedoch genau das gleiche. Das gibt unsj*j
.Das einzige, was fehlt, ist der
j*i
Begriff. Wir kombinieren dies mit derj*j
Tatsache, dass für diej*j
Berechnung nochj
Iterationen erforderlich sind. Bei jeder Iteration rücken wir den Cursor also umi
mit vor\1
. Wir müssen nur sicherstellen, dass das nicht in Gruppen geschrieben wird4
, da dies mit übereinstimmenden ungeraden Zahlen in Konflikt geraten würde. So kommen wir zum:quelle
CJam (
1615 Bytes)Online-Demo
Dies ist ein Block (eine "anonyme Funktion"), der Eingaben auf dem Stapel entgegennimmt und den Stapel verlässt
0
oder1
auf dem Stapel ablegt. Es wird die Charakterisierung verwendet, dass eine Zahl Loeschian ist, wenn sie keinen Primfaktor von 2 mod 3 mit ungerader Multiplizität hat.Vielen Dank an Dennis für die Einsparung von einem Byte.
quelle
Python 2, 56 Bytes
quelle
Haskell, 42 Bytes
Anwendungsbeispiel:
f 501
->False
.Versucht alle Kombinationen von
i
von0
bisk
undj
von0
bisi
.or
Gibt zurück,True
wenn die Gleichheitk==i*i+j*j+i*j
für mindestens eine der Kombinationen gilt.@flawr hat eine etwas andere Version mit der gleichen Byteanzahl gefunden:
quelle
or
, cool =) Vielleicht hast du eine Idee, wie man diese alternative Phrasierung spieltf k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]
:?Java 8, 81 Bytes
einfache, naive umsetzung. zufälligerweise denselben Code wie C # , sondern verwendet
->
statt=>
.quelle
;
. VERDAMMT!i
oder negativ zu seinj
.Python, 67 Bytes
https://repl.it/Cj6x
quelle
Jelly ,
15141312 Bytes1 Byte dank Meilen.
Probieren Sie es online!
Überprüfen Sie die kleineren Testfälle .
Ein Ratschlag beim Testen auf große Zahlen (größer als 50): Nicht.
Wahrheit ist eine positive Zahl. Falsey ist Null.
Erläuterung
quelle
Qualle ,
5643412928 Bytes2 Bytes dank Zgarb
Probieren Sie es online!
Eine Gabel meiner Gelee-Antwort .
quelle
MATL ,
1413 BytesProbieren Sie es online! Oder überprüfen Sie alle Testfälle .
Ausgänge
1
oder0
.Erläuterung
quelle
Python, 49 Bytes
Verwendet die äquivalente quadratische Form nach OEIS von
n == 3*i*i+j*j
. Überprüfen Sie, obn-3*i*i
es sich für ein Quadrat um ein perfektes Quadrat handelt,i
indem Sie die Quadratwurzel nehmen und prüfen, ob es sich um eine Ganzzahl handelt, dh 0 Modulo 1 entspricht. Dies+0j
macht es zu einer komplexen Zahl, um einen Fehler auf der Quadratwurzel eines Negativs zu vermeiden.quelle
C (GCC),
7169 Bytesquelle
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
oder negativ zu seinj
.i
undj
.k
, aber nichti
undj
. Schauen Sie sich die Beispiele genauer an.k
Kann wiei*i + j*j + i*j
füri, j
nicht negative ganze Zahlen ausgedrückt werden ." Sie schauen genauer hin.C #,
848281 BytesEine naive Lösung. 1 = wahr, 0 = falsch
quelle
VBA,
6867 BytesNaive Suche, beginnend mit einer leichten Verlangsamung für n = 1000. Excel erkennt die Nullrückgabe als falsch, alle anderen Rückgaben als wahr.
Beachten Sie, dass die Untersuchung des negativen i und j nicht erforderlich ist, da i> j> = 0 gegeben ist :
(das gleiche Ergebnis wie für i und j )
(Wenn einer negativ ist, spielt es keine Rolle, welcher) und dann
Und da sowohl (ij) als auch j nicht negativ sind, kann jede Erzeugung von Loeschschen Zahlen, die eine negative Zahl beinhalten, unter Verwendung von nicht negativen Zahlen erreicht werden.
Ein Byte gespart,
Next:Next
->Next b,a
dank Taylor Scott.quelle
i
oder negativ zu seinj
.Next:Next
zuNext b,a
:End Function
am Ende Ihrer LösungJavascript (mit externer Bibliothek - Enumerable) (63 Bytes)
Link zur Bibliothek: https://github.com/mvegh1/Enumerable Codeerklärung: Erstellen Sie einen Bereich von Ganzzahlen von 0 bis k (nennen Sie dies den "i" -Bereich), und testen Sie, ob ein "i" ein bestimmtes Prädikat erfüllt. Dieses Prädikat erstellt einen Bereich von 0 bis k (nenne dies den "j" -Bereich) und testet, ob irgendein "j" ein bestimmtes Prädikat erfüllt. Dieses Prädikat ist die Loeschsche Formel
quelle
Perl 6 ,
52 5150 BytesErläuterung:
Prüfung:
quelle
i
oder negativ zu seinj
.(0..$_ X 0..$_)
erzeugt eine leere Liste, wenn$_
kleiner als0
, so dass nicht auf Negative geprüft werden mussi
undj
diese niemals negativ sein werden. Da es nurTrue
für eine positive Loeschsche Zahl produziert werden soll, muss ich für den negativen Fall nichts Besonderes tun.9 = (3*3)+(-3*-3)+(3*-3)
ist ein positiver Loeschianer miti=3, j=-3
; ABER ich habe überlesen, dass jede Loeschsche Zahl nicht negativ isti
undj
. Das Suchen nach negativen Zahlen ist also nicht erforderlich. Also könnten wir diese Kommentare löschen. Entschuldigung für das Abhören; mein Fehler.{grep ->(\i,\j){$_==i*i+j*j+i*j},(-$_..$_ X -$_..$_)}(9)
resultiert((-3,0),(-3,3),(0,-3),(0,3),(3,-3),(3,0))
. Ehrlich gesagt habe ich es wahrscheinlich nur aus anderen Antworten übernommen.PowerShell v2 +,
635655 BytesNimmt Eingaben auf
$k
, schleift zweimal nach oben (äußere Schleife$i = 0 to $k
, innere Schleife$j = 0 to $i
), jede Iteration erzeugt das Ergebnis voni*i + j*j + i*j
(verkürzt aufi*(i+j) + j*j
). Diese Ergebnisse werden in Parens eingekapselt und als Array an übergeben-eq$k
. Dies wirkt als Filter, um nur Elemente auszuwählen, die der Eingabe entsprechen. Gibt eine Zahl ungleich Null (die Zahl zurück) für Wahr oder nichts (leer) für Falsch aus. Verarbeitet1000
in ca. 15 Sekunden auf meinem Computer.Testfälle
quelle
Perl, 54 + 1 (
-n
Flag) = 55 BytesAnforderungen
-n
und-M5.010
Flaggen zum Ausführen:Gibt ein paar Sachen aus, wenn die Nummer eine Loeschsche Nummer ist, und sonst nichts.
Diese Implementierung ist ziemlich langweilig. Hier ist eine weitere für 87 Bytes, die auf Regex basiert, nur für die Augen:
Vorsicht bei dieser Variante, da das Backtracking viel Speicherplatz beansprucht. Versuchen Sie also nicht, zu große Zahlen zu testen! (besonders Zahlen, die keine Löschianer sind)
quelle
Dyalog APL , 19 Bytes
Prüft, ob k ∊ ( i + j ) ² - ij ist , für 0 ≤ i , j ≤ k .
⊢
ist k∊
ein Glied∘.
aller Kombinationen von×
i mal j,-⍨
subtrahiert vom2*⍨
Quadrat von+
i plus j⍨
für alle i und j in0,
Null, die⍳
den ganzen Zahlen 1 bis k vorangestellt sind1000 dauert 3,3 Sekunden auf meinem M540 und noch weniger auf TryAPL .
quelle
Matlab,
5352 BytesEinfache Suche über alle Möglichkeiten.
Gibt ein leeres Array als falsch und einen nicht leeren Vektor als Wahrheitswert aus.
Betrachtet man die Matrix mit allen Nullen als falsch und die Matrix mit nicht allen Nullen als wahr, kann man die
find
Funktion entfernen, was zu einer Lösung von4746 Bytes führt :Ein Byte gespart dank @flawr
quelle
(a+b).^2-a.*b==n
ist kürzer.C 66 Bytes
f()
Mit der Nummer anrufen, um zu testen. Die Funktion gibt die Anzahl der gefundenen Lösungen zurück.Probiere es auf ideone aus .
quelle
Mathematica, 44 Bytes
Unbenannte Funktion, die eine Ganzzahl als Eingabe verwendet und
True
oder zurückgibtFalse
. Der Befehl0~Range~#~Tuples~2
erstellt alle geordneten Ganzzahlpaare zwischen0
und der Eingabe#
. Die Funktion(+##)^2-##&
berechnet das Quadrat aus der Summe ihrer Argumente minus dem Produkt ihrer Argumente. Wenn auf zwei Argumentei
und zugegriffen wirdj
, ist dies genaui^2+j^2+ij
wie gewünscht. Diese Funktion wird also für alle Tupel aufgerufen undMemberQ[...,#]
überprüft, ob die Eingabe einer der resultierenden Werte ist.quelle
ASP, 39 + 4 = 43 Bytes
Ausgabe: Das Problem ist erfüllbar, wenn k Loeschian ist.
Answer Set Programming ist eine logische Sprache, ähnlich wie Prolog. Ich benutze hier die Potassco-Implementierung , Clingo .
Die Eingabe erfolgt über Parameter (
-ck=
Länge 4 Byte). Aufrufbeispiel:Ausgabebeispiel:
Versucht mit 1000:
Ausgabebeispiel:
Sie können es in Ihrem Browser ausprobieren . Leider verarbeitet diese Methode keine Aufrufflags. Sie müssen daher die Zeile hinzufügen
#const k=999
, damit sie funktioniert.Ungolfed & Erklärter Code:
quelle
PHP, 70 Bytes
Nimmt Eingaben vom Kommandozeilenargument entgegen; Ausgänge mit
1
für Loeschian Nummer, mit0
sonst.Laufen Sie mit
-nr
.Nervenzusammenbruch
quelle