Poligon dalam kubus

Question

Terinspirasi sebagian oleh video Mathologer ini tentang bukti visual "menyusut" yang cantik , dan minat umum saya pada topik tersebut , tantangan ini akan membuat Anda menghitung poligon biasa dengan koordinat integer dalam 3D.

Anda akan diberikan masukan n, yang merupakan bilangan bulat non-negatif. Program Anda harus menemukan jumlah subset dari \$\{0, 1, \dots, n\}^3\$sedemikian rupa sehingga titik-titik tersebut merupakan simpul dari poligon beraturan. Artinya, simpul harus berupa koordinat 3D dengan bilangan bulat nonnegatif kurang dari atau sama dengan \$n\$.

Contoh

Untuk \$n = 4\$, ada \$2190\$poligon beraturan: \$1264\$segitiga sama sisi, \$810\$kotak, dan \$116\$segi enam biasa. Contoh masing-masing:

• Segitiga: \$(1,0,1), (0,4,0), (4,3,1)\$
• Persegi: \$(1,0,0), (4,3,0), (3,4,4), (0,1,4)\$
• Hexagon: \$(1,1,0), (0,3,1), (1,4,3), (3,3,4), (4,1,3), (3,0,1)\$
  

Urutan (indeks nol) dimulai:

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

Aturan

Untuk mencegah jenis pemaksaan kasar yang paling naif dan tidak menarik, program Anda harus mampu menangani hingga \$a(5) = 6042\$di TIO .

Ini adalah tantangan kode-golf , jadi kode terpendek menang.

---

Ini sekarang ada di Ensiklopedia On-Line Urutan Integer sebagai A338323 .

Answer 1

Python 2 , 330 313 byte

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

Cobalah secara online!

TIO menghabiskan waktu 36.893 smenghitung a(5) = 6042, jadi solusi ini cukup cepat.

Diketahui 3 titik berurutan dari poligon beraturan a,b,c, titik berikutnya adalah d = c + a - b + 2*proj(b-a, c-b)(di mana projproyeksi vektor). Solusi saya mengulangi semua titik tiga kali lipat dan menentukan apakah mereka membentuk poligon menggunakan rumus ini.

Diverifikasi hingga a(7) = 28400di komputer saya.

-17 byte dari ovs