Definiciones:

• Un triángulo se considera un triángulo rectángulo si uno de los ángulos internos es exactamente 90 grados.
• Un número se considera racional si se puede representar mediante una relación de enteros, es decir p/q, donde ambos py qson enteros.
• Un número nes un número congruente si existe un triángulo rectángulo de área ndonde los tres lados son racionales.
• Este es OEIS A003273 .

Reto

Este es un desafío de decisión-problema . Dado un número de entrada x, genera un valor distinto y coherente si xes un número congruente, y un valor distinto y coherente separado si xno es un número congruente. Los valores de salida no necesariamente tienen que ser veraz / falsey en su idioma.

Regla especial

Para los propósitos de este desafío, puede asumir que la conjetura de Birch y Swinnerton-Dyer es cierta. Alternativamente, si puede probar la conjetura de Birch y Swinnerton-Dyer, vaya a reclamar su premio Millennium de $ 1,000,000. ;-)

Ejemplos

(Utilizando Truepara números congruentes y de Falseotra manera).

5 True
6 True
108 False

Reglas y aclaraciones

• La entrada y salida se pueden dar por cualquier método conveniente .
• Puede imprimir el resultado en STDOUT o devolverlo como resultado de una función. Indique en su envío qué valores puede tomar la salida.
• Un programa completo o una función son aceptables.
• Las lagunas estándar están prohibidas.
• Este es el código de golf, por lo que se aplican todas las reglas habituales de golf, y gana el código más corto (en bytes).

R, 179 173 142 141 137 135 134 bytes

Usando los mismos argumentos basados ​​en el Teorema de Tunnell , devuelve un 0if nno es congruente y de lo 1contrario. (Me tomó mucho tiempo detectar la restricción en la condición que solo se aplica a enteros sin cuadrados ).

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

Pruébalo en línea

Mejoras aportadas por Arnaud y Giuseppe (¡el código final es principalmente Guiseppe!), Con -3 gracias a Robin

Análisis de sintaxis:

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)

con el Teorema de Tunnell que establece que n es congruente si y solo si el número de soluciones enteras a 2x² + y² + 8z² = n es el doble que el número de soluciones enteras a 2x² + y² + 32z² = n si n es impar y el número de soluciones enteras a 8x² + y² + 16z² = n es el doble que el número de soluciones enteras a 8x² + y² + 64z² = n si n es par.

Óxido - 282 bytes

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

• Utilizar el teorema de Jerrold B. Tunnell , que en realidad no entiendo, pero parece funcionar de todos modos.
• divida n entre todos sus factores cuadrados, para hacerlo 'libre de cuadrados', ya que en los documentos a continuación el teorema de Tunnell se describe solo para liberaciones cuadradas.
  • Creo que esto podría funcionar porque cada número congruente, cuando se multiplica por un cuadrado, crea un número congruente más grande, y viceversa. así que al probar el número más pequeño, podemos validar el más grande, que en nuestro caso es n. (todos los cuadrados eliminados, se pueden multiplicar juntos para hacer un gran cuadrado).
• $$\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$$
  • en el código en sí, las cuatro ecuaciones se han suavizado en una, dentro de un bucle, usando un módulo para pares / impares
• mantener un recuento de las ecuaciones que coinciden n
• después del bucle, pruebe las proporciones de los recuentos (por Tunnell)

Ver también:

• Si lo desea, pruebe el código en Rust Playground
• Números congruentes, curvas elípticas y formas modulares, por Guy Henniart, sitio web de la Universidad Bilkent, traducido por Franz Lemmermeyer
• El problema del número congruente, por Keith Conrad, sitio web de la Universidad de Connecticut
• Números congruentes, por Brian Hayes, blog bit-palyer.org

corregido par / impar, gracias @Level River St

C ++ (gcc) , 251 234 bytes

Gracias a @arnauld por señalar un error tipográfico de mi parte.

-17 bytes gracias a @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;}

Pruébalo en línea!

Devuelve 1 si nes congruente, 0 de lo contrario.

$q$$s^2q$ también es congruente (el algoritmo parece romperse en algunos números que contienen cuadrados).

JavaScript (ES7), 165 bytes

Al igual que la respuesta de @ NeilA. , esto se basa en el teorema de Tunnell y, por lo tanto, supone que la conjetura de Birch y Swinnerton-Dyer es cierta.

Devuelve un valor booleano.

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

Pruébalo en línea!

¿Cómo?

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

Pruébalo en línea!

Encontré un lugar para inicializar t=1y expandí la lista de cuadrados en un triplete en lugar de usar qpara hacer copias adicionales.

Rubí , 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}

Pruébalo en línea!

Utiliza el teorema de Tunnell como las otras respuestas. Yo uso una sola ecuación de la siguiente manera.

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

Comprobamos los casos k=8y k=32y compruebe si hay el doble de muchas soluciones para k=8que k=32. Esto se hace mediante la adición k-16a tcada vez que encontramos una solución. Esto es +16 en el caso k=32o -8 en el caso k=8. En general, el número es congruente si tes el mismo que su valor inicial al final de la función.

Es necesario encontrar todas las soluciones a la ecuación de prueba. Veo muchas respuestas probando entre +/- sqrt n. Está perfectamente bien probar también fuera de estos límites si hace que el código sea más corto, pero no se encontrarán soluciones porque el lado izquierdo de la ecuación excederá n. Lo que me perdí al principio es que negativo y positivo x,y,zse consideran por separado. Por lo tanto, -3,0,3produce tres cuadrados 9,0,9y todas las soluciones deben contarse por separado (0 debe contarse una vez y 9debe contarse dos veces).

Código sin golf

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