This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/BinaryQuadraticForms
From OeisWiki
Contents
- 1 Positive Numbers represented by aBinary Quadratic Form
- 1.1 Definitions
- 1.2 Geometric view
- 1.3 Some examples at a glance
- 1.4 A Sage based Python class: 'binaryQF(a, b, c)'
- 1.5 Computations
- 1.6 Utility functions
- 1.7 List of positive definite quadratic forms
- 1.8 List of indefinite quadratic forms
- 1.9 Number of represented integers below N as a function of the discriminant
- 1.10 References
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
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, 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 A065091 ⊆ A047486 ⊆ A042965 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'.
| 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
Note: The implementation below was written in 2014 with Python 2. An updated version using Python 3.10 can be found on GitHub.
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!
