정의 :
- 삼각형은 고려 직각 삼각형 내부 각도 중 하나가 정확히 90 ° 인 경우.
- 숫자는 고려 합리적 이 정수의 비율로 표현, 즉, 될 수 있다면
p/q, 어디에 둘p과q정수입니다. - 세 변이 모두 합리적인 영역의 오른쪽 삼각형이있는 경우 숫자
n는 일치하는 숫자n입니다. - OEIS A003273 입니다.
도전
이것은 의사 결정 문제 입니다. 입력 번호가 주어지면 일치하는 숫자 인 x경우 고유하고 일관된 값을 출력하고 x일치하는 숫자 x가 아닌 경우 별도의 고유하고 일관된 값을 출력하십시오 . 출력 값이 반드시 귀하의 언어에서 진실 / 거짓 일 필요는 없습니다.
특별 규칙
이 도전의 목적으로, 당신은 Birch와 Swinnerton-Dyer 추측 이 참 이라고 가정 할 수 있습니다 . 또는 Birch and Swinnerton-Dyer 추측을 증명할 수 있다면 $ 1,000,000 Millennium 상을 받으십시오. 😉
예
( True동일한 숫자 등을 위해 사용 False).
5 True
6 True
108 False
규칙 및 설명
답변
R, 179 173 142 141 137 135 134 바이트
Tunnell ‘s Theorem 에 기반한 동일한 인수를 사용하여 0if n가 적합하지 않은 경우 와 1그렇지 않은 경우를 반환합니다 . ( 제곱없는 정수 에만 적용 되는 조건 의 제약 조건을 찾는 데 시간이 오래 걸렸습니다 .)
function(n){b=(-n:n)^2
for(i in b^!!b)n=n/i^(!n%%i)
P=1+n%%2
o=outer
!sum(!o(y<-o(8/P*b,2*b,"+")/P-n,z<-16/P*b,"+"),-2*!o(y,4*z,"+"))}
Arnaud 와 Giuseppe의 개선 사항 (최종 코드는 대부분 Guiseppe ‘s!)- Robin 덕분에 -3
구문 분석 :
for(i in b[b>0])n=n/i^(!n%%i) #eliminates all square divisors of n
P=2^(n%%2) #n odd (2) or even (1)
o=outer #saves 3 bytes
o(8/P*b,2*b,"+")/P-n #all sums of (8/P)x^2+(2/P)*y^2-n
o(...,16/P*b,"+") #all sums of above and (16/P)*z^2
o(...,4*z,"+")) #all sums of above and (64/P)*z^2
!o(...,4*z,"+")) #all sums of above equal to zero
!sum(!...,2*!...) #are zeroes twice one another (Tunnell)
함께 Tunnell 정리는 그 N 알리는 합동 경우에만, 정수 솔루션의 수 2x² + y² + 8z² = n은 두 배 2x² 정수 솔루션의 개수 + y² + 32z² = N, n은 홀수 번호인지 n이 짝수이면 8x² + y² + 16z² = n에 대한 정수 솔루션의 수는 8x² + y² + 64z² = n에 대한 정수 솔루션 수의 두 배입니다.
답변
녹-282 바이트
fn is(mut n:i64)->bool{let(mut v,p)=(vec![0;4],n as usize%2);while let Some(l)=(2..n).filter(|i|n%(i*i)==0).nth(0){n/=l*l;}for x in -n..=n{for y in -n..=n{for z in -n..=n{for i in 0..2{if n-6*x*x*(n+1)%2==2*x*x+(2-n%2)*(y*y+(24*i as i64+8)*z*z){v[2*p+i]+=1};}}}}v[2*p]==2*v[2*p+1]}
- 내가 실제로 이해하지 못하지만 어쨌든 효과가있는 Jerrold B. Tunnell 의 정리를 사용하십시오 .
- Tunnell의 정리 아래의 논문에서 square-frees에 대해서만 설명되었으므로 n을 모든 제곱 인수로 나누면 ‘제곱없는’이됩니다.
- 모든 합동 수에 사각형을 곱하면 더 큰 합동 수가 생성되고 그 반대도 가능하기 때문에 이것이 효과가 있다고 생각합니다. 더 작은 수를 테스트함으로써 더 큰 수를 검증 할 수 있습니다.이 경우에는 n입니다. (제거 된 모든 사각형을 곱하여 하나의 큰 사각형을 만들 수 있음).
-
if n is odd, test if n = 2x2+y2+32z2 and/or 2x2+y2+8z2
if n is even, test if n = 8x2+2y2+64z2 and/or 8x2+2y2+16z2- 코드 자체에서 짝수 / 홀수에 대해 모듈로를 사용하여 루프 내에서 네 개의 방정식이 하나로 스무 싱되었습니다.
- 어떤 방정식이 n과 일치하는지 집계 계산
- 루핑 후, Tallies의 비율을 테스트하십시오 (Tunnell 당)
참조 :
- 원하는 경우 Rust Playground에서 코드를 사용해보십시오
- Bilkent University 웹 사이트의 Guy Henniart가 Franz Lemmermeyer로 번역 한 Congruent Numbers, Elliptic Curves and Modular Forms
- 코네티컷 대학교 웹 사이트 Keith Conrad의 합동 수 문제
- 일치하는 숫자, Brian Hayes, bit-palyer.org 블로그
@Level River St 덕분에 짝수 / 홀수 수정
답변
C ++ (gcc) , 251234 바이트
내 부분에 바보 같은 오타를 지적 한 @arnauld에게 감사드립니다.
@ceilingcat 덕분에 -17 바이트.
#import<cmath>
int a(int n){int s=sqrt(n),c,x=-s,y,z,i=1,X;for(;++i<n;)for(;n%(i*i)<1;n/=i*i);for(;x++<s;)for(y=-s;y++<s;)for(z=-s;z++<s;c+=n&1?2*(n==X+24*z*z)-(n==X):2*(n==4*x*x+2*X+48*z*z)-(n/2==2*x*x+X))X=2*x*x+y*y+8*z*z;return!c;}n일치하는 경우 1을 , 그렇지 않으면 0을 반환합니다.
s2q
또한 합리적입니다 (알고리즘은 일부 제곱 포함 숫자에서 깨지는 것 같습니다.
답변
자바 스크립트 (ES7), 165 바이트
@NeilA.의 답변 과 마찬가지로 이것은 Tunnell의 정리를 기반으로 하므로 Birch 및 Swinnerton-Dyer 추측이 사실이라고 가정합니다.
부울 값을 반환합니다.
n=>(r=(g=i=>i<n?g(i+!(n%i**2?0:n/=i*i)):n**.5|0)(s=2),g=(C,k=r)=>k+r&&g(C,k-1,C(k*k)))(x=>g(y=>g(z=>s+=2*(n==(X=(n&1?2:8)*x+(o=2-n%2)*y)+o*32*z)-(n==X+o*8*z))))|s==2방법?
n
n′
r=⌊n′⌋
s
2
r = ( // we will eventually save isqrt(n) into r
g = i => // g = recursive function taking an integer i
i < n ? // if i is less than n:
g(i + !( // do a recursive call with either i or i + 1
n % i**2 ? // if n is not divisible by i²:
0 // yield 0 and therefore increment i
: // else:
n /= i * i // divide n by i² and leave i unchanged
)) // end of recursive call
: // else:
n ** .5 | 0 // stop recursion and return isqrt(n)
)(s = 2) // initial call to g with i = s = 2g
C
k2
−r<k≤r
g = (C, k = r) => // C = callback function, k = counter initialized to r
k + r && // if k is not equal to -r:
g( // do a recursive call:
C, // pass the callback function unchanged
k - 1, // decrement k
C(k * k) // invoke the callback function with k²
) // end of recursive callg
(x,y,z)∈[−r+1,r]3
s
2An=Bn
n
2Cn=Dn
n
g(x => // for each x: \ NB:
g(y => // for each y: >-- all these values are
g(z => // for each z: / already squared by g
s += // add to s:
2 * ( // +2 if:
n == ( // n is equal to either
X = // An if n is odd (o = 1)
(n & 1 ? 2 : 8) * x + // or Cn if n is even (o = 2)
(o = 2 - n % 2) * y //
) + o * 32 * z //
) - ( // -1 if:
n == X + o * 8 * z // n is equal to either
) // Bn if n is odd
) // or Dn if n is even
) //
) // if s in unchanged, then n is (assumed to be) congruent답변
루비 , 126 바이트
->n{[8,32].product(*[(-n..-t=1).map{|i|i*=i;n%i<1&&n/=i;i}*2+[0]]*3).map{|j|d=2-n%2
k,x,y,z=j
2*d*x+y+k*z==n/d&&t+=k-16}
t==1}추가 사본을 만드는 데 t=1사용 q하는 대신 사각형 목록 을 초기화 하고 삼중 항으로 확장 할 장소를 찾았습니다 .
루비 , 129 바이트
->n{t=0
[8,32].product(q=(-n..-1).map{|i|i*=i;n%i<1&&n/=i;i}*2+[0],q,q).map{|j|d=2-n%2
k,x,y,z=j
2*d*x+y+k*z==n/d&&t+=k-16}
t==0}다른 답변과 마찬가지로 Tunnell의 정리를 사용합니다. 다음과 같은 단일 방정식을 사용합니다.
2*d*x^2 + y^2 + k*z^2 == n/d where d=2 for even n and d=1 for odd n우리는 사례를 확인 k=8하고 k=32그리고 많은 솔루션으로 두 번이 있는지 확인 k=8보다 k=32. 솔루션을 찾을 때마다 추가 k-16하면 t됩니다. 이 경우 +16 k=32또는 경우 -8입니다 k=8. t함수의 끝에서 초기 값과 같은 경우 전체적으로 숫자가 일치 합니다.
테스트 방정식에 대한 모든 솔루션을 찾아야합니다. +/- 사이에서 많은 답변을 테스트하는 것을 봅니다 sqrt n. 코드를 더 짧게 만들면 이러한 한계를 넘어서도 테스트해도 괜찮지 만 방정식의 왼쪽이를 초과하기 때문에 해를 구할 수 없습니다 n. 처음에 내가 놓친 것은 부정적인 것과 긍정적 인 x,y,z것이 따로 고려 된다는 것 입니다. 따라서 -3,0,3세 제곱을 산출 9,0,9하고 모든 솔루션을 별도로 계산해야합니다 (0은 한 번 9계산하고 두 번 계산해야 함).
Ungolfed 코드
->n{t=0 #counter for solutions
q=(-n..-1).map{|i|i*=i;n%i<1&&n/=i #make n square free by dividing by -n^2 to -1^2 as necessary
i}*2+[0] #return an array of squares, duplicate for 1^2 to n^2, and add the case 0
[8,32].product(q,q,q).map{|j| #make a cartesian product of all possible values for k,x,y,z and iterate
d=2-n%2 #d=1 for odd n, 2 for even n
k,x,y,z=j #unpack j. k=8,32. x,y,z are the squared values from q.
2*d*x+y+k*z==n/d&&t+=k-16} #test if the current values of k,x,y,z are a valid solution. If so, adjust t by k-16 as explained above.
t==0} #return true if t is the same as its initial value. otherwise false.