This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/BinaryQuadraticForms

From OeisWiki

Jump to: navigation, search

Positive Numbers
represented by a
Binary Quadratic Form

Aim of this post is to implement the methods for calculating the numbers represented by a binary quadratic form in a uniform and efficient way in Sage and hiding the complexity of the situation by providing a simple interface to the user. This blog post was inspired by the Wiki page created by N. J. A. Sloane, see: Binary Quadratic Forms and OEIS

Contents

Definitions

A binary quadratic form over Z is a quadratic homogeneous polynomial in two variables with integer coefficients, q(x, y) = ax^2 + bxy + cy^2. It is conveniently given by a list or tuple of 3 entries: (a, b, c).

A quadratic form q(x, y) represents an integer n if there exist integers x and y with q(x, y) = n. We say that q primitively represents n if there exist relatively prime integers x and y such that q(x, y) = n.

Positive definite forms are definite forms with a > 0. They can only represent positive numbers. Negative definite forms are definite forms with a < 0. They can represent only negative numbers. Indefinite forms can represent both positive and negative numbers.

The discriminant of a nondegenerate binary quadratic form is b^2 - 4ac. Inequivalent forms may have the same discriminant. Quadratic forms with different discriminants cannot be equivalent.

Geometric view

The graphic shows the level set of the binary quadratic form x^2+x*y+y^2 and the lattice points of the level set 13. The integral values (x, y) = (3, 1), (1, 3), (-1, 4), (-3, 4), (-4, 3), (-4, 1), (-3, -1), (-1, -3), (1, -4), (3, -4), (4, -3) and (4, -1) are points of the ellipse. Therefore 13 is represented by the form.

14 is not represented by the binary quadratic form x^2+x*y+y^2, no lattice points of the level set lie on the ellipse.

Some examples at a glance

The table below collocates a few sequences in the OEIS which list numbers represented by binary quadratic forms. If an entry in the table below shows multiple sequences this means that the sequences differ only by some initial terms or the equivalence of their definitions is not proved.

(a, b, c) b^2-4ac prime primitively positive
(1, 0, -3) 12 A068228, A141122 A243655 A084916
(1, 1, -2) 9 A002476, A007645 A244713 A056991, A242660
(1, 0, -2) 8 A001132, A038873 A057126 A035251
(1, 1, -1) 5 A038872, A141158 A089270 A031363
(1, 0, -1) 4 A065091 A047486 A042965
(1, 1, 0) 1 A000040, A006005 A000027, A001477 A000027, A001477
(1, 1, 1) -3 A002476, A007645 A034017 A003136, A035238,

A045375, A123365,

A144919, A144921
(1, 0 ,1) -4 A002144, A002313 A008784 A001481
(1, 1, 2) -7 A033207, A045373 A244779 A028951, A035248
(1, 0 , 2) -8 A033200, A033203 A057127 A002479
(1, 1, 3) -11 A056874 A244780 A028954, A035247
(1, 0, 3) -12 A002476, A007645 A244819 A003136

The oldest sequences in the table (defined here by the lowest A-number) are (apart from the natural numbers and the prime numbers) A001132 (primes ≡ ± 1 mod 8) and A001481 (numbers that are the sum of 2 squares), which nicely sets the arithmetic theme.

Note that only numbers n ≡ 0 (mod 4) or n ≡ 1 (mod 4) can be a discriminant (..., -8, -7, -4, -3, 0, 1, 4, 5, 8, ...).

Also note that reading a row in the table from the left to the right we have the inclusion "represented primes" ⊆ "primitively represented" ⊆ "represented positives". For example in the case of discriminant 4 the inclusion is A065091A047486A042965 where '⊆' is to be read as 'is subsequence of'.

Prime numbers which are represented by a binary quadratic form are primitively represented by this form. N. J. A. Sloane gave the following short proof on the seq-fan list:

"For if ax^2+bxy+cy^2 = p and gcd(x, y) = d > 1, then d divides p, so d = p. Then let x = pX, y = pY, so ap^2X^2+bp^2XY+cp^2Y^2 = p, so p^2 divides p, a contradiction."

A Sage based Python class: 'binaryQF(a, b, c)'

Algorithms

We consider 9 cases in dependence of the determinant D = b^2 - 4ac and required restrictions on the generated integers: prime, primitively represented or all positive values. The table below shows the algorithms used.

  • sfb: Extension of Sloane's 'fb' function.
  • qfb: Pari's qfbsolve function.
  • qfs: A search function based on a hint by R. Israel.
  • qfr: Pari's qfrep function.
  • jcp: Port of Will Jagy's C++ programs 'ConwayPositivePrimitive' and
    'ConwayPositiveAll'.
Algorithms used in the class binaryQF(a, b, c)
D = b^2 - 4ac, D != 0 prime primitively positive 
D = k^2, k != 0 (square) sfb  sfb  sfb 
D < 0 (definite, imaginary) qfb  qfs  qfr 
D > 0 (indefinite, real) jcp  jcp  jcp 


The main function

The aim of this implementation is to bundle all the different algorithms and resources in a Sage class and provide it uniformly to the user through a single function.

   represented_positives(
       N,        # list represented numbers in the range (1..N)
       subset,   # {'all', 'primitively', 'prime'}, default 'all'
       verbose   # print info, default true
   )

The function is implemented as a member of the class 'binaryQF'. All other functions in the class are supporting functions for this main function.

A typical use case is:

    Q = binaryQF([5, 4, 2])
    Q.represented_positives(100, 'prime')

This will output:

    Original form  [5, 4, 2] with discriminant -24
    Reduced form   [2, 0, 3]
    There are 8 primes represented up to 100
    [2, 3, 5, 11, 29, 53, 59, 83]

One can feed this output into Sage's oeis function

    oeis([2, 3, 5, 11, 29, 53, 59, 83], max_results = 4)

which returns

    0: A084865: Primes of the form 2x^2 + 3y^2.

Below we will additionally introduce a function 'lookup_OEIS' which can be used in connection with a local installation of the database.

Implementation

class binaryQF():
    """
    A binary quadratic form over Z.
    Input: a list of 3 entries: [a, b, c]
    """

    def __init__(self, abc):
        self._a, self._b, self._c = [ZZ(x) for x in abc]
        
    
    def discriminant(self):
        return self._b**2 - 4 * self._a * self._c
   
   
    def sqr_disc(self, M, primitively = False):

        d = self.discriminant()
        if d == 0:
            raise ValueError, "discriminant must not be zero"

        a, b, c = self._a, self._b, self._c
        if a == 0 and c == 0: # and b != 0
            return [b*n for n in (1..M//abs(b))]

        D = Integer(d).sqrtrem()[0]

        # a must be != 0
        if a == 0: # then c != 0; swap
            a = c
            c = 0

        k = 2 * D; m = 4 * a * D
        u = b + D; v = b - D
        S = set()

        # Solvability in Z.
        for n in (1..M):
            h = 4 * a * n  # a != 0 and n != 0
            for t in h.divisors():
                g = h // t
                if k.divides(g - t) and m.divides(g * u - t * v):

                    if primitively:
                        y = (g - t) // k
                        x = var('x')
                        eq = a * x * x + b * x * y + c * y * y
                        R = (eq - n).roots(multiplicities = False, ring = ZZ)
                        x = R[0]

                        if gcd(x, y) == 1:
                            S.add(n)
                            break
                    else:
                        S.add(n)
                        break

        return sorted(list(S))

    
    def imag_prime(self, M):
        
        solve = pari('qfbsolve')
        Q = pari('Qfb')(self._a, self._b, self._c)
        p = 1
        r = []
        
        while True:
            p = next_prime(p)
            if p > M: break
            if solve(Q, p):
                r.append(p)
        return r
        
    def imag_primitively(self, M):
        
        a, b, c = self._a, self._b, self._c
        d = c - b * b / (4 * a) 
        A = []
        
        for y in (0..isqrt(M / d)):
            r = y * b / (2 * a)
            s = sqrt((M - d * y * y) / a)
            for x in (ceil(-s -r)..floor(s - r)):
                if gcd(x, y) == 1:
                    A.append(a * x^2 + b * x * y + c * y^2) 
                    
        return sorted(Set(A).list())
    
    
    def imag_all(self, M):
        
        L = [2*ZZ(self._a), ZZ(self._b), ZZ(self._b), 2*ZZ(self._c)]
        G = Matrix(ZZ, 2, 2, L)
        A = pari('qfrep')(G, M, 1)
        return [k+1 for k in (0..M-1) if A[k] > 0]

    def _primitive_reps(self, a, h, b, M, S):
        
        if a <= M :
            S.add(a)
            if b <= M :
                S.add(b)
                if a <= (M - b) and h <= (M - a - b) :
                    if a <= (M - a - h) :
                        self._primitive_reps(a, h + 2 * a, a + b + h, M, S)
                    if b <= (M - b - h) :
                        self._primitive_reps(a + b + h, h + 2 * b, b, M, S)


    def positive_primitives(self, M, primitively):

        a, b, c = self._a, self._b, self._c
        
        S = set()
        while True:
            new_val = a + b + c
            if new_val > 0 :
                self._primitive_reps(a, b + 2 * a, new_val, M, S)
                b += 2 * c
                a = new_val
            elif new_val < 0 :
                b += 2 * a
                c = new_val
            if a == self._a and b == self._b and c == self._c:    
                break

        if not primitively :
            X = set()
            for p in S:
                q = t = 1
                while q <= M :
                    X.add(q)
                    q = t * t * p
                    t += 1
            S = X

        return S

    
    def reduce_real(self):
        
        d = self.discriminant()
        if is_square(d):
            raise ValueError, "form must not have square discriminant"

        droot = Integer(d).sqrtrem()[0]
        a, b, c = self._a, self._b, self._c

        while a <= 0 or c >= 0 or b <= abs(a + c):

            cAbs = c
            if cAbs < 0: cAbs *= -1

            # cAbs = 0 will not happen for a non square form
            delta = (b + droot) // (2 * cAbs)
            if c < 0: delta *= -1
            aa = c
            bb = 2 * c * delta - b
            cc = c * delta * delta - b * delta + a
            a, b, c = aa, bb, cc

        return [a, b, c]

    def reduce_imag(self):
        
        a, b, c = self._a, self._b, self._c
        if a < 0: a, b, c = -a, -b, -c
        d = self.discriminant()

        while True:
            A = ( a == c and b < 0) or (c < a)
            B = (-a == b and a < c) or (a < abs(b))

            if not (A or B) : break

            if A: a, b, c = c, -b, a

            if B:
                b -= 2 * a * (b // (2 * a))
                if abs(b) > a: b -= 2 * a
                c = (b * b - d) // (4 * a)

        return [a, b, c]
        
    def is_reduced(self):
        
        a, b, c = self._a, self._b, self._c
        return (-a < b <= a < c) or (ZZ(0) <= b <= a == c)
    

    def reduced_form(self):    
        """
        Returns the unique reduced form equivalent to BQF(a,b,c)
        """
                    
        if self.is_reduced() :
            return self

        if self.discriminant() >= 0:
            r = self.reduce_real()
        else:
            r = self.reduce_imag()
            
        return binaryQF(r)    


    def represented_positives(self, M, subset = "all", verbose = True):
        """
        subset = "all" or "primitively" or "prime"
        """
        
        prime = False or subset == "prime"
        primitively = False or subset == "primitively"
        
        d = self.discriminant()
        if d == 0:
            raise ValueError, "discriminant must not be 0"
        
        a, b, c = self._a, self._b, self._c            
        if verbose:
            print "Original form ", [a, b, c], "with discriminant", d

        if is_square(d):
            if verbose:
                print "Square discriminant!"
                
            if prime:  # for efficiency
                primitively = False    
            pp = self.sqr_disc(M, primitively)
            if prime:
                pp = filter(is_prime, pp)

        else:
            
            R = self.reduced_form()
            if verbose:
               print "Reduced form  ", [R._a, R._b, R._c]

            if d < 0:

                if prime:
                    pp = R.imag_prime(M)
                else:
                    if primitively:
                        pp = R.imag_primitively(M)
                    else:
                        pp = R.imag_all(M)

            # real case, indefinite form
            else: # d > 0 and not square

                if prime:  # for efficiency
                    primitively = True
                pp = R.positive_primitives(M, primitively)
                if prime:
                    pp = filter(is_prime, pp)
                pp = sorted(pp)    

        if verbose:
            msg0 = "primes" if prime else "positive integers"
            msg1 = "primitively" if primitively else ""
            msg2 = "represented up to"
            print "There are", len(pp), msg0, msg1, msg2, M

        return pp


Computations

# A243655
Q = binaryQF([1, 0, -3])
Q.represented_positives(100, 'primitively')
# Original form [1, 0, -3] with discriminant 12.
# Reduced form  [1, 2, -2]
# There are 13 positive integers primitively represented up to 100.
# [1, 6, 13, 22, 33, 37, 46, 61, 69, 73, 78, 94, 97]
# With N = 100000: time: CPU 0.14 s, Wall: 0.16 s

# A244291
Q = binaryQF([1, 6, -3]) 
Q.represented_positives(100, 'primitively')
# Original form (1, 6, -3) with discriminant 48
# Reduced form  (1, 6, -3)
# There are 12 positive integers primitively represented up to 100
# [1, 4, 13, 24, 33, 37, 52, 61, 69, 73, 88, 97]
# With N = 100000: time: CPU 0.16 s, Wall: 0.19 s

# A084916
Q = binaryQF([1, 0, -3])
Q.represented_positives(50)
# Original form [1, 0, -3] with discriminant 12.
# Reduced form  [1, 2, -2]
# There are 14 positive integers represented up to 50.
# [1, 4, 6, 9, 13, 16, 22, 24, 25, 33, 36, 37, 46, 49]
# With N = 100000: time: CPU 0.19 s, Wall: 0.21 s

# A141175
Q = binaryQF([-1, 4, 4])
Q.represented_positives(100, 'prime')
#Q = binaryQF([7, 12, 4])
#Q.represented_positives(100, 'prime')
# Original form [-1, 4, 4] with discriminant 32.
# Reduced form  [4, 4, -1]
# There are 6 primes represented up to 100.
# [7, 23, 31, 47, 71, 79]
# With N = 100000: time: CPU 0.24 s, Wall: 0.27 s

# A035269
Q = binaryQF([2, 3, -4])
Q.represented_positives(33)
# Original form [2, 3, -4] with discriminant 41.
# Reduced form  [2, 3, -4]
# There are 14 positive integers represented up to 33.
# [1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 23, 25, 31, 32]
# With N = 100000: time: CPU 0.55 s, Wall: 0.60 s

# A056991, A242660
Q = binaryQF([1, 1, -2])
Q.represented_positives(30)
# Original form [1, 1, -2] with discriminant 9.
# Square discriminant!
# There are 13 positive integers represented up to 30
# [1, 4, 7, 9, 10, 13, 16, 18, 19, 22, 25, 27, 28]
# With N = 100000: time: CPU 18.10 s, Wall: 18.95 s

# A002476
Q = binaryQF([1, 1, -2])
Q.represented_positives(100, 'prime')
# Original form [1, 1, -2] with discriminant 9.
# Square discriminant!
# There are 11 primes represented up to 100.
# [7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97]
# With N = 100000: time: CPU 18.92 s, Wall: 19.80 s

# A107132
Q = binaryQF([2, 0, 13])
Q.represented_positives(500, 'prime')
# Original form [2, 0, 13] with discriminant -104.
# Reduced       [2, 0, 13]
# There are 10 primes represented up to 500.
# [2, 13, 31, 149, 167, 317, 359, 397, 463, 487]
# With N = 100000: time: CPU 0.18 s, Wall: 0.20 s

# A045373 
Q = binaryQF([1, 1, 2])
Q.represented_positives(109, 'prime')
# Original form [1, 1, 2] with discriminant -7.
# Reduced       [1, 1, 2]
# There are 13 primes represented up to 109.
# [2, 7, 11, 23, 29, 37, 43, 53, 67, 71, 79, 107, 109]
# With N = 100000: time: CPU 0.27 s, Wall: 0.30 s

# A033203 
Q = binaryQF([1, 0, 2])
Q.represented_positives(100, 'prime')
# Original form [1, 0, 2] with discriminant -8 
# Reduced       [1, 0, 2]
# There are 13 primes represented up to 100.
# [2, 3, 11, 17, 19, 41, 43, 59, 67, 73, 83, 89, 97]
# With N = 100000: time: CPU 0.26 s, Wall: 0.29 s

Q = binaryQF([2, -1, 17])
Q.represented_positives(100000, 'prime')
# Original form [2, -1, 17] with discriminant -135 
# Reduced       [2, -1, 17]
# There are 1609 primes represented up to 100000.
# [2, 17, 23, 53, 83, 137, ..., 99623, 99707, 99713, 99833]
# With N = 100000: time: CPU 0.20 s, Wall: 0.22 s

# A028951, A035248  
Q = binaryQF([1, 1, 2])
Q.represented_positives(30)
# Original form [1, 1, 2] with discriminant -7
# There are 15 positive integers represented up to 30
# [1, 2, 4, 7, 8, 9, 11, 14, 16, 18, 22, 23, 25, 28, 29]
# With N = 100000: time: CPU 1.68 s, Wall: 2.31 s

# A003136
Q = binaryQF([1, 1, 1])
Q.represented_positives(30)
# Original form [1, 1, 1] with discriminant -3
# There are 13 positive integers represented up to 30
# [1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25, 27, 28]
# With N = 100000: time: CPU 1.19 s, Wall: 1.39 s

# A001481
Q = binaryQF([1, 0, 1])
Q.represented_positives(30)
# Original form [1, 0, 1] with discriminant -4
# Reduced       [1, 0, 1]
# There are 15 positive integers represented up to 30
# [1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29]
# With N = 100000: time: CPU 1.08 s, Wall: 1.21 s

# A244019
Q = binaryQF([9, 6, 1849])
Q.represented_positives(18000, 'prime') 
# Original form [9, 6, 1849] with discriminant -66528
# Reduced       [9, 6, 1849]
# There are 44 primes represented up to 18000
# [1873, 2017, 2137, 2377, 2473, 2689, 3217, 3529, 3697, 4057, 4657, 5569,
# 6073, 6337, 7177, 7393, 7417, 7561, 7681, 7753, 8017, 8089, 8233, 8353,
# 8737, 8761, 9241, 9601, 9769, 11113, 11257, 11617, 12049, 12433, 12457,
# 12721, 13297, 13633, 13729, 14281, 15073, 15313, 16417, 17977]
# With N = 100000: time: CPU 0.14 s, Wall: 0.16 s

# A139668
Q = binaryQF([1, 0, 1848])
Q.represented_positives(18000, 'prime')
# Original form [1, 0, 1848] with discriminant -7392
# Reduced       [1, 0, 1848]
# There are 49 primes represented up to 18000
# [1873, 2017, 2137, 2377, 2473, 2689, 3217, 3529, 3697, 4057, 4657, 5569,
# 6073, 6337, 7177, 7393, 7417, 7561, 7681, 7753, 8017, 8089, 8233, 8353,
# 8737, 8761, 9241, 9601, 9769, 11113, 11257, 11617, 12049, 12433, 12457,
# 12721, 13297, 13633, 13729, 14281, 15073, 15313, 16417, 16633, 16657,
# 16921, 16993, 17257, 17977]
# With N = 100000: time: CPU 0.13 s, Wall: 0.15 s

Q = binaryQF([0, 233, 3])
Q.represented_positives(2000, 'prime')
#Q = binaryQF([3, 229, -154])
#Q.represented_positives(2000, 'prime')
# Original form [0, 233, 3] with discriminant 54289
# Square discriminant!
# There are 4 primes represented up to 2000
# [3, 311, 1709, 1867]
# With N = 100000: time: CPU 36.50 s, Wall: 37.73 s

# A141175, A007522
Q = binaryQF([-1, 0, 8])
Q.represented_positives(100, 'prime')
# Original form (-1, 0, 8) with discriminant 32
# Reduced form  (4, 4, -1)
# There are 6 primes represented up to 100
# [7, 23, 31, 47, 71, 79]
# With N = 100000: time: CPU 0.36 s, Wall: 0.40 s

# A035269
Q = binaryQF([-5, 1, 2])
Q.represented_positives(33)
# Original form (-5, 1, 2) with discriminant 41
# Reduced form  (2, 3, -4)
# There are 14 positive integers represented up to 33
# [1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 23, 25, 31, 32]
# With N = 100000: time: CPU 0.52 s, Wall: 0.57 s

# A002313
Q = binaryQF([41, 100, 61])
Q.represented_positives(50, 'prime')
# Original form (41, 100, 61) with discriminant -4
# Reduced       (1,    0,  1)
# There are 7 primes represented up to 50
# [2, 5, 13, 17, 29, 37, 41]
# With N = 100000: CPU 0.25 s, Wall: 0.29 s

# A002479
Q = binaryQF([-1, -2, -3])
Q.represented_positives(30)
# Original form (-1, -2, -3) with discriminant -8
# Reduced       (1,   0,  2)
# There are 17 positive integers represented up to 30
# [1, 2, 3, 4, 6, 8, 9, 11, 12, 16, 17, 18, 19, 22, 24, 25, 27]
# With N = 100000: CPU 0.25 s, Wall: 0.29 s

# A035251
Q = binaryQF([1, 0, -2])
Q.represented_positives(30)
# Original form (1, 0, -2) with discriminant 8
# Reduced form  (1, 2, -1)
# There are 13 positive integers represented up to 30
# [1, 2, 4, 7, 8, 9, 14, 16, 17, 18, 23, 25, 28]
# With N = 100000: CPU 0.33 s, Wall: 0.38 s

# A002480
Q = binaryQF([5, 4, 2])
Q.represented_positives(40)
# Original form (5, 4, 2) with discriminant -24
# Reduced       (2, 0, 3)
# There are 15 positive integers represented up to 40
# [2, 3, 5, 8, 11, 12, 14, 18, 20, 21, 27, 29, 30, 32, 35]
# With N = 100000: CPU 1.14 s, Wall: 1.27 s

Utility functions

  • OEIS_ID(list, n)
    Tries to find n sequences which match the list.
     
  • lookup_OEIS(q, subset)
    Tries to find sequences which are represented by the binary quadratic form with coefficient list q = [a, b, c] and which have elements in the 'subset', which is one of  'all', 'primitively' or 'prime'.
SloaneEncyclopedia.install()
# Comment this line out after the first call. This function updates
# the database and it is sufficient to call it only once in a while.

def OEIS_ID(T, num) :
    
    if len(T) < 3:
        return []
    S = T[1:min(len(T),20)] 
    R = SloaneEncyclopedia.find(S, num)
    if R == [] :
        U = filter(lambda z: z != 0 , S)
        del U[0]
        R = SloaneEncyclopedia.find(U, num)
    A = [r[0] for r in R] 
    s = []
    for a in A :
        sa = str(a)
        L = "A000000"[0:7-len(sa)]
        s.append(L + sa)
    return s    

def lookup_OEIS(q, filter = 'all'):

    d = q[1]^2 - 4*q[0]*q[2]    
    sl = 100 if filter == 'prime' else 50
    
    # make sure that seq is long enough
    for l in (0..2):
        Q = binaryQF(q)
        rep = Q.represented_positives(sl, filter, verbose = False)
        if len(rep) >= 12:
            break
        else:
            sl *= 10 
    
    if rep <> []:
       short = rep[:min(len(rep),11)]
       print d, q, short, OEIS_ID(rep, 2) 
    else:
        print d, q

Examples:

lookup_OEIS((1,1,1), 'all') 
lookup_OEIS((1,1,1), 'prime')
lookup_OEIS((1,1,1), 'primitively')
-3 (1, 1, 1) [1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25] [A003136, A035238]
-3 (1, 1, 1) [3, 7, 13, 19, 31, 37, 43, 61, 67, 73]  [A002476, A007645]
-3 (1, 1, 1) [1, 2, 4, 7, 8, 11, 14, 16, 22, 23, 28] [A034017]
lookup_OEIS((1,1,2), 'all') 
lookup_OEIS((1,1,2), 'prime')
lookup_OEIS((1,1,2), 'primitively')
-7 (1, 1, 2) [1, 2, 4, 7, 8, 9, 11, 14, 16, 18, 22]  [A028951, A035248]
-7 (1, 1, 2) [2, 7, 11, 23, 29, 37, 43, 53, 67, 71]  [A033207, A045373]
-7 (1, 1, 2) [1, 2, 4, 7, 8, 11, 14, 16, 22, 23, 28] [A244779]


List of positive definite quadratic forms

def posDefQF():
    c = 1
    while True:
        yield (1, 1, c)
        yield (1, 0, c)
        c += 1

def listPosDefQF(len, filter = 'all'):
    F = posDefQF()     
    for i in range(len):
        q = F.next()
        lookup_OEIS(q, filter)

Calls to listPosDefQF(100) and listPosDefQF(100, 'prime') produce, when combined, the list:

-3  (1, 1, 1) [1, 3, 4, 7, 9, 12, 13, 16, 19, 21]       ['A003136', 'A034022']
-3  (1, 1, 1) [3, 7, 13, 19, 31, 37, 43, 61, 67, 73]    ['A002476', 'A007645']
-4  (1, 0, 1) [1, 2, 4, 5, 8, 9, 10, 13, 16, 17]        ['A001481']
-4  (1, 0, 1) [2, 5, 13, 17, 29, 37, 41, 53, 61, 73]    ['A002144', 'A002313']
-7  (1, 1, 2) [1, 2, 4, 7, 8, 9, 11, 14, 16, 18]        ['A028951', 'A035248']
-7  (1, 1, 2) [2, 7, 11, 23, 29, 37, 43, 53, 67, 71]    ['A033207', 'A045373']
-8  (1, 0, 2) [1, 2, 3, 4, 6, 8, 9, 11, 12, 16]         ['A002479']
-8  (1, 0, 2) [2, 3, 11, 17, 19, 41, 43, 59, 67, 73]    ['A033200', 'A033203']
-11 (1, 1, 3) [1, 3, 4, 5, 9, 11, 12, 15, 16, 20]       ['A028954', 'A035247']
-11 (1, 1, 3) [3, 5, 11, 23, 31, 37, 47, 53, 59, 67]    ['A056874']
-12 (1, 0, 3) [1, 3, 4, 7, 9, 12, 13, 16, 19, 21]       ['A003136', 'A034022']
-12 (1, 0, 3) [3, 7, 13, 19, 31, 37, 43, 61, 67, 73]    ['A002476', 'A007645']
-15 (1, 1, 4) [1, 4, 6, 9, 10, 15, 16, 19, 24, 25]      ['A028957']
-15 (1, 1, 4) [19, 31, 61, 79, 109, 139, 151, 181, 199] ['A033212', 'A141184']
-16 (1, 0, 4) [1, 4, 5, 8, 9, 13, 16, 17, 20, 25]       ['A020668']
-16 (1, 0, 4) [5, 13, 17, 29, 37, 41, 53, 61, 73, 89]   ['A002144', 'A002313']
-19 (1, 1, 5) [1, 4, 5, 7, 9, 11, 16, 17, 19, 20]       ['A035243']
-19 (1, 1, 5) [5, 7, 11, 17, 19, 23, 43, 47, 61, 73]    ['A106863']
-20 (1, 0, 5) [1, 4, 5, 6, 9, 14, 16, 20, 21, 24]       ['A020669']
-20 (1, 0, 5) [5, 29, 41, 61, 89, 101, 109, 149, 181]   ['A033205', 'A216815']
-23 (1, 1, 6) [1, 4, 6, 8, 9, 12, 16, 18, 23, 24]       ['A028958']
-23 (1, 1, 6) [23, 59, 101, 167, 173, 211, 223, 271]    ['A033217']
-24 (1, 0, 6) [1, 4, 6, 7, 9, 10, 15, 16, 22, 24]       ['A002481']
-24 (1, 0, 6) [7, 31, 73, 79, 97, 103, 127, 151, 193]   ['A033199']
-27 (1, 1, 7) [1, 4, 7, 9, 13, 16, 19, 25, 27, 28]      ['A243175']
-27 (1, 1, 7) [7, 13, 19, 31, 37, 43, 61, 67, 73, 79]   ['A002476', 'A007645']
-28 (1, 0, 7) [1, 4, 7, 8, 9, 11, 16, 23, 25, 28]       ['A020670']
-28 (1, 0, 7) [7, 11, 23, 29, 37, 43, 53, 67, 71, 79]   ['A033207', 'A045373']
-31 (1, 1, 8) [1, 4, 8, 9, 10, 14, 16, 20, 25, 28]      ['A243176']
-31 (1, 1, 8) [31, 47, 67, 131, 149, 173, 227, 283]     ['A033221']
-32 (1, 0, 8) [1, 4, 8, 9, 12, 16, 17, 24, 25, 32]      ['A020671']
-32 (1, 0, 8) [17, 41, 73, 89, 97, 113, 137, 193, 233]  ['A007519', 'A045390']
-35 (1, 1, 9) [1, 4, 9, 11, 15, 16, 21, 25, 29, 35]     ['A243178']
-35 (1, 1, 9) [11, 29, 71, 79, 109, 149, 151, 179, 191] ['A106881']
-36 (1, 0, 9) [1, 4, 9, 10, 13, 16, 18, 25, 34, 36]     ['A020672']
-36 (1, 0, 9) [13, 37, 61, 73, 97, 109, 157, 181, 193]  ['A068228', 'A141122']
-39 (1, 1, 10) [1, 4, 9, 10, 12, 16, 22, 25, 30, 36]    ['A243194']
-39 (1, 1, 10) [43, 103, 139, 157, 181, 277, 367, 439]  ['A033227']
-40 (1, 0, 10) [1, 4, 9, 10, 11, 14, 16, 19, 25, 26]    ['A020673']
-40 (1, 0, 10) [11, 19, 41, 59, 89, 131, 139, 179, 211] ['A033201']
-43 (1, 1, 11) [1, 4, 9, 11, 13, 16, 17, 23, 25, 31]    ['A035233']
-43 (1, 1, 11) [11, 13, 17, 23, 31, 41, 43, 47, 53, 59] ['A106891']
-44 (1, 0, 11) [1, 4, 9, 11, 12, 15, 16, 20, 25, 27]    ['A243651']
-44 (1, 0, 11) [11, 47, 53, 103, 163, 199, 257, 269]    ['A033209', 'A106279']
-47 (1, 1, 12) [1, 4, 9, 12, 14, 16, 18, 24, 25, 32]    ['A243650']
-47 (1, 1, 12) [47, 83, 191, 197, 269, 439, 487, 523]   ['A033232']
-48 (1, 0, 12) [1, 4, 9, 12, 13, 16, 21, 25, 28, 36]    []
-48 (1, 0, 12) [13, 37, 61, 73, 97, 109, 157, 181, 193] ['A068228', 'A141122']
-51 (1, 1, 13) [1, 4, 9, 13, 15, 16, 19, 25, 33, 36]    []
-51 (1, 1, 13) [13, 19, 43, 67, 103, 127, 151, 157]     ['A106904']
-52 (1, 0, 13) [1, 4, 9, 13, 14, 16, 17, 22, 25, 29]    []
-52 (1, 0, 13) [13, 17, 29, 53, 61, 101, 113, 157, 173] ['A033210']
-55 (1, 1, 14) [1, 4, 9, 14, 16, 20, 25, 26, 34, 36]    []
-55 (1, 1, 14) [59, 71, 199, 229, 251, 269, 311, 379]   ['A033235']
-56 (1, 0, 14) [1, 4, 9, 14, 15, 16, 18, 23, 25, 30]    []
-56 (1, 0, 14) [23, 127, 137, 151, 233, 239, 281, 359]  ['A033211']
-59 (1, 1, 15) [1, 4, 9, 15, 16, 17, 21, 25, 27, 35]    []
-59 (1, 1, 15) [17, 59, 71, 139, 163, 197, 223, 317]    ['A106922']
-60 (1, 0, 15) [1, 4, 9, 15, 16, 19, 24, 25, 31, 36]    ['A243173']
-60 (1, 0, 15) [19, 31, 61, 79, 109, 139, 151, 181]     ['A033212', 'A141184']
-63 (1, 1, 16) [1, 4, 9, 16, 18, 22, 25, 28, 36, 46]    []
-63 (1, 1, 16) [67, 79, 127, 163, 277, 373, 421, 463]   ['A106930']
-64 (1, 0, 16) [1, 4, 9, 16, 17, 20, 25, 32, 36, 41]    []
-64 (1, 0, 16) [17, 41, 73, 89, 97, 113, 137, 193, 233] ['A007519', 'A045390']
-67 (1, 1, 17) [1, 4, 9, 16, 17, 19, 23, 25, 29, 36]    []
-67 (1, 1, 17) [17, 19, 23, 29, 37, 47, 59, 67, 71, 73] ['A106933']
-68 (1, 0, 17) [1, 4, 9, 16, 17, 18, 21, 25, 26, 33]    []
-68 (1, 0, 17) [17, 53, 149, 157, 281, 293, 349, 353]   ['A033213']
-71 (1, 1, 18) [1, 4, 9, 16, 18, 20, 24, 25, 30, 36]    []
-71 (1, 1, 18) [71, 107, 293, 509, 643, 647, 739, 971]  ['A033246']
-72 (1, 0, 18) [1, 4, 9, 16, 18, 19, 22, 25, 27, 34]    []
-72 (1, 0, 18) [19, 43, 67, 73, 97, 139, 163, 193, 211] ['A106950', 'A141170']
-75 (1, 1, 19) [1, 4, 9, 16, 19, 21, 25, 31, 36, 39]    []
-75 (1, 1, 19) [19, 31, 61, 79, 109, 139, 151, 181]     ['A033212', 'A141184']
-76 (1, 0, 19) [1, 4, 9, 16, 19, 20, 23, 25, 28, 35]    []
-76 (1, 0, 19) [19, 23, 83, 101, 157, 163, 197, 271]    ['A033214']
-79 (1, 1, 20) [1, 4, 9, 16, 20, 22, 25, 26, 32, 36]    []
-79 (1, 1, 20) [79, 83, 179, 223, 317, 397, 479, 541]   ['A033251']
-80 (1, 0, 20) [1, 4, 9, 16, 20, 21, 24, 25, 29, 36]    []
-80 (1, 0, 20) [29, 89, 101, 181, 229, 349, 401, 461]   ['A047650']
-83 (1, 1, 21) [1, 4, 9, 16, 21, 23, 25, 27, 33, 36]    []
-83 (1, 1, 21) [23, 41, 83, 131, 193, 199, 227, 229]    ['A106970']
-84 (1, 0, 21) [1, 4, 9, 16, 21, 22, 25, 30, 36, 37]    []
-84 (1, 0, 21) [37, 109, 193, 277, 337, 373, 421, 457]  ['A033215']
-87 (1, 1, 22) [1, 4, 9, 16, 22, 24, 25, 28, 34, 36]    []
-87 (1, 1, 22) [103, 151, 283, 349, 373, 397, 487, 571] ['A033256']
-88 (1, 0, 22) [1, 4, 9, 16, 22, 23, 25, 26, 31, 36]    []
-88 (1, 0, 22) [23, 31, 47, 71, 89, 97, 103, 113, 137]  ['A033216']
-91 (1, 1, 23) [1, 4, 9, 16, 23, 25, 29, 35, 36, 43]    []
-91 (1, 1, 23) [23, 29, 43, 53, 79, 107, 113, 127, 179] ['A106988', 'A106989']
-92 (1, 0, 23) [1, 4, 9, 16, 23, 24, 25, 27, 32, 36]    []
-92 (1, 0, 23) [23, 59, 101, 167, 173, 211, 223, 271]   ['A033217']
-95 (1, 1, 24) [1, 4, 9, 16, 24, 25, 26, 30, 36, 44]    []
-95 (1, 1, 24) [131, 239, 389, 419, 461, 821, 859, 919] ['A033206']
-96 (1, 0, 24) [1, 4, 9, 16, 24, 25, 28, 33, 36, 40]    []
-96 (1, 0, 24) [73, 97, 193, 241, 313, 337, 409, 433]   ['A107008', 'A141375']
-99 (1, 1, 25) [1, 4, 9, 16, 25, 27, 31, 36, 37, 45]    []
-99 (1, 1, 25) [31, 37, 67, 97, 103, 157, 163, 181]     ['A107013', 'A141177']
-100 (1, 0, 25) [1, 4, 9, 16, 25, 26, 29, 34, 36]       []
-100 (1, 0, 25) [29, 41, 61, 89, 101, 109, 149, 181]    ['A033205', 'A216815']
-103 (1, 1, 26) [1, 4, 9, 16, 25, 26, 28, 32, 36, 38]   []
-103 (1, 1, 26) [103, 107, 139, 167, 359, 421, 461]     []
-104 (1, 0, 26) [1, 4, 9, 16, 25, 26, 27, 30, 35, 36]   []
-104 (1, 0, 26) [107, 113, 251, 283, 467, 523, 641]     ['A033218']
-107 (1, 1, 27) [1, 4, 9, 16, 25, 27, 29, 33, 36, 39]   []
-107 (1, 1, 27) [29, 47, 83, 107, 137, 241, 251, 271]   []
-108 (1, 0, 27) [1, 4, 9, 16, 25, 27, 28, 31, 36, 43]   []
-108 (1, 0, 27) [31, 43, 109, 127, 157, 223, 229, 277]  ['A014752', 'A016108']
-111 (1, 1, 28) [1, 4, 9, 16, 25, 28, 30, 34, 36, 40]   []
-111 (1, 1, 28) [127, 211, 307, 367, 613, 733, 787]     []
-112 (1, 0, 28) [1, 4, 9, 16, 25, 28, 29, 32, 36, 37]   []
-112 (1, 0, 28) [29, 37, 53, 109, 113, 137, 149, 193]   ['A107134', 'A141172']
-115 (1, 1, 29) [1, 4, 9, 16, 25, 29, 31, 35, 36]       []
-115 (1, 1, 29) [29, 31, 41, 59, 71, 101, 131, 139]     []
-116 (1, 0, 29) [1, 4, 9, 16, 25, 29, 30, 33, 36]       []
-116 (1, 0, 29) [29, 173, 197, 277, 353, 457, 557, 661] ['A033219']
-119 (1, 1, 30) [1, 4, 9, 16, 25, 30, 32, 36, 42]       []
-119 (1, 1, 30) [263, 443, 557, 701, 1019, 1087, 1171]  []
-120 (1, 0, 30) [1, 4, 9, 16, 25, 30, 31, 34, 36]       []
-120 (1, 0, 30) [31, 79, 151, 199, 241, 271, 409, 439]  ['A033220']
-123 (1, 1, 31) [1, 4, 9, 16, 25, 31, 33, 36, 37]       []
-123 (1, 1, 31) [31, 37, 43, 61, 73, 103, 127, 139]     []
-124 (1, 0, 31) [1, 4, 9, 16, 25, 31, 32, 35, 36]       []
-124 (1, 0, 31) [31, 47, 67, 131, 149, 173, 227, 283]   ['A033221']
-127 (1, 1, 32) [1, 4, 9, 16, 25, 32, 34, 36, 38, 44]   []
-127 (1, 1, 32) [127, 131, 163, 191, 227, 271, 383]     []
-128 (1, 0, 32) [1, 4, 9, 16, 25, 32, 33, 36, 41]       []
-128 (1, 0, 32) [41, 113, 137, 257, 313, 337, 353, 409] ['A105389']
-131 (1, 1, 33) [1, 4, 9, 16, 25, 33, 35, 36, 39]       []
-131 (1, 1, 33) [53, 89, 131, 167, 307, 337, 367, 601]  []
-132 (1, 0, 33) [1, 4, 9, 16, 25, 33, 34, 36, 37]       []
-132 (1, 0, 33) [37, 97, 157, 181, 229, 313, 397, 421]  ['A033222']
-135 (1, 1, 34) [1, 4, 9, 16, 25, 34, 36, 40, 46]       []
-135 (1, 1, 34) [139, 151, 199, 331, 541, 619, 661]     ['A047652']
-136 (1, 0, 34) [1, 4, 9, 16, 25, 34, 35, 36, 38]       []
-136 (1, 0, 34) [43, 59, 83, 137, 257, 307, 331, 563]   ['A033223']
-139 (1, 1, 35) [1, 4, 9, 16, 25, 35, 36, 37, 41]       []
-139 (1, 1, 35) [37, 41, 47, 107, 139, 167, 191, 239]   []
-140 (1, 0, 35) [1, 4, 9, 16, 25, 35, 36, 39, 44]       []
-140 (1, 0, 35) [71, 149, 179, 331, 359, 379, 569, 571] ['A033224']
-143 (1, 1, 36) [1, 4, 9, 16, 25, 36, 38, 42, 48]       []
-143 (1, 1, 36) [179, 467, 653, 719, 797, 1013, 1291]   []
-144 (1, 0, 36) [1, 4, 9, 16, 25, 36, 37, 40, 45]       []
-144 (1, 0, 36) [37, 61, 157, 193, 313, 349, 373, 397]  ['A107142']
-147 (1, 1, 37) [1, 4, 9, 16, 25, 36, 37, 39, 43]       []
-147 (1, 1, 37) [37, 43, 67, 79, 109, 127, 151, 163]    ['A139492', 'A141159']
-148 (1, 0, 37) [1, 4, 9, 16, 25, 36, 37, 38, 41]       []
-148 (1, 0, 37) [37, 41, 53, 73, 101, 137, 149, 157]    ['A033225']
-151 (1, 1, 38) [1, 4, 9, 16, 25, 36, 38, 40, 44]       []
-151 (1, 1, 38) [151, 167, 251, 347, 613, 653, 727]     []
-152 (1, 0, 38) [1, 4, 9, 16, 25, 36, 38, 39, 42]       []
-152 (1, 0, 38) [47, 233, 263, 367, 463, 479, 593, 617] ['A033226']
-155 (1, 1, 39) [1, 4, 9, 16, 25, 36, 39, 41, 45]       []
-155 (1, 1, 39) [41, 59, 149, 191, 311, 349, 379, 419]  []
-156 (1, 0, 39) [1, 4, 9, 16, 25, 36, 39, 40, 43]       []
-156 (1, 0, 39) [43, 103, 139, 157, 181, 277, 367, 439] ['A033227']
-159 (1, 1, 40) [1, 4, 9, 16, 25, 36, 40, 42, 46]       []
-159 (1, 1, 40) [163, 223, 643, 661, 757, 997, 1447]    []
-160 (1, 0, 40) [1, 4, 9, 16, 25, 36, 40, 41, 44]       []
-160 (1, 0, 40) [41, 89, 241, 281, 401, 409, 449, 521]  ['A107145']
-163 (1, 1, 41) [1, 4, 9, 16, 25, 36, 41, 43, 47]       []
-163 (1, 1, 41) [41, 43, 47, 53, 61, 71, 83, 97, 113]   []
-164 (1, 0, 41) [1, 4, 9, 16, 25, 36, 41, 42, 45]       []
-164 (1, 0, 41) [41, 173, 373, 389, 433, 617, 769, 853] ['A033228']
-167 (1, 1, 42) [1, 4, 9, 16, 25, 36, 42, 44, 48]       []
-167 (1, 1, 42) [167, 311, 491, 677, 743, 1109, 1567]   []
-168 (1, 0, 42) [1, 4, 9, 16, 25, 36, 42, 43, 46]       []
-168 (1, 0, 42) [43, 67, 163, 193, 211, 331, 337, 379]  ['A033229']
-171 (1, 1, 43) [1, 4, 9, 16, 25, 36, 43, 45, 49]       []
-171 (1, 1, 43) [43, 73, 199, 271, 283, 349, 367, 397]  []
-172 (1, 0, 43) [1, 4, 9, 16, 25, 36, 43, 44, 47, 49]   []
-172 (1, 0, 43) [43, 47, 59, 79, 107, 173, 181, 197]    ['A033230']
-175 (1, 1, 44) [1, 4, 9, 16, 25, 36, 44, 46, 49, 50]   []
-175 (1, 1, 44) [179, 191, 211, 239, 431, 499, 659]     []
-176 (1, 0, 44) [1, 4, 9, 16, 25, 36, 44, 45, 48]       []
-176 (1, 0, 44) [53, 257, 269, 397, 401, 421, 617, 757] ['A107150']
-179 (1, 1, 45) [1, 4, 9, 16, 25, 36, 45, 47, 49, 51]   []
-179 (1, 1, 45) [47, 101, 179, 227, 317, 409, 433, 503] []
-180 (1, 0, 45) [1, 4, 9, 16, 25, 36, 45, 46, 49, 54]   []
-180 (1, 0, 45) [61, 109, 181, 229, 241, 349, 409, 421] ['A107152', 'A141301']
-183 (1, 1, 46) [1, 4, 9, 16, 25, 36, 46, 48, 49, 52]   []
-183 (1, 1, 46) [199, 283, 379, 439, 733, 757, 853, 859][]
-184 (1, 0, 46) [1, 4, 9, 16, 25, 36, 46, 47, 49, 50]   []
-184 (1, 0, 46) [47, 71, 127, 167, 193, 233, 271, 353]  ['A033231']
-187 (1, 1, 47) [1, 4, 9, 16, 25, 36, 47, 49, 53, 59]   []
-187 (1, 1, 47) [47, 53, 59, 67, 89, 103, 137, 157, 179][]
-188 (1, 0, 47) [1, 4, 9, 16, 25, 36, 47, 48, 49, 51]   []
-188 (1, 0, 47) [47, 83, 191, 197, 269, 439, 487, 523]  ['A033232']
-191 (1, 1, 48) [1, 4, 9, 16, 25, 36, 48, 49, 50, 54]   []
-191 (1, 1, 48) [191, 227, 773, 1091, 1487, 1493, 1723] []
-192 (1, 0, 48) [1, 4, 9, 16, 25, 36, 48, 49, 52, 57]   []
-192 (1, 0, 48) [73, 97, 193, 241, 313, 337, 409, 433]  ['A107008', 'A141375']
-195 (1, 1, 49) [1, 4, 9, 16, 25, 36, 49, 51, 55, 61]   []
-195 (1, 1, 49) [61, 79, 139, 181, 199, 211, 439, 571]  []
-196 (1, 0, 49) [1, 4, 9, 16, 25, 36, 49, 50, 53, 58]   []
-196 (1, 0, 49) [53, 113, 149, 193, 197, 277, 317, 373] ['A107155']
-199 (1, 1, 50) [1, 4, 9, 16, 25, 36, 49, 50, 52, 56]   []
-199 (1, 1, 50) [199, 263, 523, 599, 683, 797, 821, 877][]
-200 (1, 0, 50) [1, 4, 9, 16, 25, 36, 49, 50, 51, 54]   []
-200 (1, 0, 50) [59, 131, 281, 491, 499, 571, 619, 641] ['A107157']

listPosDefQF(6, 'primitively')

-3 (1, 1, 1) [1, 3, 7, 13, 19, 21, 31, 37, 39, 43, 49] [A034017]
-4 (1, 0, 1) [1, 2, 5, 10, 13, 17, 25, 26, 29, 34, 37] [A008784, A037942]
-7 (1, 1, 2) [1, 2, 4, 7, 8, 11, 14, 16, 22, 23, 28]   [A244779]
-8 (1, 0, 2) [1, 2, 3, 6, 9, 11, 17, 18, 19, 22, 27]   [A057127]
-11 (1, 1, 3) [1, 3, 5, 9, 11, 15, 23, 25, 27, 31, 33] [A244780]
-12 (1, 0, 3) [1, 3, 4, 7, 12, 13, 19, 21, 28, 31, 37] [A244819]

List of indefinite quadratic forms

IQF = [(1,0,-1), (1, 1,-1), (1, 2,-1), (1,1,-2), (1, 2,-2), 
(1, 3,-1), (-1,2,3), (1,3,-2), (1, 4,-1), (1, 3,-3), (1, 4,-2),
(-1, 3, 4), (1, 4,-3), (1, 5,-1), (1, 4,-4), (1, 5,-2), (-3, 0, 3), 
(1, 5,-3), (1, 6,-1), (1, 5,-4), (1, 6,-2), (1, 5,-5), (1, 6,-3), 
(-3, 1, 4), (1, 6,-4), (1, 7,-1), (1, 6,-5), (3,3,-4), (1,6,-6), 
(3,5,-3), (-4, 4, 3), (4,1,-4), (1,8,-3), (1,10,-9), (1,15,-1)] 

def listIndefiniteQF():
    for q in IQF:
        lookup_OEIS(q, 'all')
        lookup_OEIS(q, 'primitively')
        lookup_OEIS(q, 'prime')

listIndefiniteQF()

The call listIndefiniteQF() produces the list below:

 4 (1, 0, -1) [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] ['A000040', 'A006005']
 4 (1, 0, -1) [1, 3, 5, 7, 8, 9, 11, 13, 15, 16, 17]    ['A047486', 'A229838']
 4 (1, 0, -1) [1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15]     ['A042965', 'A074227']
 5 (1, 1, -1) [5, 11, 19, 29, 31, 41, 59, 61, 71, 79]   ['A038872', 'A045468']
 5 (1, 1, -1) [1, 5, 11, 19, 29, 31, 41, 55, 59, 61, 71]['A089270']
 5 (1, 1, -1) [1, 4, 5, 9, 11, 16, 19, 20, 25, 29, 31]  ['A031363']
 8 (1, 2, -1) [2, 7, 17, 23, 31, 41, 47, 71, 73, 79, 89]['A001132', 'A038873']
 8 (1, 2, -1) [1, 2, 7, 14, 17, 23, 31, 34, 41, 46, 47] ['A057126']
 8 (1, 2, -1) [1, 2, 4, 7, 8, 9, 14, 16, 17, 18, 23]    ['A035251']
 9 (1, 1, -2) [7, 13, 19, 31, 37, 43, 61, 67, 73, 79]   ['A002476', 'A007645']
 9 (1, 1, -2) [1, 4, 7, 10, 13, 16, 18, 19, 22, 25, 27] []
 9 (1, 1, -2) [1, 4, 7, 9, 10, 13, 16, 18, 19, 22, 25]  ['A056991', 'A242660']
12 (1, 2, -2) [13, 37, 61, 73, 97, 109, 157, 181, 193]  ['A068228', 'A141122']
12 (1, 2, -2) [1, 6, 13, 22, 33, 37, 46, 61, 69, 73, 78]['A243655']
12 (1, 2, -2) [1, 4, 6, 9, 13, 16, 22, 24, 25, 33, 36]  ['A084916']
13 (1, 3, -1) [3, 13, 17, 23, 29, 43, 53, 61, 79, 101]  ['A038883', 'A141188']
13 (1, 3, -1) [1, 3, 9, 13, 17, 23, 27, 29, 39, 43, 51] ['A243656']
13 (1, 3, -1) [1, 3, 4, 9, 12, 13, 16, 17, 23, 25, 27]  ['A035256']
16 (-1, 2, 3) [3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71]['A002145', 'A045326']
16 (-1, 2, 3) [3, 4, 7, 11, 15, 19, 20, 23, 27, 31, 32] []
16 (-1, 2, 3) [3, 4, 7, 11, 12, 15, 16, 19, 20, 23, 27] []
17 (1, 3, -2) [2, 13, 17, 19, 43, 47, 53, 59, 67, 83]   ['A038889']
17 (1, 3, -2) [1, 2, 4, 8, 13, 16, 17, 19, 26, 32, 34]  []
17 (1, 3, -2) [1, 2, 4, 8, 9, 13, 16, 17, 18, 19, 25]   ['A035258']
20 (1, 4, -1) [5, 11, 19, 29, 31, 41, 59, 61, 71, 79]   ['A038872', 'A045468']
20 (1, 4, -1) [1, 4, 5, 11, 19, 20, 29, 31, 41, 44, 55] []
20 (1, 4, -1) [1, 4, 5, 9, 11, 16, 19, 20, 25, 29, 31]  ['A031363']
21 (1, 3, -3) [7, 37, 43, 67, 79, 109, 127, 151, 163 ]  ['A139492', 'A141159']
21 (1, 3, -3) [1, 7, 15, 25, 37, 43, 51, 67, 79, 85]    []
21 (1, 3, -3) [1, 4, 7, 9, 15, 16, 25, 28, 36, 37, 43]  ['A243172']
24 (1, 4, -2) [3, 19, 43, 67, 73, 97, 139, 163, 193]    ['A106950', 'A141170']
24 (1, 4, -2) [1, 3, 10, 19, 25, 30, 43, 46, 57, 58]    []
24 (1, 4, -2) [1, 3, 4, 9, 10, 12, 16, 19, 25, 27, 30]  ['A242661']
25 (-1, 3, 4) [19, 29, 59, 79, 89, 109, 139, 149, 179]  ['A030433', 'A045457']
25 (-1, 3, 4) [4, 6, 9, 14, 19, 21, 24, 25, 26, 29, 34] []
25 (-1, 3, 4) [4, 6, 9, 14, 16, 19, 21, 24, 25, 26, 29] []
28 (1, 4, -3) [2, 29, 37, 53, 109, 113, 137, 149, 193]  ['A107134', 'A141172']
28 (1, 4, -3) [1, 2, 9, 18, 21, 29, 37, 42, 53, 57, 58] []
28 (1, 4, -3) [1, 2, 4, 8, 9, 16, 18, 21, 25, 29, 32]   ['A242662']
29 (1, 5, -1) [5, 7, 13, 23, 29, 53, 59, 67, 71, 83]    ['A038901']
29 (1, 5, -1) [1, 5, 7, 13, 23, 25, 29, 35, 49, 53, 59] []
29 (1, 5, -1) [1, 4, 5, 7, 9, 13, 16, 20, 23, 25, 28]   ['A035264']
32 (1, 4, -4) [17, 41, 73, 89, 97, 113, 137, 193, 233]  ['A007519', 'A045390']
32 (1, 4, -4) [1, 8, 17, 28, 41, 49, 56, 73, 89, 92, 97][]
32 (1, 4, -4) [1, 4, 8, 9, 16, 17, 25, 28, 32, 36, 41]  ['A242663']
33 (1, 5, -2) [3, 31, 37, 67, 97, 103, 157, 163, 181]   ['A107013', 'A141177']
33 (1, 5, -2) [1, 3, 4, 12, 16, 22, 31, 34, 37, 48, 58] []
33 (1, 5, -2) [1, 3, 4, 9, 12, 16, 22, 25, 27, 31, 34]  ['A243185']
36 (-3, 0, 3) [3]                                       []
36 (-3, 0, 3) [3, 9, 15, 21, 24, 27, 33, 39, 45, 48, 51][]
36 (-3, 0, 3) [3, 9, 12, 15, 21, 24, 27, 33, 36, 39, 45]['A136290']
37 (1, 5, -3) [3, 7, 11, 37, 41, 47, 53, 67, 71, 73, 83]['A038913', 'A141178']
37 (1, 5, -3) [1, 3, 7, 9, 11, 21, 27, 33, 37, 41, 47]  []
37 (1, 5, -3) [1, 3, 4, 7, 9, 11, 12, 16, 21, 25, 27]   ['A035267']
40 (1, 6, -1) [31, 41, 71, 79, 89, 151, 191, 199, 239]  ['A141180']
40 (1, 6, -1) [1, 6, 9, 10, 15, 26, 31, 39, 41, 54, 65] []
40 (1, 6, -1) [1, 4, 6, 9, 10, 15, 16, 24, 25, 26, 31]  ['A242664']
41 (1, 5, -4) [2, 5, 23, 31, 37, 41, 43, 59, 61, 73, 83]['A038919', 'A141181']
41 (1, 5, -4) [1, 2, 4, 5, 8, 10, 16, 20, 23, 25, 31]   []
41 (1, 5, -4) [1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 23]    ['A035269']
44 (1, 6, -2) [5, 37, 53, 89, 97, 113, 137, 157, 181]   ['A141182']
44 (1, 6, -2) [1, 5, 14, 22, 25, 37, 38, 49, 53, 70, 77][]
44 (1, 6, -2) [1, 4, 5, 9, 14, 16, 20, 22, 25, 36, 37]  ['A243166']
45 (1, 5, -5) [19, 31, 61, 79, 109, 139, 151, 181, 199] ['A033212', 'A141184']
45 (1, 5, -5) [1, 9, 19, 31, 45, 55, 61, 79, 99, 109]   []
45 (1, 5, -5) [1, 4, 9, 16, 19, 25, 31, 36, 45, 49, 55] ['A243174']
48 (1, 6, -3) [13, 37, 61, 73, 97, 109, 157, 181, 193]  ['A068228', 'A141122']
48 (1, 6, -3) [1, 4, 13, 24, 33, 37, 52, 61, 69, 73, 88][]
48 (1, 6, -3) [1, 4, 9, 13, 16, 24, 25, 33, 36, 37, 49] ['A243168']
49 (-3, 1, 4) [2, 11, 23, 37, 53, 67, 79, 107, 109, 137]['A045374', 'A045387']
49 (-3, 1, 4) [2, 4, 9, 11, 15, 16, 18, 22, 23, 25, 30] []
49 (-3, 1, 4) [2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25]  []
52 (1, 6, -4) [3, 13, 17, 23, 29, 43, 53, 61, 79, 101]  ['A038883', 'A141188']
52 (1, 6, -4) [1, 3, 4, 9, 12, 13, 17, 23, 27, 29, 36]  []
52 (1, 6, -4) [1, 3, 4, 9, 12, 13, 16, 17, 23, 25, 27]  ['A035256']
53 (1, 7, -1) [7, 11, 13, 17, 29, 37, 43, 47, 53, 59]   ['A038931', 'A141189']
53 (1, 7, -1) [1, 7, 11, 13, 17, 29, 37, 43, 47, 49, 53][]
53 (1, 7, -1) [1, 4, 7, 9, 11, 13, 16, 17, 25, 28, 29]  ['A243191']
56 (1, 6, -5) [2, 11, 43, 67, 107, 113, 137, 163, 179]  ['A141190']
56 (1, 6, -5) [1, 2, 11, 22, 25, 35, 43, 50, 65, 67, 70][]
56 (1, 6, -5) [1, 2, 4, 8, 9, 11, 16, 18, 22, 25, 32]   ['A243186']
57 (3, 3, -4) [2, 3, 29, 41, 53, 59, 71, 89, 107, 113]  ['A141192']
57 (3, 3, -4) [2, 3, 8, 12, 14, 21, 29, 32, 38, 41, 48] []
57 (3, 3, -4) [1, 2, 3, 8, 12, 14, 18, 21, 27, 29, 32]  ['A243192']
60 (1, 6, -6) [61, 109, 181, 229, 241, 349, 409, 421]   ['A107152', 'A141301']
60 (1, 6, -6) [1, 10, 21, 34, 49, 61, 66, 85, 106, 109] []
60 (1, 6, -6) [1, 4, 9, 10, 16, 21, 25, 34, 36, 40, 49] ['A243188']
61 (3, 5, -3) [3, 5, 13, 19, 41, 47, 61, 73, 83, 97]    ['A038941', 'A141215']
61 (3, 5, -3) [1, 3, 5, 9, 13, 15, 19, 25, 27, 39, 41]  []
61 (3, 5, -3) [1, 3, 4, 5, 9, 12, 13, 15, 16, 19, 20]   ['A243654']
64 (-4, 4, 3) [3, 11, 19, 43, 59, 67, 83, 107, 131, 139]['A007520', 'A045339']
64 (-4, 4, 3) [3, 11, 16, 19, 27, 28, 35, 43, 51, 59]   []
64 (-4, 4, 3) [3, 11, 12, 16, 19, 27, 28, 35, 43, 44]   []
65 (4, 1, -4) [29, 61, 79, 101, 131, 139, 179, 181, 191]['A141111']
65 (4, 1, -4) [1, 4, 10, 14, 16, 26, 29, 35, 40, 49, 56][]
65 (4, 1, -4) [1, 4, 9, 10, 14, 16, 25, 26, 29, 35, 36] ['A243170']
76 (1, 8, -3) [5, 17, 61, 73, 101, 137, 149, 157, 197]  ['A142956']
76 (1, 8, -3) [1, 5, 6, 9, 17, 25, 30, 38, 45, 54, 57]  []
76 (1, 8, -3) [1, 4, 5, 6, 9, 16, 17, 20, 24, 25, 30]   []
136 (1, 10, -9) [2, 47, 89, 191, 223, 239, 271, 359]    []
136 (1, 10, -9) [1, 2, 15, 30, 33, 47, 55, 66, 81, 87]  []
136 (1, 10, -9) [1, 2, 4, 8, 9, 15, 16, 18, 25, 30, 32] []
229 (1, 15, -1) [37, 53, 173, 193, 229, 241, 347, 359]  ['A141166']
229 (1, 15, -1) [1, 15, 27, 33, 37, 45, 51, 53, 55, 57] []
229 (1, 15, -1) [1, 4, 9, 15, 16, 25, 27, 33, 36, 37]   []

Number of represented integers below N as a function of the discriminant

Looking at the examples above the impression arises that the number of integers which are represented by a positive definite form decreases when the absolute value of the discriminant increases. The following numerical experiment confirms this. The clear upper bound in the plot below calls for an explanation.

def numberOfPosDefQF(n, belowOrEqual, filter = 'all'):
    F = posDefQF()     
    L = []
    for i in range(n):
        q = F.next()
        Q = binaryQF(q)
        rep = Q.represented_positives(belowOrEqual, filter, verbose = False)
        d = Q.discriminant()
        L.append((-d, len(rep)))
    return L
    
print numberOfPosDefQF(10, 100)

    (3, 36), (4, 43), (7, 41), (8, 51), (11, 39), (12, 36), 
    (15, 30), (16, 32), (19, 36), (20, 32)]    

This might take a while:

A = numberOfPosDefQF(500, 10000) 
R = numberOfPosDefQF(500, 10000, 'primitively')
P = numberOfPosDefQF(500, 10000, 'prime')       
allplot = list_plot(A[5::], color='blue', legend_label='all reps')
primeplot = list_plot(P[5::], color='purple', legend_label='prime reps')
combi = allplot + primeplot
combi.axes_labels(['positive definite QF with discriminant -n',\ 
                   'number of reps below 10000'])
show(combi, title='Number of reps as a function of the discriminant.',\ 
            frame=True, legend_loc="upper right")

Please report bugs immediately to the author. Suggestions for improvements and extensions are welcome.

References

  • Johannes Buchmann, Ulrich Vollmer: Binary Quadratic Forms, Springer, Berlin 2007.
  • Pete L. Clark, Topics in Arithmetic Geometry II, Handout 3: Elementary Theory of Quadratic Forms.
  • Henri Cohen, A Course in Computational Algebraic Number Theory, Springer‎ 1993.
  • Franz Lemmermeyer, Binary Quadratic Forms, 2010.
  • Andrew Sutherland, Introduction to Arithmetic Geometry, Lecture 9: Quadratic forms, MIT Open Course Ware, Fall 2013.   Of special interest is definition 9.7 and theorem 9.9. Sutherland writes: "The constraint that x!=0 is critical, otherwise every quadratic form would represent 0; the quadratic forms that represent 0 are of particular interest to us."
  • Elementary Number Theory – Section 3.2 Binary Quadratic Forms.
    Elementary Number Theory – Section 3.3 Sums of two squares.

This is an IPython Notebook which was developed on SageMath Cloud. SageMath Cloud is a free service with support from University of Washington, the National Science Foundation and Google. Sage is a free open source alternative to Magma, Maple, Mathematica and Matlab. Get an account on SageMath Cloud, download this notebook, upload it to SMC and start exploring!

Personal tools