Polygone in einem Würfel

Question

Zum Teil inspiriert von diesem Mathologer-Video über wunderschöne visuelle "Schrumpf" -Beweise und meinem allgemeinen Interesse an dem Thema , werden Sie bei dieser Herausforderung regelmäßige Polygone mit ganzzahligen Koordinaten in 3D zählen.

Sie erhalten eine Eingabe n, die eine nicht negative Ganzzahl ist. Ihr Programm sollte die Anzahl der Teilmengen von \ finden$\{0, 1, \dots, n\}^3\$so dass die Punkte die Eckpunkte eines regulären Polygons sind. Das heißt, die Eckpunkte sollten 3D-Koordinaten mit nichtnegativen Ganzzahlen sein, die kleiner oder gleich \ sind$n\$.

Beispiele

Für \$n = 4\$gibt es \$2190\$reguläre Polygone: \$1264\$gleichseitige Dreiecke, \$810\$Quadrate und \$116\$regelmäßige Sechsecke. Ein Beispiel von jedem:

• Dreieck: \$(1,0,1), (0,4,0), (4,3,1)\$
• Quadrat: \$(1,0,0), (4,3,0), (3,4,4), (0,1,4)\$
• Sechseck: \$(1,1,0), (0,3,1), (1,4,3), (3,3,4), (4,1,3), (3,0,1)\$
  

Die (nullindizierte) Sequenz beginnt:

0, 14, 138, 640, 2190, 6042, 13824, 28400, 53484, 94126, 156462, 248568, 380802, 564242, 813528, 1146472, 1581936, 2143878, 2857194, 3749240, 4854942, 6210442

Regeln

Um die naivsten und uninteressantesten Arten von Brute-Forcing zu verhindern, muss Ihr Programm in der Lage sein, bis zu \ zu verarbeiten$a(5) = 6042\$auf TIO .

Dies ist eine Code-Golf- Herausforderung, daher gewinnt der kürzeste Code.

---

Dies ist jetzt in der Online -Enzyklopädie der ganzzahligen Sequenzen als A338323 .

Answer 1

Python 2 , 330 313 Bytes

import numpy as N,itertools as I
L=list
D=N.dot
n=input()
def G((a,b,c)):
 A=a
 while 1:
	u=b-a;v=c-b;d=D(v,v)
	if D(u,u)-d:return 0
	p=2*D(u,v)*v
	a,b,c=b,c,c+a-b+p/d
	if(p%d|(c<0)|(c>n)).any()or L(a)<L(A):return 0
	if L(a)==L(A):return 1
print sum(map(G,I.permutations(N.indices((n+1,)*3).reshape(3,-1).T,3)))/2

Probieren Sie es online aus!

TIO hat mit der 36.893 sBerechnung verbracht a(5) = 6042, daher ist diese Lösung gerade schnell genug.

Bei 3 aufeinanderfolgenden Punkten eines regulären Polygons a,b,cist der nächste Punkt d = c + a - b + 2*proj(b-a, c-b)(wo projist die Vektorprojektion). Meine Lösung durchläuft alle Tripel von Punkten und bestimmt anhand dieser Formel, ob sie ein Polygon bilden.

Verifiziert bis a(7) = 28400auf meinem Computer.

-17 Bytes von Ovs