Definitionen:
- Ein Dreieck wird als rechtwinkliges Dreieck betrachtet, wenn einer der Innenwinkel genau 90 Grad beträgt.
- Eine Zahl wird als rational angesehen, wenn sie durch ein Verhältnis von ganzen Zahlen dargestellt werden kann, dh
p/q
wenn beidep
undq
ganze Zahlen sind. - Eine Zahl
n
ist eine kongruente Zahl, wenn es ein rechtwinkliges Flächendreieck gibt,n
in dem alle drei Seiten rational sind. - Dies ist OEIS A003273 .
Herausforderung
Dies ist eine Entscheidungsproblemherausforderung . Ausgeben x
eines eindeutigen und konsistenten Werts, wenn x
es sich um eine kongruente Zahl handelt, und eines separaten eindeutigen und konsistenten Werts, wenn x
es sich nicht um eine kongruente Zahl handelt. Die Ausgabewerte müssen in Ihrer Sprache nicht unbedingt wahr oder falsch sein.
Sonderregel
Für die Zwecke dieser Herausforderung können Sie davon ausgehen, dass die Vermutung von Birch und Swinnerton-Dyer wahr ist. Wenn Sie alternativ die Vermutung von Birch und Swinnerton-Dyer beweisen können, fordern Sie Ihren 1.000.000-Dollar-Millennium-Preis an. ;-)
Beispiele
(Verwendung True
für kongruente Zahlen und False
sonstiges).
5 True
6 True
108 False
Regeln und Erläuterungen
- Die Ein- und Ausgabe kann auf jede bequeme Weise erfolgen .
- Sie können das Ergebnis an STDOUT drucken oder als Funktionsergebnis zurückgeben. Bitte geben Sie bei Ihrer Übermittlung an, welche Werte die Ausgabe annehmen kann.
- Es ist entweder ein vollständiges Programm oder eine Funktion zulässig.
- Standardlücken sind verboten.
- Dies ist Codegolf, daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.
code-golf
decision-problem
number-theory
AdmBorkBork
quelle
quelle
Antworten:
R
179173142141137135134 BytesWenn Sie dieselben Argumente verwenden, die auf dem Satz von Tunnell basieren , wird ein
0
if zurückgegeben,n
das nicht kongruent ist,1
andernfalls. (Ich habe lange gebraucht, um die Einschränkung für die Bedingung zu erkennen, die nur für ganze Zahlen ohne Quadrate gilt .)Probieren Sie es online aus
Verbesserungen von Arnaud und Giuseppe (der letzte Code ist hauptsächlich der von Guiseppe!), Mit -3 dank Robin
Syntaxanalyse:
mit dem Satz von Tunnell , dass n genau dann kongruent ist, wenn die Anzahl der ganzzahligen Lösungen zu 2x² + y² + 8z² = n doppelt so groß ist wie die Anzahl der ganzzahligen Lösungen zu 2x² + y² + 32z² = n, wenn n ungerade ist und die Anzahl von ganzzahligen Lösungen auf 8x² + y² + 16z² = n ist doppelt so viel wie die Anzahl von ganzzahligen Lösungen auf 8x² + y² + 64z² = n, wenn n gerade ist.
quelle
@[username]
... Ich nehme an, Sie wurden von Robin Ryder in den Code-Golf gezogen?-n:n
? Ich habe das Theorem von Tunnel nicht gelesen, aber es scheint mir, dassn:0
es für -1 Byte genauso gut funktionieren würde ... Außerdem, Profi-Tipp, wenn Sie die "Link" -Taste oben auf TIO drücken, werden Sie nett Formate zum Kopieren und Einfügen in PPCG :-) EDIT: Ich sehe, es gibt einige Fälle, in denenn:0
nicht funktioniert.Rust - 282 Bytes
Siehe auch:
korrigiert gerade / ungerade, danke @Level River St
quelle
C ++ (gcc) ,
251234 BytesVielen Dank an @arnauld für den Hinweis auf einen dummen Tippfehler von meiner Seite.
-17 Bytes dank @ceilingcat.
Probieren Sie es online!
Gibt 1 zurück, wenn
n
kongruent ist, andernfalls 0.quelle
JavaScript (ES7), 165 Byte
Ähnlich wie die Antwort von @ NeilA. Basiert diese auf dem Satz von Tunnell und geht daher davon aus, dass die Vermutung von Birch und Swinnerton-Dyer wahr ist.
Gibt einen Booleschen Wert zurück.
Probieren Sie es online!
Wie?
quelle
Ruby , 126 Bytes
Probieren Sie es online!
fanden einen Ort zum Initialisieren
t=1
und Erweitern der Liste der Quadrate in ein Triplett, anstattq
zusätzliche Kopien zu erstellen.Ruby , 129 Bytes
Probieren Sie es online!
Verwendet den Satz von Tunnell wie die anderen Antworten. Ich verwende eine einzelne Gleichung wie folgt.
Wir prüfen die Fälle
k=8
undk=32
, ob es doppelt so viele Lösungen gibtk=8
wiek=32
. Dies geschieht durch Hinzufügenk-16
zut
jedem Zeitpunkt, an dem wir eine Lösung finden. Dies ist entweder +16 im Fallk=32
oder -8 im Fallk=8
. Insgesamt ist die Zahl kongruent, wenn siet
mit dem Anfangswert am Ende der Funktion übereinstimmt.Es ist notwendig, alle Lösungen für die Testgleichung zu finden. Ich sehe viele Antworten zwischen +/-
sqrt n
. Es ist vollkommen in Ordnung, auch außerhalb dieser Grenzen zu testen, ob der Code dadurch kürzer wird, aber es werden keine Lösungen gefunden, da die linke Seite der Gleichung überschritten wirdn
. Das, was ich am Anfang vermisst habe, ist, dass Negatives und Positivesx,y,z
getrennt betrachtet werden. Somit-3,0,3
ergeben sich drei Quadrate9,0,9
und alle Lösungen müssen separat gezählt werden (0 muss einmal gezählt werden und9
muss zweimal gezählt werden.)Ungolfed Code
quelle