합동 수 숫자n 입니다. OEIS A003273 입니다. 도전 이것은

정의 :

  • 삼각형은 고려 직각 삼각형 내부 각도 중 하나가 정확히 90 ° 인 경우.
  • 숫자는 고려 합리적 이 정수의 비율로 표현, 즉, 될 수 있다면 p/q, 어디에 둘 pq정수입니다.
  • 세 변이 모두 합리적인 영역의 오른쪽 삼각형이있는 경우 숫자 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

규칙 및 설명

  • 입력 및 출력은 편리한 방법 으로 제공 할 수 있습니다 .
  • 결과를 STDOUT에 인쇄하거나 함수 결과로 리턴 할 수 있습니다. 출력물에 어떤 값을 사용할 수 있는지 제출물에 명시하십시오.
  • 전체 프로그램 또는 기능이 허용됩니다.
  • 표준 허점 은 금지되어 있습니다.
  • 이것은 이므로 모든 일반적인 골프 규칙이 적용되며 가장 짧은 코드 (바이트)가 이깁니다.


답변

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,"+"))}

온라인으로 사용해보십시오

ArnaudGiuseppe의 개선 사항 (최종 코드는 대부분 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 당)

참조 :

@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을 반환합니다.

q

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 = 2

g

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 call

g

(x,y,z)∈[−r+1,r]3

s

2An=Bn

n

2Cn=Dn

n

An=#{(x,y,z)∈[−r+1,r]3∣n=2x2+y2+32z2}Bn=#{(x,y,z)∈[−r+1,r]3∣n=2x2+y2+8z2}Cn=#{(x,y,z)∈[−r+1,r]3∣n=8x2+2y2+64z2}Dn=#{(x,y,z)∈[−r+1,r]3∣n=8x2+2y2+16z2}

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.