21
\$\begingroup\$

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 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 so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
  • 3
    \$\begingroup\$ Is the input a positive integer? \$\endgroup\$ – Lynn Apr 26 at 22:31
  • \$\begingroup\$ My initial approach was to multiply the input by an arbitrary square number until it's half of the product of the legs in a Pythagorean triple, but then I realized it might be a bit hard to actually terminate for a non-congruent input. \$\endgroup\$ – Unrelated String Apr 26 at 22:42
  • \$\begingroup\$ @Xi'an Okay, but challenges should be self-contained. \$\endgroup\$ – Lynn Apr 27 at 14:18
  • \$\begingroup\$ @Lynn Yes, the input will be a positive integer. \$\endgroup\$ – AdmBorkBork Apr 29 at 12:27
8
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! The goal is to make code as short as possible. Perhaps you might look at these tips for golfing or these R-specific tips. \$\endgroup\$ – Giuseppe Apr 27 at 15:38
  • 1
    \$\begingroup\$ There's a lot of whitespace, and also I'd recommend including a link to Try It Online! to help verify your code :-) \$\endgroup\$ – Giuseppe Apr 27 at 15:39
  • 1
    \$\begingroup\$ Feel free to reach out in the R golfer chat too if you'd like; you can notify by using @[username]...I'm guessing you got pulled into code golf by Robin Ryder?? \$\endgroup\$ – Giuseppe Apr 27 at 15:45
  • 1
    \$\begingroup\$ 142 bytes -- anonymous functions are perfectly fine, and I made a few other golfs that I'm happy to explain \$\endgroup\$ – Giuseppe Apr 27 at 16:27
  • 1
    \$\begingroup\$ Nice! Is there a reason you use -n:n? I didn't read Tunnel's theorem, but it seems to me that n:0 would work just as well for -1 byte...Also, pro tip, if you hit the "link" button on the top of TIO, you'll get nice formats for copying and pasting into PPCG :-) EDIT: I see, there are some cases where n:0 doesn't work. \$\endgroup\$ – Giuseppe Apr 27 at 17:05
3
\$\begingroup\$

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:

corrected even/odd, thanks@Level River St

\$\endgroup\$
  • 1
    \$\begingroup\$ oh well, at the time i got this working i only saw the c++ answer which was wrong... \$\endgroup\$ – don bright Apr 27 at 16:29
  • \$\begingroup\$ thanks Level River St \$\endgroup\$ – don bright Apr 28 at 14:02
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @Arnauld: ah, that was a typo on my part. fixed. \$\endgroup\$ – Neil A. Apr 27 at 18:57
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ about positive and negative solutions, same here, I wasted quite a while missing this point! \$\endgroup\$ – Xi'an Apr 28 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.