Congruent Numbers Part II

Using Elliptic Curves to Compute the Triangles

The method of my first post is too slow to find the side lengths for a triangle of area N=157, which has many digits:

    \[ \left(\frac{6803298487826435051217540}{411340519227716149383203}\right)^2 + \left(\frac{411340519227716149383203}{21666555693714761309610}\right)^2 \]

    \[ = \left(\frac{224403517704336969924557513090674863160948472041}{8912332268928859588025535178967163570016480830} \right)^2 \]

    \[ \rule{0pt}{30pt} \frac{1}{2} \times \frac{6803298487826435051217540}{411340519227716149383203} \times \frac{411340519227716149383203}{21666555693714761309610} = 157 \]

In the 1984 book by Koblitz,  Introduction to Elliptic Curves and Modular Forms, computation of the side lengths for N=157 is credited to the mathematician Don Zagier. Now, however, it can be computed quickly by anyone with access to the SageMath system. The Python code given below computes the values for N=157 in less than one minute on my Mac laptop.

Put the code in the next section into a file called (say) congruent.py, fire up SageMath, and then type load(‘congruent.py’) followed by print_range(157, 157, 13). This produces the answer in about 15 seconds.

 
This post has three parts: I derive equations that produce triangle side lengths for congruent numbers; I give Python code that implements the equations; and I present two tables of congruent numbers. The first table is for N \leq 1000, and is a variant of the web table. The second is an incomplete table for 1000 < N \leq 2000 constructed using the Python code.

The equations

Exhaustive search is too slow to find the sides of the triangle with area N=157; finding them requires a new idea. That idea is to reduce the search to a problem in elliptic curves (the same idea used to prove Fermat’s Last Theorem!).

An elliptic curve is the next level of complexity after a quadratic curve. A quadratic curve is y^2 = ax^2 + bx + c; an elliptic curve is y^2 = ax^3 + bx^2 + cx + d. For the congruent number problem, Koblitz’s book Introduction to Elliptic Curves and Modular Forms shows the connection between a congruent N and the elliptic curve y^2 = x^3 - N^2x. I summarize it here.

The connection involves adding points. For a conic section like a circle x^2 + y^2 = 1 each point (x,y) can be represented by (\cos \theta, \sin \theta), and two points (x,y), (x', y') with angles \theta, \theta' can be added to get a third point (x'', y'') with angle \theta + \theta'. In a formula

    \[ x'' = \cos(\theta + \theta') = \cos \theta \cos \theta' - \sin \theta \sin \theta' = xx' - yy' \]

with a similar formula for y''. So the formula for (x,y) \oplus (x', y') is a rational function of x,y,x', y', where \oplus is our special addition, not vector addition. In the same way, two points on an elliptic curve can be added, and there is a formula for the sum. If y^2 = f(x) = ax^3 = bx^2 + cx + d and (x', y') = (x,y) \oplus (x,y) then the formula for x' (I don’t need y') is

    \[ x' = -2x - \frac{b}{a} + \frac{1}{a}\left( \frac{f'(x)}{2y} \right)^2 \]

If (x,y) is a point of

    \[ y^2 = x^3 - N^2x \]

this simplifies to

    \[ x' = -2x + \left( \frac{3x^2 - N^2}{2y} \right)^2 \]

In that equation x', x and y are rational numbers. I need a formula in terms of their numerators and denominators. So write

(1)   \begin{equation*}  x = \frac{s}{t} \qquad y = \frac{u}{v} \end{equation*}

Then

    \begin{eqnarray*} x' & = & -2\frac{s}{t} + \left( \frac{3(\frac{s}{t})^2 - N^2}{\frac{2u}{v}} \right)^2 \\ & = & -\frac{2s}{t} + \left(\frac{3s^2v - t^2vn^2}{2ut^2}\right)^2 \\ & = & -\frac{2s}{t} + \frac{v^2}{4u^2t^4}\left(3s^2 - t^2n^2 \right)^2 \\ & = & -\frac{8su^2t^3}{4u^2t^4} + \frac{v^2\left(3s^2 - t^2n^2 \right)^2}{4u^2t^4} \\ & = & \frac{-8su^2t^3 + v^2\left(3s^2 - t^2n^2 \right)^2}{(2ut^2)^2} \\ & = & \frac{s'}{t'} = \frac{s'}{\tau^2} \end{eqnarray*}

Next, use Koblitz page 47, which says that if (x',y') is the \oplus sum of a point on y^2 = x^3 - N^2x with itself, then you get rational sides with area N for sides \alpha, \beta with

    \begin{eqnarray*} \alpha & = & \sqrt{x'+N} - \sqrt{x'-N} \\ \beta & = & \sqrt{x'+N} + \sqrt{x'-N} \\ \end{eqnarray*}

so

    \begin{eqnarray*} \alpha & = & \sqrt{x'+N} - \sqrt{x'-N} = \frac{\sqrt{s' + Nt'} - \sqrt{s' - Nt'}}{\tau} \\ \beta & = & \sqrt{x'+N} + \sqrt{x'-N} = \frac{\sqrt{s' + Nt'} + \sqrt{s' - Nt'}}{\tau} \end{eqnarray*}

Or since \alpha = a/d, \beta = b/e

    \begin{eqnarray*} a &=& \sqrt{s' + Nt'} - \sqrt{s' - Nt'} \\ d &=& \tau \\ b &=& \sqrt{s' + Nt'} + \sqrt{s' - Nt'}\\ e &=& d \end{eqnarray*}

This gives an algorithm that can find the sides’ lengths for area N, and is fast enough to work for N=157. Use SageMath to find a point on y^2 = x^3 - Nx. Next use equation (1) to define s, t, u, v and the equation after that to get s' and t'. And use the equations directly above to get the side lengths \alpha = a/d and \beta = b/e.

Python code for SageMath

Here is the code that implements the algorithm of the previous section.

# congruent in python for use in SageMath

import re

# print sides of congruent number from lo to hi, inclusive
def print_range(lo, hi, lim=12):
    for i in range(lo, hi+1):
        if (squarefree(i) == 1):
            if  ((i%2 == 1) and odd(i)) or ((i%2 == 0) and even(i)):
                print_congruent(i, lim)

# return 1 if n squarefree
def squarefree(n):
    if n % 4 == 0:
        return 0
    rt = floor(sqrt(n))
    for i in range(3, rt+1, 2):
       if n % (i*i) == 0:
           return 0
    return 1

# print sides of triangle with area N.  'lim' controls how much searching is done
def print_congruent(N, lim=12):
   e = EllipticCurve([-N*N, 0])
   try:
       g = e.gens(descent_second_limit = lim)
   except (RuntimeError) as msg:
       #  msg might be of the form "generators found=[[323144640, -6423052104, 274625]])."
       match = re.search(r"\[([0-9-]*),(.*),([0-9- ]*)", str(msg))
       if match is not None:
          preparser(False)
          a = int(match.group(1))
          b = int(match.group(2))
          c = int(match.group(3))
          preparser(True)
          print_points(a, c, b, c, N)
       else:
          print N, "Cannot find Solution"
   else:
      for i in range(0, len(g)):
          print_points(g[i][0].numerator(), g[i][0].denominator(), g[i][1].numerator(),
                g[i][1].denominator(), N)

# Get the side lengths alpha = a/d, beta = b/e, compute
# the corresponding values of P,Q, write them as a square
# times a factor of N,  and print them
def print_points(s,t,u,v, N):  # pts x=s/t, y=u/v on elliptic curve
   s1, t1, u1, v1 = double(s, t, u, v, N)
   a, d, b, e = point_to_sides(s1, t1, N)        
   print N, "   alpha=", a, "/", d
   print "      beta=", b, "/", e

   #  compute A,B,C so that A^2 + B^2 = C^2
   A = a*e
   B = b*d
   g = gcd(A,B)
   A = A/g
   B = B/g
   C = sqrt(A*A + B*B)

   # compute P,Q so that A = 2PQ, B = P^2 - Q^2
   if B % 2 == 1:
      P = sqrt((C+B)/2)
      Q = sqrt((C-B)/2)
      print "     P=", P, " Q=", Q
   else:
      P = sqrt((C+A)/2)
      Q = sqrt((C-A)/2)
      print "     P=", P, " Q=",  Q

   # factor P = i0*P0^2,  Q = j0*Q0^2
   for i in range(1, N+1):
       if ( P%i == 0 and floor(sqrt(P/i))**2 == P/i):
            P0 = sqrt(P/i)
            i0 = i
            break
   for j in range(1, N+1):
       if (Q%j == 0 and  floor(sqrt(Q/j))**2 == Q/j):
            Q0 = sqrt(Q/j)
            j0 = j
            break
   print "    P= ", i0, "*", P0, "^2, Q=", j0, "*", Q0, "^2"

# x=s/t, y=u/v is a point on y^2 = x^3 - N^2x.  Returns (x,y) + (x,y)
def double(s,t,u,v, N): 
   num = -8*s*t**3*u*u + v*v*(3*s*s - t*t*N*N)**2
   denom = 2*u*t*t
   s1 = num
   t1 = denom*denom
   u1 = -2*u*u*t1*t**3 + v*v*(s*t1 - t*s1)*(3*s*s - t*t*N*N)
   v1 = 2*u*v*t1*t**3
   g1 = gcd(s1, t1)
   g2 = gcd(u1, v1)
   return (s1/g1, t1/g1, u1/g2, v1/g2) # don't need last two elements

# Given (x,y) + (x,y) = (s/t, u/v), compute the corresponding alpha = a/d, beta = b/e
def point_to_sides(s, t, N):
   p1 = sqrt(s + t*N)  # sqrt(x+N)
   p2 = sqrt(s - t*N)  # sqrt(x-N)

   a = p1 - p2
   d =  sqrt(t)
   b = p1 + p2
   e  = d
   g1 = gcd(a, d)
   g2 = gcd(b, e)
   return(a/g1, d/g1, b/g2, e/g2)

# test for n congruent when n is odd
def odd(n): 
    cnt1 = 0
    cnt2 = 0
    m = floor(sqrt(n))
    for x in range(-m, m+1):
      for y in range(-m, m+1):
        for z in range(-m, m+1):
           if 2*x*x + y*y + 32*z*z == n:
               cnt1 = cnt1 + 1
    for x in range(-m, m+1):
      for y in range(-m, m+1):
        for z in range(-m, m+1):
           if 2*x*x + y*y + 8*z*z == n:
               cnt2 = cnt2 + 1
    return(2*cnt1 == cnt2)

# test for n congruent when n is even
def even(n): 
    cnt1 = 0
    cnt2 = 0
    n = n/2
    m = floor(sqrt(n))
    for x in range(-m, m+1):
      for y in range(-m, m+1):
        for z in range(-m, m+1):
           if 4*x*x + y*y + 32*z*z == n:
               cnt1 = cnt1 + 1
    for x in range(-m, m+1):
      for y in range(-m, m+1):
        for z in range(-m, m+1):
           if 4*x*x + y*y + 8*z*z == n:
               cnt2 = cnt2 + 1
    return(2*cnt1 == cnt2)

The table through 1000

Here is a table with the side lengths of congruent numbers. Like the web tables, it gives P and Q rather than the side lengths \alpha, \beta, but I give P and Q in factored form. In addition it differs from the web table at N=210, N=559, N=609, and N=985. The changes at N=609 and N=985 give fractions with a smaller denominator. The change at N=559 fixes the glitch wherein both P and Q are both odd.

The change at N=210 adds a second solution with the same denominator. I remarked before that there are multiple values of P, Q (or equivalently \alpha, \beta, \gamma) for each N, and that I would pick the one with the smallest D. This doesn’t always select a unique triangle. For example N=210 has both (\alpha=20, \beta=21, \gamma=29) and (\alpha=12, \beta=35, \gamma=37), both with D=1. Other such examples are

Rendered by QuickLaTeX.com

And now, here’s the table. Also available as a text file.

 
  N                                             P                                             Q
  5                                         5*1^2                                           2^2
  6                                         2*1^2                                           1^2
  7                                           4^2                                           3^2
 13                                        13*5^2                                           6^2
 14                                         2*2^2                                           1^2
 15                                           2^2                                           1^2
 21                                           2^2                                         3*1^2
 22                                         2*5^2                                           7^2
 23                                         156^2                                         133^2
 29                                       29*13^2                                          70^2
 30                                         3*1^2                                         2*1^2
 31                                          40^2                                           9^2
 34                                           3^2                                         2*2^2
 37                                      37*145^2                                          42^2
 38                                        2*25^2                                          17^2
 39                                        13*1^2                                         3*2^2
 41                                           5^2                                           4^2
 46                                         2*6^2                                           7^2
 47                                        3816^2                                        1513^2
 53                                     53*5945^2                                       34034^2
 55                                         5*5^2                                        11*2^2
 61                                      61*445^2                                        3198^2
 62                                       2*140^2                                         151^2
 65                                           3^2                                           2^2
 69                                         3*8^2                                          13^2
 70                                         7*1^2                                         2*1^2
 71                                          60^2                                          11^2
 77                                       11*16^2                                          53^2
 78                                        26*1^2                                           1^2
 79                                       13000^2                                       12921^2
 85                                        85*1^2                                           6^2
 86                                        2*13^2                                           7^2
 87                                         134^2                                          13^2
 93                                          38^2                                         3*5^2
 94                                        2*84^2                                          23^2
 95                                        5*17^2                                        19*2^2
101                                   101*21041^2                                       63050^2
102                                         2*5^2                                           1^2
103                                    93704884^2                                    86901837^2
109                                       109*5^2                                          42^2
110                                        10*1^2                                           1^2
111                                        37*1^2                                         3*2^2
118                                     2*18925^2                                        4393^2
119                                          12^2                                           5^2
127                                 17501923504^2                                 17467450497^2
133                                         506^2                                       19*87^2
134                                      2*1021^2                                         119^2
137                                       137*5^2                                          56^2
138                                         6*2^2                                           1^2
141                                         3*4^2                                           1^2
142                                     2*49590^2                                       12809^2
143                                         318^2                                          43^2
145                                        29*1^2                                         5*2^2
149                                      149*25^2                                         238^2
151                                         340^2                                         189^2
154                                           3^2                                         2*1^2
157                             157*53156661805^2                                407598125202^2
158                                       2*620^2                                         761^2
159                                         182^2                                         107^2
161                                           4^2                                         7*1^2
165                                           4^2                                        11*1^2
166                                      2*9941^2                                        9799^2
167                                      339444^2                                       58717^2
173                              173*3728226965^2                                 48661701478^2
174                                         3*3^2                                         2*1^2
181                                    181*4121^2                                       34950^2
182                                         7*7^2                                         2*3^2
183                                      61*541^2                                       3*390^2
190                                        10*1^2                                           3^2
191                                   636182040^2                                   620449561^2
194                                        97*1^2                                         2*6^2
197                                 197*3179345^2                                    10192154^2
199                                     3732820^2                                      523149^2
205                                         5*3^2                                           2^2
206                                      2*1394^2                                        1103^2
210                                         5*1^2                                         2*1^2
210                                         6*1^2                                           1^2
213                                      3*1600^2                                         851^2
214                                       2*313^2                                         287^2
215                                          62^2                                          19^2
219                                        73*1^2                                         3*4^2
221                                        13*1^2                                           2^2
222                                       74*13^2                                          59^2
223                                  7137389056^2                                  3792733167^2
226                                           9^2                                         2*4^2
229                                   229*61793^2                                       87030^2
230                                        23*7^2                                        2*19^2
231                                         7*1^2                                           2^2
237                                       43454^2                                      3*5915^2
238                                        2*30^2                                          41^2
239                                         120^2                                         119^2
246                                        2*17^2                                          23^2
247                                        5998^2                                        5877^2
253                                         354^2                                       11*91^2
254                                       2*272^2                                         161^2
255                                           4^2                                           1^2
257                                         153^2                                         104^2
262                                      2*7345^2                                        9553^2
263                           49143127346631084^2                           46867792486220437^2
265                                           7^2                                           2^2
269                             269*85656402325^2                                 82710580922^2
271                                   300940360^2                                   101904681^2
277                         277*232579772276105^2                            1032363194300802^2
278                                    2*701185^2                                      990817^2
285                                        19*2^2                                           7^2
286                                        11*1^2                                         2*1^2
287                                      137904^2                                      137903^2
291                                           7^2                                         3*4^2
293                            293*231520447985^2                               3842474897278^2
295                                       5*433^2                                       59*62^2
299                                           6^2                                        13*1^2
301                                        43*8^2                                          27^2
302                                2*2167791890^2                                  3004234751^2
303                                      202046^2                                      166403^2
309                                        3458^2                                       3*799^2
310                                        10*2^2                                           3^2
311                                436723577940^2                                353087218429^2
313                                          13^2                                          12^2
317                              317*2951368765^2                                 16840660634^2
319                                          50^2                                          49^2
323                                        17*5^2                                        19*4^2
326                                     2*33661^2                                         679^2
327                                    109*7969^2                                     3*47950^2
330                                         6*1^2                                         5*1^2
334                                   2*1279626^2                                     1061887^2
335                                        2798^2                                        2629^2
341                                         118^2                                       11*15^2
349                                    349*7453^2                                      113730^2
353                                          17^2                                           8^2
357                                        21*1^2                                           2^2
358                                  2*21866725^2                                    20489063^2
359                                    57470100^2                                    57469741^2
365                                   365*14893^2                                       94874^2
366                                       122*1^2                                          11^2
367                     16382168821648506431464^2                       496953629608513608777^2
371                                        53*1^2                                         7*2^2
373                     373*2603564129117970265^2                        16377382078444972158^2
374                                        2*29^2                                           1^2
381                                         398^2                                       3*221^2
382                                    2*129060^2                                       88679^2
383                                    20091144^2                                    17430983^2
386                                          11^2                                         2*6^2
389                          389*14699193245425^2                              72369303587042^2
390                                         2*2^2                                         5*1^2
391                                         572^2                                         555^2
395                                         5*4^2                                           1^2
397                                  397*109045^2                                     2069034^2
398                                    2*655850^2                                      806831^2
399                                           8^2                                        57*1^2
406                                        58*8^2                                           3^2
407                                    37*11225^2                                    11*20586^2
410                                        41*1^2                                        10*2^2
413                                       64114^2                                     59*6213^2
415                                       29698^2                                       15671^2
421                                421*32786945^2                                   189819882^2
422                                       2*565^2                                         217^2
426                                         6*4^2                                           5^2
429                                         3*2^2                                           1^2
430                                        43*9^2                                        2*41^2
431                                   439631880^2                                    56365561^2
434                                         2*4^2                                        31*1^2
437                                        8914^2                                     19*1247^2
438                                           7^2                                         6*2^2
439                                   266438380^2                                   207471339^2
442                                          11^2                                        26*2^2
445                                        89*1^2                                         5*4^2
446                                  2*37655576^2                                    19427153^2
447                                       22442^2                                       21481^2
453                                     1307114^2                                    3*722785^2
454                                    2*708089^2                                      925711^2
455                                           8^2                                           1^2
457                                         253^2                                         204^2
461                            461*331709140421^2                               6025359571150^2
462                                        14*1^2                                        11*1^2
463                                  1078250296^2                                   376638153^2
465                                           4^2                                        15*1^2
469                                      67*148^2                                        1101^2
470                                        47*1^2                                         2*1^2
471                                     157*949^2                                      3*1962^2
478                             2*7613312866500^2                               1278366247319^2
479                                       46320^2                                       22849^2
485                                    485*6409^2                                       81314^2
487                              31922317361596^2                              20227123841253^2
493                                  493*348125^2                                     3026946^2
494                                       19*11^2                                        2*27^2
501                                      3*8932^2                                        4163^2
502                                  2*13172945^2                                     5749553^2
503                    126022097765194972888404^2                    124468507893835378881997^2
505                                       101*1^2                                         5*2^2
509                                      509*13^2                                         170^2
510                                         2*4^2                                        17*1^2
511                                       18952^2                                        2145^2
514                                       257*1^2                                         2*4^2
517                                           6^2                                        11*1^2
518                                        74*4^2                                          29^2
519                                      570986^2                                       64223^2
526                                      2*3774^2                                         137^2
527                                          24^2                                           7^2
533                                    533*6025^2                                      137522^2
534                                       2*157^2                                         217^2
535                                         418^2                                         311^2
541                             541*82652759501^2                               1629675045390^2
542                             2*8337517165460^2                               6072862516759^2
543                               181*849929197^2                                3*3004968950^2
546                                         7*1^2                                         6*1^2
551                                         350^2                                         179^2
557                              557*1746479765^2                                 40206424678^2
559                                      13*317^2                                      43*174^2
561                                        17*1^2                                           4^2
565                                      565*41^2                                         558^2
566                                   2*3119461^2                                      508681^2
573                                 3*155482680^2                                   222747577^2
574                                        2*12^2                                           1^2
581                                         554^2                                       83*57^2
582                                       194*1^2                                          13^2
583                                     53*8825^2                                    11*19178^2
589                                      19*944^2                                        2265^2
590                                       10*41^2                                          67^2
591                                        1406^2                                         181^2
597                                  4509125978^2                                3*2061246655^2
598                                      26*186^2                                         727^2
599                   1743235759090264843329900^2                   1298070998128102765757269^2
602                                           5^2                                         2*3^2
606                                        3*27^2                                        2*13^2
607         11193477616854092718151692958821016^2          5301570241310268303909957034492887^2
609                                         7*2^2                                           1^2
613                          613*14799287186305^2                              46559016084714^2
614                                  2*59953357^2                                    57198937^2
615                                          22^2                                          19^2
622                                        2*90^2                                          31^2
623                                  3040742304^2                                   958046297^2
629                                       629*1^2                                          10^2
631                              84388339390660^2                              84042085995171^2
638                                     11*2019^2                                      2*4375^2
645                                         5*5^2                                           2^2
646                                         2*3^2                                           1^2
647       1149852430778431376586487272927719076^2        763331759345415695713922022788822893^2
651                                         7*2^2                                         3*1^2
653         653*4956148647851982833406804183365^2           119088454066039826980851213749474^2
654                                      218*13^2                                         121^2
655                                      5*7085^2                                     131*178^2
658                                         2*8^2                                        47*1^2
661                          661*52573871914105^2                            1337443404825678^2
663                                        13*5^2                                        51*2^2
669                                          14^2                                         3*3^2
670                                        67*3^2                                        2*11^2
671                                           6^2                                           5^2
674                                       337*1^2                                        2*12^2
677       677*266071911559565396617913225699185^2          6090385733713292676671917039688234^2
678                                      2*1885^2                                        2567^2
679                                     4829572^2                                     4736355^2
685                                  685*384709^2                                     3760398^2
687                                     229*181^2                                       3*370^2
689                                       689*1^2                                          20^2
694                                       2*269^2                                         329^2
695                                    5*107633^2                                   139*13862^2
701                      701*778126037665372045^2                        20381058964400398922^2
703                                     1176802^2                                      879777^2
709                                      709*17^2                                         210^2
710                                       10*12^2                                          37^2
717                                  3*42438120^2                                      665543^2
718                          2*4524903101629650^2                            2549487886137199^2
719                                       18720^2                                       16511^2
721                                         7*4^2                                           3^2
723                                         103^2                                        3*20^2
727      16213151558097443674133462376327492124^2      11607920028365757398549972945257395957^2
731                                          39^2                                        43*4^2
733            733*7587780721511267936796299165^2              175714842077423718884281543602^2
734                                       2*644^2                                         137^2
741                                           4^2                                         3*1^2
742                                    106*4334^2                                       25983^2
743              664892406397562627531460993684^2               70167984148003728340455310237^2
749                                      107*44^2                                         307^2
751                                         520^2                                         231^2
757 757*134047218103304241673334209140989001305^2    2498951123086366985427431466492641572998^2
758                        2*121343494129262725^2                           13640465896081927^2
759                                         3*2^2                                        11*1^2
761                                      761*29^2                                          40^2
766                                 2*588188916^2                                   153301273^2
767                                    14526198^2                                     3869323^2
773                          773*35770654935185^2                             628933159841954^2
777                                        37*2^2                                         3*3^2
781                                     2079450^2                                   11*578677^2
782                                       2*110^2                                          71^2
789                                     3*53196^2                                       83339^2
790                                       10*88^2                                          39^2
791                                       113*1^2                                         7*4^2
793                                       793*5^2                                         132^2
797 797*6509757429070914743924008309828829377565^2   77437998217120395728776728661988058847754^2
798                                         2*4^2                                           5^2
799                                           8^2                                        17*1^2
805                                           9^2                                         5*4^2
806                                        31*1^2                                         2*3^2
807                                    20388278^2                                     6378229^2
813                                          14^2                                         3*5^2
814                                        74*1^2                                           5^2
815                                    63306722^2                                    60351761^2
821                                     821*905^2                                        6118^2
822                                    2*178445^2                                      221999^2
823    1800731922098507686862624200977450853996^2    1093332003924633933040927920553338780747^2
829               829*1114687145192391935645405^2                  13332313139036257353598962^2
830                                        83*9^2                                        2*29^2
831                                 277*4899877^2                                  3*13289406^2
838                             2*8009381984165^2                               1735885783193^2
839                                      959700^2                                      893651^2
853                        853*1555403055469705^2                           41407411349159166^2
854                                        7*41^2                                        2*27^2
861                                       21*11^2                                          50^2
862                      2*31754083744528352940^2                        44433441426033013319^2
863                      1365999649102602102024^2                      1363371767025194841143^2
866                                          19^2                                         2*6^2
869                                      11*208^2                                         535^2
870                                       145*1^2                                         6*2^2
871                                        3646^2                                        3579^2
877                 877*98019289159914592820005^2                    285144044108203957571958^2
878                                   2*1564070^2                                     2155561^2
879                                          62^2                                          59^2
885                                         632^2                                       59*59^2
886                                   2*1812317^2                                     2229703^2
887          2129987769776435785528571874098484^2           613374508678206671797659663089437^2
889                                           8^2                                         7*3^2
890                                           7^2                                        10*2^2
893                                   314604694^2                                 19*13026563^2
894                                       3*681^2                                        2*73^2
895                                       5*169^2                                      179*22^2
901                                       17*13^2                                        53*4^2
902                                      2*1625^2                                        2297^2
903                                        43*2^2                                         3*1^2
905                                       181*1^2                                         5*6^2
910                                        65*1^2                                        14*2^2
911              101674006024983403715286392160^2              101247414652636878045579297649^2
915                                        61*1^2                                        15*2^2
917                                    79016186^2                                 131*3187071^2
919                                   415257700^2                                   307783011^2
926                           2*207949336647956^2                              65855561465047^2
933                              3*627284421900^2                                906169058509^2
934                                       2*137^2                                          17^2
935                                          52^2                                          47^2
941                           941*6949430837141^2                             212353330183010^2
943                                       41*29^2                                       23*20^2
949                                       949*1^2                                          30^2
951                                          14^2                                          11^2
957                                        29*1^2                                           2^2
958                         2*64137447275611920^2                           86812781740303009^2
959                                          72^2                                          65^2
965                                965*37658777^2                                   268747634^2
966                                        23*1^2                                         2*1^2
967                  40855341363101303203686796^2                  31495021407376795594262853^2
973                                          74^2                                       139*3^2
974                             2*1209837172766^2                                359802927673^2
982                          2*3361484998004965^2                            1361998041016823^2
985                                      985*13^2                                         408^2
987                                        21*4^2                                          17^2
989                                      211066^2                                    43*23387^2
991                                372979863880^2                                355105187961^2
995                                         5*8^2                                          11^2
997 997*205768636979011246293067486487264646177793235665^2 1939472939861978131500861593607331562307144802554^2
998                       2*7036245713483923165^2                         6759000852285855817^2

An incomplete table for 1000 to 2000

One of the motivations for writing the code in this posting was to try computing the side lengths for N > 1000. Of the 358 square-free congruent numbers between 1000 and 2000, the code was able to find sides for all but 50. I’d be thrilled to hear about more sophisticated algorithms that can compute these missing entries.  Here are the entries I was able to compute, also available as a separate file.

 
1003                                    63^2                                 59*4^2
1005                                 5*565^2                                 1202^2
1006                               2*36354^2                                51343^2
1007                             640869638^2                            587562763^2
1013
1015                                 29*13^2                                 35*2^2
1021                           1021*257149^2                              7820010^2
1022                                  2*20^2                                   17^2
1023                                  7664^2                               33*375^2
1030                              103*1327^2                               2*1271^2
1031                       553773154545780^2                      313927967546509^2
1037                            1037*23725^2                               735278^2
1038                                  3*33^2                                 2*23^2
1039                           19222641880^2                            464534841^2
1045                                  5*13^2                                209*2^2
1046                               2*54433^2                                62033^2
1047                            349*815413^2                            3*6269390^2
1054                                2*1692^2                                 1561^2
1055                             5*2218957^2                           211*235258^2
1057                                   247^2                                   96^2
1061                1061*11017137603102721^2                    52393391142142750^2
1063
1069
1070                             107*41187^2                             2*256331^2
1073                                    23^2                                   14^2
1077                                 3*880^2                                 1237^2
1079                                    54^2                                   29^2
1081                                    35^2                                   12^2
1085                                  35*4^2                                   23^2
1086                                 362*1^2                                    1^2
1087           534490229096555257177885984^2          504876251097996356696056863^2
1093
1094                                 2*409^2                                  511^2
1095                                    14^2                                   13^2
1101                                  6734^2                               3*3333^2
1102                             19*330627^2                             2*724355^2
1103                                   816^2                                  287^2
1105                                     7^2                                    6^2
1109
1110                                   2*4^2                                  5*1^2
1111                                    10^2                                    1^2
1113                                   7*2^2                                    5^2
1117
1118                                 26*53^2                                  197^2
1119                           373*5047393^2                           3*56058478^2
1122                                     5^2                                  2*2^2
1126                                 2*953^2                                  113^2
1131                                     4^2                                 13*1^2
1133                                104354^2                             11*31341^2
1135                               4317302^2                              1209899^2
1141                          163*20033248^2                             35220117^2
1142                    2*3498126297122005^2                     3101671470103703^2
1145                                1145*5^2                                   52^2
1146                                  2*13^2                                191*1^2
1149                            3*10180232^2                             17116727^2
1151                             126739920^2                            124197361^2
1154                                    17^2                                 2*12^2
1155                                  11*1^2                                    2^2
1157                     1157*101695523225^2                        1997676115478^2
1158                                 193*5^2                                 6*24^2
1159                                  61*5^2                                 19*6^2
1165                             1165*1037^2                                24366^2
1166                               106*229^2                                  565^2
1167                        80234354894378^2                       69040110896471^2
1169                                  7*12^2                                   29^2
1173                                69*273^2                                 1718^2
1174                         2*10970739277^2                           5524968023^2
1178                                   2*5^2                                 31*1^2
1181
1182                             3*2494283^2                             2*170977^2
1185                                     8^2                                 15*1^2
1186                                   257^2                                2*136^2
1189                               1189*65^2                                 1518^2
1190                                   2*3^2                                 17*1^2
1191                           397*4319701^2                           3*43476026^2
1195                                    22^2                                  5*7^2
1198                         2*79342901670^2                          10971111209^2
1199                            4846487934^2                           4826824675^2
1201                                    25^2                                   24^2
1205                                    31^2                                 5*12^2
1207                              11643884^2                             10025013^2
1213
1214                            2*18094076^2                             12405353^2
1217                               1217*65^2                                 1504^2
1221                                 37*17^2                                33*14^2
1222                                47*151^2                                2*731^2
1223
1229                 1229*3171885776594453^2                    22661957001363890^2
1230                                 123*1^2                                  2*1^2
1231                1093893124029377517040^2                508787759180739534831^2
1237
1238
1239                                   596^2                               177*37^2
1241                                    29^2                                   20^2
1245                                 5*449^2                                  982^2
1246                                  2*24^2                                   23^2
1247                             500503826^2                            493934857^2
1249                                   481^2                                  360^2
1253                            179*139708^2                              1576963^2
1254                                  11*1^2                                  2*2^2
1255                           5*130143077^2                          251*4799482^2
1261                             1261*6205^2                               211494^2
1262     2*5146561601772899976047772998810^2      5187845455908637659823361579711^2
1263                          421*72473677^2                          3*805599790^2
1270                              127*1561^2                               2*5381^2
1271                                  41*5^2                                 31*4^2
1277
1279               73978703287659341689600^2              38338545749238184291809^2
1282                                 641*1^2                                 2*10^2
1285                             1285*1105^2                                 8358^2
1286                      2*10448952878281^2                       10529188863199^2
1293                          3*1697884540^2                           2937063841^2
1294                             2*4872522^2                              1370959^2
1295                                     6^2                                    1^2
1301                 1301*3117192484228345^2                    77237364746203922^2
1302                                    11^2                                  6*4^2
1303
1309                                  77*3^2                                   26^2
1310                             10*153829^2                               432161^2
1311                                  23*1^2                                    2^2
1317
1318                       2*1428058929085^2                         592793094313^2
1319                2483679569975131134420^2               1474854640815874983299^2
1321                                 37669^2                                27060^2
1326                                  26*1^2                                    5^2
1327
1330                                  14*1^2                                  5*1^2
1333                                   206^2                                43*15^2
1334                                 58*48^2                                  133^2
1335                                  4258^2                                 4169^2
1339                                    34^2                                 13*9^2
1342                            11*6293233^2                           2*11110465^2
1343                            1513392816^2                             87126737^2
1346                                   239^2                                2*168^2
1349                          19*572172984^2                           1718426035^2
1351                                    92^2                                193*3^2
1357                             59*799332^2                              6119003^2
1358                                 2*170^2                                  239^2
1365                                   5*2^2                                  7*1^2
1366                      2*75067556653673^2                         276597312593^2
1367             2210029442288216604321564^2            1092492023913676770056123^2
1373
1374                             458*39481^2                               518017^2
1379                                 197*1^2                                  7*2^2
1381                    1381*5877838501505^2                       85358642942118^2
1382
1383                                  8114^2                                 6527^2
1387                                 73*25^2                                19*48^2
1389                              28962134^2                           3*15288133^2
1390                             10*529105^2                              1452477^2
1391                              13*55241^2                            107*14214^2
1393                                  1724^2                               199*57^2
1397                                  11*4^2                                    7^2
1398                                 2*205^2                                   23^2
1399                             140108980^2                             24481971^2
1405                                    19^2                                  5*4^2
1406                                  19*1^2                                  2*3^2
1407                               67*4694^2                               3*9411^2
1411                                    79^2                                 83*4^2
1414                                7*2329^2                               2*4237^2
1415                                  6998^2                                 4451^2
1419                                   3*3^2                                    4^2
1423       7846891217457546585817785748936^2      6692442382211391072755148372327^2
1429
1430                                   2*8^2                                 13*3^2
1434                                  6*10^2                                   19^2
1437                           3*359821900^2                            579736247^2
1438                      2*44553108632760^2                       37487295533089^2
1439             1008014492965566903395280^2             960164863865618935964209^2
1443                                     5^2                                  3*2^2
1446                                  2*11^2                                    1^2
1447
1453
1454                               2*59006^2                                38953^2
1455                                  1586^2                                  263^2
1461                                  9314^2                               3*2233^2
1462                                  34*1^2                                    3^2
1463                                  11*2^2                                 19*1^2
1469                                  13*3^2                                    2^2
1471          1928596035670269313433517160^2         1779886513628987622022447431^2
1477                      211*220919758676^2                        1248458528883^2
1478
1479                                    16^2                                   13^2
1482                                  19*1^2                                  6*1^2
1486                        2*239711193546^2                           8032739393^2
1487                4658308462162163630976^2               1320338709334411132607^2
1493                               1493*25^2                                  434^2
1495                                   202^2                                   87^2
1501                                  19*4^2                                   15^2
1502                          2*2028737420^2                            311366489^2
1509                         3*58309238416^2                           6189441829^2
1510                                  10*4^2                                    3^2
1511                                   780^2                                  731^2
1513                                  89*1^2                                    8^2
1517                                  1181^2                               37*160^2
1518                                   125^2                                22*13^2
1526                                218*16^2                                   19^2
1527                       591153019517366^2                      572357977499363^2
1533                                 28262^2                               3*5805^2
1534                                59*113^2                                 2*29^2
1535                          702318605942^2                         469355582779^2
1541                                    58^2                                 67*7^2
1542                                 2*265^2                                  287^2
1543
1549
1551                                 3*106^2                                11*23^2
1558                               2*24125^2                                20113^2
1559            46558955761464766823805420^2           40991718920623965561016069^2
1561                                   116^2                                223*3^2
1565                               1565*61^2                                 1078^2
1567                                  1624^2                                   57^2
1574
1581                                  93*3^2                                    2^2
1582                                    13^2                                 14*2^2
1583
1589                            1955370754^2                         227*95700609^2
1590                                 265*1^2                                  6*4^2
1591                                    22^2                                   21^2
1595                                   5*2^2                                    3^2
1597
1598                                    39^2                                 94*4^2
1599                                   236^2                                  115^2
1605                                  5*17^2                                   38^2
1606                                2*2269^2                                 1751^2
1607
1610                                  14*1^2                                    3^2
1613
1614                                3*1091^2                               2*1021^2
1615                                85*101^2                                19*42^2
1621
1622
1623                            541*818977^2                            3*8400690^2
1630                                163*81^2                                2*209^2
1631                                    11^2                                  7*4^2
1633                                   324^2                                23*25^2
1635                                 109*1^2                                 15*2^2
1637
1639                           93119931626^2                          17274220825^2
1645                                   381^2                                 5*76^2
1646                               2*10502^2                                12361^2
1649                                1649*1^2                                   40^2
1651                                  13*4^2                                    9^2
1653                                 29*61^2                                  278^2
1654                          2*5099522713^2                           7191812593^2
1655                         5*15944597077^2                       331*1593316982^2
1659                                    10^2                                 21*1^2
1661                          11*449674700^2                           1128819629^2
1662                                 554*1^2                                   23^2
1663
1669                               1669*17^2                                  690^2
1670                                167*41^2                                2*331^2
1671                            4709357954^2                           4709150447^2
1677                                 13*25^2                                129*6^2
1678                    2*2197332480074250^2                     2986757644280911^2
1679                                    83^2                                23*12^2
1685                      1685*10780079129^2                         323265236278^2
1686                               2*30193^2                                 9553^2
1687                        20020795748764^2                       14313931423077^2
1693
1695                                     8^2                                    7^2
1702                           23*83377711^2                          2*259732823^2
1703                          13*136174385^2                         131*42165966^2
1705                                   5*2^2                                 11*1^2
1709                         1709*56899397^2                           1914111430^2
1711                                29*281^2                               59*130^2
1717                                101*13^2                                   38^2
1718                       2*1622842557865^2                         432593825023^2
1726               2*232211988542532693804^2                206435450751981013463^2
1727                               157*265^2                               11*858^2
1731                                 577*1^2                                  3*4^2
1733
1735                               1247378^2                              1029289^2
1741
1742                           67*10122299^2                           2*15946527^2
1743                               3041032^2                            249*85593^2
1745                                 349*1^2                                  5*6^2
1749                                     8^2                                 11*1^2
1751                                  17*4^2                                   13^2
1757                            8065011826^2                        251*412114251^2
1758                        3*102985227451^2                       2*121557212519^2
1759
1762                                 881*1^2                                 2*20^2
1765                          1765*1965793^2                             29034642^2
1766                          2*1241178349^2                            748018649^2
1767                              19*18578^2                              3*43325^2
1770                                   2*4^2                                  3*3^2
1774                                 2*234^2                                  257^2
1781                         1781*64281065^2                           1800656762^2
1783    4792743876089805249498502926760516^2   4210256678211637838081213167457613^2
1785                                   3*2^2                                  5*1^2
1789
1790                             10*178841^2                               493243^2
1794                                  26*1^2                                 23*1^2
1797                          3*5264857000^2                           4228721773^2
1798                           31*10911449^2                            2*7818425^2
1799                                  1740^2                                   59^2
1806                                    47^2                                 6*19^2
1807                             13*408185^2                           139*121818^2
1814                             2*1024057^2                               931217^2
1821                                661934^2                             3*220917^2
1822                               2*17520^2                                23471^2
1823    7761300340225847160065004009945984^2   7073498453526479365692239139413137^2
1829                           59*29844700^2                            181206031^2
1830                                  3*29^2                                122*1^2
1831                            3565715500^2                           2898888171^2
1837
1838               2*640482037573884561770^2                768308549845289572991^2
1839                                613*97^2                                3*294^2
1846                                71*217^2                                2*439^2
1847
1853                       1853*1327014805^2                          56375498794^2
1855                                  1222^2                                  493^2
1858                                    27^2                                 2*10^2
1861
1869                                  21*3^2                                   10^2
1870                                  2*16^2                                 17*1^2
1871
1877
1878                                  2*13^2                                    5^2
1879                            4130777980^2                           1199536101^2
1885                                  29*1^2                                    4^2
1886                                   2*4^2                                    3^2
1887                                  6044^2                                 5119^2
1893                       206546260507082^2                     3*64269514053185^2
1894                        2*324087672709^2                         213795376151^2
1895
1901
1902                        3*900186672163^2                       2*946544303197^2
1903                                114182^2                                19043^2
1909                               4644138^2                             83*21329^2
1910                                  10*6^2                                   13^2
1918                                     9^2                                 14*2^2
1919                               101*197^2                               19*310^2
1927                               1654276^2                               634893^2
1933
1934                              2*127958^2                               180551^2
1939                                 277*1^2                                  7*6^2
1941                      3*22087563983576^2                       35655089110091^2
1942                  2*127615924034303765^2                    89779252381023607^2
1943                              29*16613^2                              67*2990^2
1949
1951
1957                            19*3285772^2                              7471773^2
1958                                  2*15^2                                 89*1^2
1959                        45651794958266^2                       34244727779041^2
1965                                   136^2                               131*11^2
1966                  2*378280891208203374^2                   484645319443334263^2
1967                                 12419^2                               7*4340^2
1973
1974                                  42*2^2                                   11^2
1981                                   506^2                               283*27^2
1982                           2*472837460^2                             48441881^2
1983                                 661*1^2                                 3*10^2
1990                           10*64794470^2                             85105071^2
1991                              181*1193^2                              11*1350^2
1995                                   5*2^2                                    1^2
1995                                   3*2^2                                  7*1^2
1997
1999

embedded-druid: Leveraging Druid Capabilities in Stand-alone Applications

Co-authors:  Ramachandran Ramesh, Mahesh Somani, and Sankar Venkatraman

The eBay Cloud Platform team is happy to announce the open-source project embedded-druid, which aims to provide Druid capability for a reasonably small amount of data without involving the complexity of multi-node setup. That is, embedded-druid is Druid but with a single JVM process.

Background

Druid is an open-source data store designed for real-time exploratory analytics on large data sets. Combining a column-oriented storage layout, a distributed, shared-nothing architecture, and an advanced indexing structure, Druid allows for the arbitrary exploration of billion-row tables with sub-second latencies. It also supports fast aggregations and OLAP queries. Druid is proven technology for executing OLAP kinds of queries involving Big Data, and for providing sub-second response times.

Motivation

Given its distributed, shared-nothing architecture for large amounts of data, Druid has multiple components: real-time node, historical node, broker node, co-ordinator node, deep storage, MySQL, ZooKeeper, etc. If the input data size is small (say, up to hundreds of millions of rows), then the overhead involved in deploying Druid might be excessive; one might prefer to use in-memory database systems like Apache Derby or PostgreSQL if the report requirement is very simple (such as grouping by some dimension or retrieving topN values). There are numerous use cases where the input is not “Big Data” but rather medium or small data requiring OLAP-like capabilities, such as grouping by multiple dimensions and handling percentile and other aggregation functions.

For example, in eBay we generate operational metrics reports for applications that run on multiple machines across data centers. This report contains total request counts, average request durations, etc. across different dimensions, such as the type of request, data center, request status, dependency, etc. Each application owner might view different types of information from this report – top hosts with errors, slowest requests by request type / data center, or requests by error code, as just a few examples. Given the dynamic nature of such queries, if Druid capabilities can be leveraged without deployment complexity, then the lives of developers, debuggers, and analysts can be made much easier.

embedded-druid in action

Let us assume a simple database that represents the number of characters added for a particular page in Wikipedia. We have the following columns representing the dimensions for our data:

Timestamp, Page, Username, Gender, City

Here is the metric we are interested in:

CharsAdded

The following table shows sample data for the above schema:

Timestamp Page Username Gender City CharsAdded
1234567 JB Abc Male SF 1290
1234576 JB Xyz Female SJ 3421
1234687 AB Qwe Male LA 2345
1234789 AB Def Female LV 1234

We want to generate different reports, such as “How many edits were made on page AB grouped by gender?” or “What is the histogram for edits made on page JB in SF?” The following sections walk through how to generate such reports using embedded-druid.

Creating the loader

Currently, embedded-druid supports loading CSV files, for which the implementation class CSVLoader is available. One needs to first provide a list of all columns available in the CSV file (including metrics), a list of dimensions, and a column specifying the timestamp (if available). For example, for the Wikipedia schema mentioned above, the CSV file might have data in this format:

Timestamp, Page, Username, Gender, City, metric, value

The following code creates the Loader object required to load this data in memory:

List<String> columns = Arrays.asList("Timestamp", "Page", "Username", "Gender", "City", “metric”, “value”);

    List<String> metrics = Arrays.asList("value");
    List<String> dimensions = new ArrayList<String>(columns);
    dimensions.removeAll(metrics);

    Loader loader = new CSVLoader(reader, columns, dimensions, "Timestamp");

Creating Druid segment/index files

Druid generates segment and index files for the given input. Once the Loader object is created, one needs to specify segment and index files required for query purposes. This specification includes the available dimensions and the kind of aggregator function to be used for querying. For example, if one is interested in querying values like total count, max, min, total sum, and percentiles, then the following AggregatorFactory objects need to be created:

DimensionsSpec dimensionsSpec = new DimensionsSpec(dimensions, null, null);
AggregatorFactory[] metricsAgg = new AggregatorFactory[] {
        new LongSumAggregatorFactory("agg_count", "count"),
        new MaxAggregatorFactory("agg_max", "max"),
        new MinAggregatorFactory("agg_min", "min"),
        new DoubleSumAggregatorFactory("agg_sum", "sum"),
        new ApproximateHistogramAggregatorFactory("agg_histogram", "value", null, null, null, null)
    };

To create segment and index files locally, one needs to create a QueryableIndex object as follows:

IncrementalIndexSchema indexSchema = new IncrementalIndexSchema(0, QueryGranularity.ALL, dimensionsSpec, metricsAgg);
QueryableIndex index = IndexHelper.getQueryableIndex(loader, indexSchema);

By default, segment files are created at the location System.getProperty("druid.segment.dir"). If this property is not set, then the files will be created at the temporary location System.getProperty("java.io.tmpdir") + File.separator + "druid-tmp-index-". Therefore, if one wants to create segment files at a specified location, then  property “druid.segment.dir” needs to be set first.

Querying data

Once segment files are created, one can execute different kinds of queries using the QueryableIndex object. For example, if one wants to execute GroupByQuery for the above mentioned schema, then the code looks like this:

List<DimFilter> filters = new ArrayList<DimFilter>();
filters.add(DimFilters.dimEquals("Page", "JB"));
filters.add(DimFilters.dimEquals("Gender", "Male"));
filters.add(DimFilters.dimEquals("metric", "CharsAdded"));

GroupByQuery query = GroupByQuery.builder()
        .setDataSource("test")
        .setQuerySegmentSpec(QuerySegmentSpecs.create(new Interval(0, new DateTime().getMillis())))
        .setGranularity(QueryGranularity.NONE)
        .addDimension("City")
        .addAggregator(new LongSumAggregatorFactory("agg_count", "agg_count"))
        .addAggregator(new MaxAggregatorFactory("agg_max", "agg_max"))
        .addAggregator(new MinAggregatorFactory("agg_min", "agg_min"))
        .addAggregator(new DoubleSumAggregatorFactory("agg_sum", "agg_sum"))
        .addAggregator(new ApproximateHistogramFoldingAggregatorFactory("agg_histogram", "agg_histogram", 20, 5, null, null))
        .addPostAggregator(new QuantilesPostAggregator("agg_quantiles", "agg_histogram", new float[] {0.25f, 0.5f, 0.75f, 0.95f, 0.99f}))
    .setFilter(DimFilters.and(filters))
    .build();
Sequence<Row> sequence = QueryHelper.run(query, index);
    ArrayList<Row> results = Sequences.toList(sequence, Lists.<Row>newArrayList());

Similarly, here is the code snippet for executing TopNQuery:

List<DimFilter> filters = new ArrayList<DimFilter>();
filters.add(DimFilters.dimEquals("Page", "JB"));
filters.add(DimFilters.dimEquals("Gender", "Male"));
filters.add(DimFilters.dimEquals("metric", "CharsAdded"));

TopNQuery query =
        new TopNQueryBuilder()
            .threshold(5)
            .metric("agg_count")
            .dataSource("test")
            .intervals(QuerySegmentSpecs.create(new Interval(0, new DateTime().getMillis())))
            .granularity(QueryGranularity.NONE)
            .dimension("City")
            .aggregators(
                Arrays.<AggregatorFactory>asList(
                    new LongSumAggregatorFactory("agg_count", "agg_count"),
                    new MaxAggregatorFactory("agg_max", "agg_max"),
                    new MinAggregatorFactory("agg_min", "agg_min"),
                    new DoubleSumAggregatorFactory("agg_sum", "agg_sum"))
            .filters(DimFilters.and(filters))
            . build();

Sequence<Result> sequence = QueryHelper.run(query, index);
    ArrayList<Result> results = Sequences.toList(sequence, Lists.<Result>newArrayList());

Future work

We are planning to extend this work by providing (and/or integrating) REST APIs for ingestion and for querying Druid data. For visualization, we also plan to integrate with an easy-to-use UI like Grafana. These enhancements will help users analyze data quickly and surface meaningful information promptly.

Congruent Numbers Part I

Usually my posts have a connection to eBay, but this time I’m writing about a recreational math problem that caught my attention.

Introduction

One of the most famous facts of mathematics is that a triangle with sides of length 3, 4, and 5 is a right triangle, which means it can be drawn with a horizontal base and a vertical side, forming a right angle. Since the area of a triangle is one-half base times height, this triangle has area \frac{1}{2}(3 \times 4) = 6.
right_triangle
Is there a right triangle with area 5? Of course there is, since a right triangle with a base of length 1 and height 10 has area 5. But the third side (the hypotenuse) has length \sqrt{101}, which is not an integer.

That the side is {\scriptstyle \sqrt{101}} follows from the famous Pythagorean theorem of high-school geometry, which says that if two sides of a right triangle have lengths {\scriptstyle \alpha} and {\scriptstyle \beta}, then the third side has length {\scriptstyle \gamma} with {\scriptstyle \gamma^2 = \alpha^2 + \beta^2}. So when {\scriptstyle \alpha = 1} and {\scriptstyle \beta = 10}, the third side has length {\scriptstyle \gamma = \sqrt{101}}. The converse of the Pythagorean theorem is also true. It says that if {\scriptstyle \gamma^2 = \alpha^2 + \beta^2}, then the triangle with side lengths = {\scriptstyle \alpha, \beta, \gamma} is a right triangle. In particular, the triangle with sides of length 3, 4, and 5 is a right triangle since {\scriptstyle 3^2 + 4^2 = 5^2 = 25}.

If you require all three sides of a triangle to be integers, then there is no right triangle with area 5. A brute-force enumeration verifies this, and easily shows that 6 is the smallest, and the next few N after 6 that are the area of a right triangle are 24, 30, 54, 60. So asking if there is a right triangle with integer area N appears to be of little interest. But what if you allow rational sides? It’s possible for the height and width to be non-integer fractions, but have integer area. And in fact there is such a triangle with area N=5. The equation

    \[ \left(\frac{3}{2}\right) ^2 + \left(\frac{20}{3}\right) ^2 = \left(\frac{41}{6}\right) ^2 \]

shows that a triangle with sides \alpha = 3/2, \beta = 20/3 and \gamma = 41/6 is a right triangle. The area is \frac{1}{2} \alpha \beta = 5.

An integer N that is the area of a right triangle having all sides of rational length is called congruent. What numbers are congruent? Detecting them has something in common with detecting primes. There is a fast test to see if a number is prime or composite, but it’s a lot harder to obtain direct evidence that a number is composite by producing its factors. Similarly, there is a fast test to see if a number is congruent, but it is hard to find the side lengths \alpha, \beta, \gamma that demonstrate directly that N is congruent.

The analogy isn’t exact, because the direct test for congruent numbers isn’t guaranteed to work. More precisely, there is a proof that it works, but the proof depends on an unproven hypothesis called the Birch and Swinnerton-Dyer conjecture.

The reason it can be hard to find the sides is that they can be fractions with a lot of digits. For example, the sides of a right triangle with area N=79 are

    \[ \left(\frac{335946000}{2950969}\right)^2 + \left(\frac{233126551}{167973000}\right)^2 = \left(\frac{56434050774922081}{495683115837000}\right)^2 \]

I found tables on several web sites containing the side lengths for all congruent numbers less than 1000, but I believe they are all copies of the same table, because they all have an identical glitch at N = 559 which I will explain shortly.

The table appears on multiple web sites, but these variants are identical except for a misprint in the entry for {\scriptstyle N=199}. It has the incorrect value {\scriptstyle 27368486201} on all but the site http://bitman.name/math/table/29, which has the correct value {\scriptstyle 2736848\underline{7}6201}. However, that site has a different misprint at {\scriptstyle N=31} which says that {\scriptstyle D=103020} but it should be {\scriptstyle 103\underline{3}20}.

Why

In this posting and the next I will explain my efforts to compute the sides of a triangle with area N. I got interested in this problem because

  • I wondered how it was done.
  • I wanted to compute sides for N > 1000.
  • I wanted to check if the existing table can be improved.

I found the existing table can indeed be improved, as I now explain. The rational sides demonstrating that N is congruent are not unique. For example, 6 is the area of a triangle with sides (3,4,5) and also (120/7, 7/10, 1201/70).

Elliptic curve theory explains why there are infinitely many triangles for each area. It gives a formula that takes any set of sides and produces a new set of sides.

I’ll always try to find the example with the smallest denominators. So I prefer (3,4,5) (denominator of 1) to (120/7, 7/10, 1201/70) (denominator of 70).

After I wrote my own code to generate a table of side lengths, I discovered that the web table doesn’t always give sides with the smallest denominator. Two examples are below, where the triangle sides are \alpha, \beta, \gamma.

Rendered by QuickLaTeX.com

Plot

How big (how many digits) are the numerator and denominator of the sides? I used the web table to plot the number of digits needed for the denominator D of the length of the hypotenuse \gamma against the area N. The plot is below. The vertical axis is \log_{10}D which is the number of base-10 digits in the denominator D. Note that prime values of N (blue) generally require more digits than composite numbers do.

The straight line suggests that the number of digits needed for the denominator increases linearly with N. In other words, the size of D is exponential in N.

congruent

Elementary method of computing the triangles

In this section I explain in detail a search method for finding the sides for the triangle of area N that can easily find the fractions for N=79, which are

    \[ \left(\frac{335946000}{2950969}\right)^2 + \left(\frac{233126551}{167973000}\right)^2 = \left(\frac{56434050774922081}{495683115837000}\right)^2 \]

A brute-force exhaustive search for N=79 would find the fractions \alpha = 335946000/2950969 and \beta = 233126551/167973000 by trying all \alpha = a/d with integers a, d having up to k=9 digits (and similarly for \beta). That is n^4 possibilities, where n = 10^k. This search would take a long time, n^4 = 10^{36}. There are some simple tricks that make it much faster to find the fraction by brute force.

Going back to sides for the congruent number N=5,

    \[ \left(\frac{3}{2}\right) ^2 + \left(\frac{20}{3}\right) ^2 = \left(\frac{41}{6}\right) ^2 \]

Rewrite the equation to have a common denominator.

    \[ \left(\frac{9}{6}\right) ^2 + \left(\frac{40}{6}\right) ^2 = \left(\frac{41}{6}\right) ^2 \]

The numerators satisfy

    \begin{eqnarray*} 9^2 + 40^2 & = & 41^2 \\ 81 + 1600 & = & 1681 \end{eqnarray*}

A triple of such integers is called a pythagorean triple. This link between congruent numbers and Pythagorean triples holds in general, as summarized below:

Rendered by QuickLaTeX.com

So from rational numbers \alpha, \beta, and \gamma you get integers A and B that are Pythagorean, meaning A^2 + B^2 is a square. I’ll always assume that any factor common to all of A, B, C, and D has been removed, in other words that \gcd(A,B,C,D) = 1. Also note that if N is congruent, then multiplying the sides of its triangle by the integer k shows that k^2N is congruent. And conversely, if you have a triangle showing that k^2N is congruent, divide the sides by k to get a triangle for N. So I only need to consider square-free N.

Here are the first few square-free congruent numbers.

Rendered by QuickLaTeX.com

Note that in each case the denominator of \gamma is the product of the denominators of \alpha and \beta. A proof that this is always so is in the final post of this three-part series.

Pythagorean triples (A, B, C) can be written in the form

(1)   \begin{eqnarray*} A &=& 2PQ \\ B &=& P^2 - Q^2 \qquad (\mbox{with } P > Q) \nonumber \\ C &=& P^2 + Q^2 \nonumber \end{eqnarray*}

The proof of this can be found on the web and in most number theory textbooks under the name Euclid’s Formula, but I also give a proof in the final post of this series. The formulas can be rewritten as

(2)   \begin{eqnarray*} P &=& \sqrt{\frac{C+B}{2}} \\ Q &=& \sqrt{\frac{C-B}{2}} \nonumber \\ \end{eqnarray*}

So there is a 1-1 correspondence between \alpha, \beta, \gamma and P, Q. Specifically, starting with \alpha, \beta, \gamma you rewrite with a common denominator to get A, B, C and then use (2) to get P, Q. Conversely, given P and Q use (1) to compute A, B, C, and then get D using

(3)   \begin{equation*}  % \frac{AB}{2D^2} = N \qquad D = \sqrt{\frac{AB}{2N}} = \sqrt{\frac{PQ(P^2 - Q^2)}{N}} \frac{AB}{2D^2} = N \qquad D = \sqrt{\frac{AB}{2N}} \end{equation*}

Finally, reduce A/D to get \alpha = a/d, similarly for \beta = b/e.

This means that a brute-force search can be done using only two integers P and Q (with P > Q) instead of four integers a, b, d, and e. What is their size? If a, b etc. have k digits, then A, B etc. have 2k digits and P, Q have k digits, so brute force is now n^2 = 10^{2k} \approx 10^{18}. Huge but smaller than 10^{36}.

Here is a table of the first few square-free congruent numbers represented as P and Q:

Rendered by QuickLaTeX.com

Note that P and Q are always of opposite parity (that is, one is odd and the other even). As I’ll explain in the final post, once you remove any common factors from (A,B,C,D) then P and Q must be of opposite parity. This is the glitch in the web table I mentioned earlier. For N=559, the web table gives P=2608225, Q=4489, which are both odd. If you use them to generate (A,B,C,D) you will find they all have a common factor of 2. If you remove this factor and recompute P, Q you get P' = 1306357, Q'= 1301868 with P' < P.

A major improvement in exhaustive search can be made by noting the special form of P and Q. You can see the pattern in the following table of P and Q, where they are written in partially factored form.
Rendered by QuickLaTeX.com
For entries in the table, P is a square, or a square times a divisor of N, and similarly for Q. As N=30 shows, both P and Q can have divisors. Stated more formally, P = sP_0^2 and Q = tQ_0^2 where st|N. Since this is true for all numbers in the table above, it’s plausible that it’s true in general, and I’ll show that in the final post.

This property means you only need to search up to the square root of P and Q. In other words, you only need to check n = 10^{k/2} values of P and similarly for Q, so exhaustive search takes n^2 = 10^k \approx 10^9 steps when N=79. This  can be done in less than a minute, at least on my laptop.

I won’t bother to give the code, because although it easily computes the sides for N=79 it can’t get the side lengths for more challenging areas such as N=157. In the next post I’ll explain an improved algorithm using elliptic curves and give code for the SageMath system that can solve N=157.

Powered by QuickLaTeX