Congruent Numbers

Question

Definitions:

• A triangle is considered a right triangle if one of the inner angles is exactly 90 degrees.
• A number is considered rational if it can be represented by a ratio of integers, i.e., p/q, where both p and q are integers.
• A number n is a congruent number if there exists a right triangle of area n where all three sides are rational.
• This is OEIS A003273.

Challenge

This is a decision-problem challenge. Given an input number, x, output a distinct and consistent value if x is a congruent number, and a separate distinct and consistent value if x is not a congruent number. The output values do not necessarily need to be truthy/falsey in your language.

Special Rule

For the purposes of this challenge, you can assume that the Birch and Swinnerton-Dyer conjecture is true. Alternatively, if you can prove the Birch and Swinnerton-Dyer conjecture, go claim your $1,000,000 Millennium prize. ;-)

Examples

(Using True for congruent numbers and False otherwise).

5 True
6 True
108 False

Rules and Clarifications

• Input and output can be given by any convenient method.
• You can print the result to STDOUT or return it as a function result. Please state in your submission what values the output can take.
• Either a full program or a function are acceptable.
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Answer 1

R, 179 173 142 141 137 135 134 bytes

Using the same arguments based on Tunnell's Theorem, returns a 0 if nis not congruent and 1 otherwise. (It took me a long while to spot the constraint on the condition only applying to squared-free integers.)

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

Try it online

Improvements brought by Arnaud and Giuseppe (the final code is mostly Guiseppe's!), with -3 thanks to Robin

Syntax analysis:

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)

with Tunnell's Theorem stating that n is congruent if and only if the number of integer solutions to 2x²+y²+8z²=n is twice as much as the number of integer solutions to 2x²+y²+32z²=n if n is odd and the number of integer solutions to 8x²+y²+16z²=n is twice as much as the number of integer solutions to 8x²+y²+64z²=n if n is even.

Answer 2

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

• Use Jerrold B. Tunnell's theorem, which I dont actually understand, but seems to work anyways.
• divide n by all its square factors, to make it 'square free', since in the papers below Tunnell's theorem is described for square-frees only.
  • I believe this might work because every congruent number, when multiplied by a square, creates a bigger congruent number, and vice versa. so by testing the smaller number, we can validate the larger, which in our case is n. (all the removed squares, can be multiplied together to make one big square).
• loop through all possible combinations of x,y,z integers, test Tunnell's equations: $$\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$$
  • in the code itself, the four equations have been smooshed into one, inside a loop, using modulo for even/odd
• keep a tally count of which equations match n
• after looping, test the ratios of the tallies (per Tunnell)

See Also:

• If you wish, try the code on the Rust Playground
• Congruent Numbers, Elliptic Curves, and Modular Forms, by Guy Henniart, Bilkent University website, translated by Franz Lemmermeyer
• The Congruent Number Problem, by Keith Conrad, University of Connecticut website
• Congruent numbers, by Brian Hayes, bit-palyer.org blog

corrected even/odd, thanks@Level River St

Answer 3

C++ (gcc), 251 234 bytes

Thanks to @arnauld for pointing out a silly typo on my part.

-17 bytes thanks to @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;}

Try it online!

Returns 1 if n is congruent, 0 otherwise.

Given that we can assume that the Birch and Swinnerton-Dyer conjecture is true, I used Tunnel's Theorem as a test. Note that technically only nonzero x, y, and z need to be tested, as a set of positive (x, y, z) implies more sets for when each of those is negative, since the four numbers defined use the square of x, y, and z in their calculation. Additionally, since only the ratio of the two numbers A and B, or C and D, is desired, we need not even worry about these other sets. Thus, we only need to add 2 for every solution for A or C, and subtract 1 for every solution of B or D, and check if we end with 0. Also, the input is reduced to a squarefree integer, because if \$q\$ is a congruent number then \$s^2q\$ is also congruent (the algorithm seems to break on some square-containing numbers.

Answer 4

APL (Dyalog Unicode), ⁷³ 67 bytes

{e←2∨w←⍵÷×⍨⊃⌽⍒⍵|⍨×⍨⍳⍵⋄0=¯2⊥+/w=e×⍪(r∘.+⍨32 8∘.×r)∘.+2×e×r←0,2/×⍨⍳w}

Try it online!

^{-6 bytes thanks to @ngn and @H.PWiz.}

Essentially the same algorithm as others.

Ungolfed and how it works

f←{
  ⍝ Extract squarefree part of ⍵
  w←⍵÷×⍨⊃⌽⍒⍵|⍨×⍨⍳⍵
⍝             ×⍨⍳⍵  ⍝ Square of 1..⍵
⍝          ⍵|⍨      ⍝ Remainders of dividing ⍵ by each of the above
⍝       ⊃⌽⍒         ⍝ Last item of descending sort order; index of last 0
⍝ w←⍵÷×⍨            ⍝ Remove square term and name it w

  ⍝ 1 if odd, 2 if even; divide w by that
  w÷←e←2∨w
⍝    e←2∨w  ⍝ GCD of w with 2; name it e
⍝ w÷←       ⍝ Divide w by e and overwrite to w

  ⍝ Square of plus-minus range
  r←0,2/×⍨⍳w
⍝       ×⍨⍳w  ⍝ Square of 1..w
⍝ r←0,2/      ⍝ Make two copies of each number, prepend 0 and name it r

  ⍝ y2+32z2 (A/C) and y2+8z2 (B/D), with y and z swapped
  m←∘.(32 8⊥¨∘⊂,)⍨r
⍝   ∘.(         )⍨r  ⍝ Self outer product of r by...
⍝              ,     ⍝ Concatenate two input numbers and
       32 8⊥¨∘⊂      ⍝ Interpret as base-32 and base-8
⍝ m←                 ⍝ Name it m

  ⍝ Add 2×e×x2
  m←,m∘.+2×e×r
⍝    m∘.+2×e×r  ⍝ Outer product by + with 2×e×x2
⍝ m←,           ⍝ Flatten and overwrite m

  ⍝ count w in m and check if B/D is twice A/C
  0=¯2⊥⊃+/w=m
⍝         w=m  ⍝ Test for each sum being w
⍝      ⊃+/     ⍝ Count of 'w's in A/C and B/D
⍝   ¯2⊥        ⍝ (¯2×A/C) + B/D
⍝ 0=           ⍝ Equals 0?
}

Answer 5

JavaScript (ES7), 165 bytes

Much like @NeilA.'s answer, this is based on Tunnell's theorem and therefore assumes that the Birch and Swinnerton-Dyer conjecture is true.

Returns a Boolean value.

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

Try it online!

How?

We first transform the input \$n\$ into its square-free counterpart \$n'\$, compute \$r=\lfloor\sqrt{n'}\rfloor\$ and initialize \$s\$ to \$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

We then define the helper function \$g\$ which invokes a callback function \$C\$ with \$k^2\$ for \$-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

We finally use 3 nested calls to \$g\$ to walk through all triplets \$(x,y,z) \in [-r+1,r]^3\$ and update \$s\$ to test whether \$2A_n = B_n\$ if \$n\$ is odd or \$2C_n=D_n\$ if \$n\$ is even, with:

$$\begin{align} &A_n=\#\{(x,y,z)\in [-r+1,r]^3 \mid n=2x^2+y^2+32z^2\}\\ &B_n=\#\{(x,y,z)\in [-r+1,r]^3 \mid n=2x^2+y^2+8z^2\}\\ &C_n=\#\{(x,y,z)\in [-r+1,r]^3 \mid n=8x^2+2y^2+64z^2\}\\ &D_n=\#\{(x,y,z)\in [-r+1,r]^3 \mid n=8x^2+2y^2+16z^2\} \end{align}$$

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

Answer 6

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

We check the cases k=8 and k=32 and check if there are twice as many solutions for k=8 than k=32. This is done by adding k-16 to t every time we find a solution. This is either +16 in the case k=32 or -8 in the case k=8. Overall the number is congruent if t is the same as its initial value at the end of the function.

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.