Полигоны в кубе

Question

Вдохновленный частично этим видео Mathologer о великолепных визуальных доказательствах "сжатия" и моим общим интересом к теме , эта задача заставит вас считать правильные многоугольники с целочисленными координатами в 3D.

Вам будет предоставлен ввод n, который является целым неотрицательным числом. Ваша программа должна найти количество подмножеств \$\{0, 1, \dots, n\}^3\$такие, что точки являются вершинами правильного многоугольника. То есть вершины должны быть трехмерными координатами с неотрицательными целыми числами, меньшими или равными \$n\$.

Примеры

Для \$n = 4\$, есть \$2190\$правильные многоугольники: \$1264\$равносторонние треугольники, \$810\$квадраты и \$116\$правильные шестиугольники. Пример каждого:

• Треугольник: \$(1,0,1), (0,4,0), (4,3,1)\$
• Квадрат: \$(1,0,0), (4,3,0), (3,4,4), (0,1,4)\$
• Шестиугольник: \$(1,1,0), (0,3,1), (1,4,3), (3,3,4), (4,1,3), (3,0,1)\$
  

Последовательность (с нулевым индексом) начинается:

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

Правила

Чтобы предотвратить самые наивные и неинтересные виды перебора, ваша программа должна поддерживать до \$a(5) = 6042\$на TIO .

Это задача игры в гольф , поэтому побеждает самый короткий код.

---

Сейчас он находится в Он-лайн энциклопедии целочисленных последовательностей как A338323 .

Answer 1

Python 2 , 330 313 байт

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

Попробуйте онлайн!

TIO потратил 36.893 sвычисления a(5) = 6042, так что это решение достаточно быстрое.

Даны 3 последовательные точки правильного многоугольника a,b,c, следующая точка d = c + a - b + 2*proj(b-a, c-b)(где proj- векторная проекция). Мое решение перебирает все тройки точек и определяет, образуют ли они многоугольник, используя эту формулу.

Проверено a(7) = 28400на моей машине.

-17 байт от овс