Definicje:

• Trójkąt jest uważany za trójkąt prosty, jeśli jeden z kątów wewnętrznych ma dokładnie 90 stopni.
• Wiele jest uważany za racjonalne , jeżeli może być reprezentowany przez stosunek liczb całkowitych, to znaczy p/q, gdzie zarówno pi qsą liczbami całkowitymi.
• Liczba njest liczbą zgodną, jeśli istnieje prostokątny trójkąt obszaru, w nktórym wszystkie trzy boki są racjonalne.
• To jest OEIS A003273 .

Wyzwanie

To wyzwanie stanowi problem decyzyjny . Biorąc pod uwagę liczbę wejściową x, wypisz odrębną i spójną wartość, jeśli xjest liczbą zgodną, ​​i oddzielną odrębną, spójną wartość, jeśli xnie jest liczbą zgodną . Wartości wyjściowe niekoniecznie muszą być zgodne z prawdą / falsey w twoim języku.

Zasada specjalna

Na potrzeby tego wyzwania możesz założyć hipotezę Birch i Swinnerton-Dyer jest prawdziwa. Alternatywnie, jeśli możesz udowodnić hipotezę Birch i Swinnerton-Dyer, idź po nagrodę Millennium w wysokości 1 000 000 $. ;-)

Przykłady

(Używanie Truedla przystających numerów i Falseinnych).

5 True
6 True
108 False

Zasady i wyjaśnienia

• Dane wejściowe i wyjściowe można podać dowolną dogodną metodą .
• Możesz wydrukować wynik do STDOUT lub zwrócić go jako wynik funkcji. Podaj w swoim zgłoszeniu, jakie wartości może przyjąć wynik.
• Dopuszczalny jest pełny program lub funkcja.
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

R 179 173 142 141 137 137 135 134 bajtów

Używając tych samych argumentów opartych na twierdzeniu Tunnella , zwraca 0if, jeśli nnie jest przystające, i 1inaczej. (Długo zajęło mi dostrzeżenie ograniczenia, pod warunkiem, że dotyczy to tylko liczb całkowitych bez kwadratów .)

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

Wypróbuj online

Ulepszenia wprowadzone przez Arnauda i Giuseppe (końcowy kod to w większości Guiseppe!), Z -3 dzięki Robin

Analiza składniowa:

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)

z twierdzeniem Tunnella stwierdzającym, że n jest zgodny wtedy i tylko wtedy, gdy liczba rozwiązań całkowitych do 2x² + y² + 8z² = n jest dwa razy większa niż liczba rozwiązań całkowitych do 2x² + y² + 32z² = n, jeśli n jest nieparzyste, a liczba rozwiązań całkowitych do 8x² + y² + 16z² = n jest dwa razy większa niż liczba rozwiązań całkowitych do 8x² + y² + 64z² = n, jeśli n jest parzyste.

Rdza - 282 bajtów

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]}

• Użyj twierdzenia Jerrolda B. Tunnella , którego tak naprawdę nie rozumiem, ale wydaje się, że i tak działa.
• podziel n przez wszystkie czynniki kwadratowe, aby uczynić go „wolnym od kwadratu”, ponieważ w poniższych dokumentach twierdzenie Tunnella jest opisane tylko dla zwolnień kwadratowych.
  • Wierzę, że to może zadziałać, ponieważ każda liczba przystająca, pomnożona przez kwadrat, tworzy większą liczbę przystającą i odwrotnie. testując mniejszą liczbę, możemy sprawdzić większą, która w naszym przypadku wynosi n. (wszystkie usunięte kwadraty można pomnożyć razem, tworząc jeden duży kwadrat).
• $$\text{if n is odd, test if n = }2x^2 + y^2 + 32z^2\text{ and/or } 2x^2 + y^2 + 8z^2$$ $$\text{if n is even, test if n = }8x^2 + 2y^2 + 64z^2 \text { and/or } 8x^2 + 2y^2 + 16z^2$$
  • w samym kodzie cztery równania zostały zamazane w jedno, wewnątrz pętli, za pomocą modulo dla parzystych / nieparzystych
• zachowaj sumę, które równania pasują do n
• po zapętleniu przetestuj współczynniki wartości (na tunel)

Zobacz też:

• Jeśli chcesz, wypróbuj kod na Rust Playground
• Numery przystające, krzywe eliptyczne i formy modułowe, autor: Guy Henniart, strona internetowa Bilkent University, przetłumaczony przez Franza Lemmermeyera
• The Congruent Number Problem, autor: Keith Conrad, strona internetowa University of Connecticut
• Zgodne liczby, autor: Brian Hayes, blog bit-palyer.org

poprawione parzyste / nieparzyste, dzięki @Level River St

C ++ (gcc) , 251 234 bajtów

Dzięki @arnauld za wskazanie głupiej literówki z mojej strony.

-17 bajtów dzięki @ceilingcat.

#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;}

Wypróbuj online!

Zwraca 1, jeśli nprzystaje, 0 w przeciwnym razie.

$q$$s^2q$ jest również zgodny (algorytm wydaje się łamać na liczbach zawierających kwadrat).

JavaScript (ES7), 165 bajtów

Podobnie jak odpowiedź @ NeilA. , jest on oparty na twierdzeniu Tunnella i dlatego zakłada, że ​​hipoteza Bircha i Swinnertona-Dyera jest prawdziwa.

Zwraca wartość logiczną.

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

Wypróbuj online!

W jaki sposób?

$n$$n'$$r=\lfloor\sqrt{n'}\rfloor$$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$$k^2$$-r<k\le 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) \in [-r+1,r]^3$$s$$2A_n = B_n$$n$$2C_n=D_n$$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

Ruby, 126 bytes

->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}

Try it online!

found a place to initialize t=1 and expanded the list of squares into a triplet instead of using q to make additional copies.

Ruby, 129 bytes

->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}

Try it online!

Uses Tunnell's theorem like the other answers. I use a single equation as follows.

2*d*x^2 + y^2 + k*z^2 == n/d  where d=2 for even n and d=1 for odd n

Sprawdzamy przypadki k=8i k=32sprawdzamy, czy istnieje dwa razy więcej rozwiązań dla k=8niż k=32. Odbywa się to poprzez dodanie k-16za tkażdym razem, gdy znajdziemy rozwiązanie. Jest to +16 w przypadku k=32lub -8 w przypadku k=8. Ogólnie liczba jest zgodna, jeśli tjest taka sama jak jej wartość początkowa na końcu funkcji.

It is necessary to find all solutions to the test equation. I see many answers testing between +/-sqrt n. It is perfectly OK to test also outside these limits if it makes code shorter, but no solutions will be found because the left side of the equation will exceed n. The thing I missed in the beginning is that negative and positive x,y,z are considered separately. Thus -3,0,3 yields three squares 9,0,9 and all solutions must be counted separately (0 must be counted once and 9 must be counted twice.)

Ungolfed code

->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.