입방체의 다각형

Question

멋진 시각적 "축소"증명에 대한이 Mathologer 비디오 에서 부분적으로 영감을 받았으며 주제에 대한 저의 일반적인 관심 은 3D에서 정수 좌표가있는 정다각형을 계산하도록합니다.

n음이 아닌 정수인 input이 제공됩니다 . 프로그램에서 \ 의 하위 집합 수를 찾아야합니다.$\{0, 1, \dots, n\}^3\$점이 정다각형의 꼭지점이되도록합니다. 즉, 정점은 \ 보다 작거나 같은 음이 아닌 정수를 갖는 3D 좌표 여야합니다.$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 인덱스) 시퀀스가 ​​시작됩니다.

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 으로 Integer Sequences의 On-Line Encyclopedia에 있습니다.

Answer 1

파이썬 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내 컴퓨터에서 까지 확인했습니다 .

ovs에서 -17 바이트