Reference / Paper · 1970
Integer Sequences Having Prescribed Quadratic Character (Math. Comp. 24, 433–451)
Pseudosquare searches run on the Lehmers' electronic sieves, with the machines' role described.
Reference / Paper · 1970
Pseudosquare searches run on the Lehmers' electronic sieves, with the machines' role described.
MATHEMATICS OF COMPUTATION, VOLUME 24, NUMBER 110, APRIL, 1970 Integer Sequences Having Prescribed Quadratic Character By D. H. Lehmer, Emma Lehmer and Daniel Shanks Abstract. For the odd primes p, = 3, p2 = 5, ■• -, we determine integer sequences Np such that the Legendre symbol (N/p,) = +1 for all p¡ S P for a prescribed array of signs ± 1; (i.e., for a prescribed quadratic character). We examine six quadratic characters having special interest and applications. We present tables of these Np and examine some applications, particularly to questions concerning extreme values for the smallest primitive root (of a prime N), the class number of the quadratic field R(J —N), the real Dirichlet L functions, and quadratic character sums. Introduction. Let pu p2, ..., pm be a set of odd primes and let eu e2,..■, em be a sequence with e2 = 1. The problem considered here is that of finding an integer N such that (1) (N/Pi) = eh (i = l(l)m), where the symbol is that of Legendre. In other words we are looking for a positive integer N whose quadratic character with respect to each of the given p¡ is specified. This is a special case of a more general problem of Kummer in which the e's are /cth roots of unity and the symbols are feth power characters. This problem has infinitely many solutions for every k, cf. Mills [1]. For k = 2 the infinitude of solutions follows from the law of quadratic reciprocity, since N lies in an arithmetical progression of difference 4p, for each of the m values of i, and hence there exists an arithmetical progression of difference 4pip2... pm every term of which is a desired number N. This argument can also be used to obtain the asymptotic density of the TV'sand even the density of prime values of N, but it fails to give any information about the smallest positive value of N. The problem of finding the values of N in natural order is solved automatically by the Delay Line Sieve, DLS 127 [2] provided the p¡ ^ 127. In what follows we consider six problems of special interest which have applications to other branches of the theory of numbers. In these problems pi =3, p2 = 5,..., p¡ is the ith odd prime, the e's form a simple pattern, and N is usually specified modulo 8. We present tables of these integer sequences N for the several problems considered, and examine some of their applications, particularly to questions concerning primitive roots, class numbers, Dirichlet L functions, and quadratic character sums. For example, we show that if any algebraic field R(J - A) of class number 3 exists besides the known examples, then A > 1.4 ■1012. Received August 22, 1969. AMS Subject Classifications. Primary 1016, 1060; Secondary 1041, 1064, 1066. Key Words and Phrases. Quadratic character, tions, quadratic character sums, pseudo-squares. sieves, primitive roots, class number, Dirichlet L func- 433 Copyright © 1970, American Mathematical Society 434 Problem I. D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS Find N = 1 (mod 8) with s¡ = 1 for all odd/?, = p in (1). A solution Np of this problem is a quadratic residue ( / 0) of all primes p¡ _ p and hence every odd square satisfies the conditions of the problem. We shall be interested here in solutions which are not perfect squares and which have been called pseudo-squares. Marshall Hall [3] has shown how to use these numbers for a test for primality. Cobham [4] pointed out that the pseudo-squares afford a cheap way of deciding whether a given number is a perfect square or not. Kraitchik [5] listed the least pseudo-square for p ^ 47, and Lehmer [6] and [7] extended this list to p = 61, and p S 79, respectively. Using the DLS 127 this table was recently extended to p = 127. For completeness we give the least pseudo-square for 3 _ p _ 127 in Table I. Table I Table of Pseudo-Squares p 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59,61 67 71,73 79 83,89,97 101 103 107,109 113,127 Least Solution 73 241 1009 2641 = 19-139 8089 18001 = 47 • 383 53881 87481 117049 = 67-1747 515761 1083289 3206641 = 643-4987 3818929 9257329 22000801 48473881 175244281 427733329 898716289 2805544681= 127-859-25717 10310263441=4007-2573063 23616331489 85157610409= 397-214502797 196265095009 Least Prime Solution 73 241 1009 2689 8089 33049 53881 87481 483289 515761 1083289 3818929 3818929 9257329 22000801 48473881 175244281 427733329 898716289 Unknown Unknown 23616331489 Unknown 196265095009 Least Prim. Root 5 7 11 19 17 29 31 29 31 37 41 53 53 53 59 97 79 83 101 107 131 The difficulty of this problem is the necessity of eliminating the perfect squares which, to start with, completely upset the expected asymptotic density of the solutions, which is 435 INTEGER SEQUENCES To overcome this difficulty we exploit the capability of the DLS 127 of counting the number of its solutions without actually putting them out. It is clear that the number of unwanted perfect squares g X is exactly the number <p(Pm,X1'2) of numbers prime to Pm = pip2 ...pm and ^ Xil2. This, in turn, is the number of solutions x _ Xi/2 given by the Sieve of the trivial Diophantine equation xy = 1. These two problems were run alternately, using a logarithmic search procedure until the extra nonsquare solution was located and verified. The deviations from the probabilistic estimate (2) caused by the squares is very marked. While odd perfect squares automatically satisfy N = 1 (mod 8) and e¡ = 1, and there are therefore many more solutions of (1) than is indicated by (2), the number of pseudo-square solutions is substantially smaller. For example, for m = 22, p¡ _ pm = 83, there are 168091 solutions of (1) less than 13089432= 1713331777249. But 161409 of these are squares, and only 6682 pseudo-square solutions occur. The number of solutions predicted by (2) is 12554. Western and Miller [8] tabulate the least prime solution Np for p = 53. By the law of quadratic reciprocity this is equivalent to finding the least prime Np whose least quadratic nonresidue exceeds p. This insures that every prime <NP has a quadratic nonresidue less than p and that there exist primes with arbitrarily large least primitive roots. In Table I, the least prime solution Np and its least primitive root is also listed. Western and Miller also give a companion table of least negative prime solutions. From our point of view this corresponds to the following problem. Problem II. Find N = -1 (mod 8) with e¡ = (- l/p¡) for all p¡ = p. The negatives —Np of the solutions of this problem are quadratic residues ( # 0) of all primes p¡ ^ p and hence can be thought of as negative pseudo-squares. This time there is no direct interference from actual squares and one may expect a more predictable distribution. The following short table is for pm = 53, m = 15, Am= 1.03829-10"6. Limit-10-6 No. of Sol. Exp.No. No. of Sol./Exp. No. 275 324 466 725 1297 2720 19617 28925 81324 97900 117000 150 200 300 500 1000 2500 18560 27950 80654 97463 116780 286 336 484 753 1347 2824 20368 30033 84438 101649 121480 .524 .595 .620 .664 .742 .885 .911 .931 .955 .959 .961 If Problems I and II are thought of as a single problem, one can conjecture that the density of negative pseudo-squares approaches the expected value as the limit -» oo and the influence of the perfect squares recedes. 436 D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS Table II Negative Squares L,east Least Prime Solution P Least Solution 3 5 7 11 13 17 19 23 29 31 37,41 43 47 53 59 61 67 71 73,79 83 89 97 101, 103 107 109 113,127 131 23 71 311 479 1559 5711 10559 18191 31391 307271 = 109• 2819 366791 2155919 = 59-36541 2155919 2155919 6077111 = 1039-5849 6077111 98538359 = 79■1247321 120293879 131486759 508095719= 367-547-2531 2570169839= 439•5854601 2570169839 2570169839 2570169839 2570169839 328878692999 513928659191 23 71 311 479 1559 5711 10559 18191 31391 366791 366791 4080359 12537719 30706079 36415991 82636319 120293879 120293879 131486759 2929911599 2929911599 7979490791 33857579279 89206899239 121560956039 328878692999 513928659191 Prim. Root 5 7 17 13 19 19 23 29 31 43 43 47 53 59 67 67 73 73 83 97 97 109 107 109 113 131 139 The least solution of Problem II for each 3 _ p _ 131, and the least prime solution, in case the least solution is composite, is given in Table II together, again, with the primitive roots. The negative squares have the property that the corresponding quadratic imaginary fields R{J —N) have exceptionally large class numbers relative to JN, and exceptionally large real Dirichlet L functions at argument 1 : (3) UX,x) = I -N Here, ( —N/ri) is the Kronecker symbol. A reflection of this property is that for all —Np listed in Table II with p > 11 there exist reduced, binary quadratic forms (A, B, C) = Au2 + Buv + Cv2 of discriminant -NPm = B2 - 4AC for every A = 1, 2, 3, ... less than pm+1. For example, for N97 = 7979490791, we have 437 INTEGER SEQUENCES Table Ha Negative Squares P L(l, X) h(-Np) 3 5 7 11 13 17 19 23 29 31 37,41 43 47 53 59 61 67 71 73,79 83 89 97 101, 103 107 109 113,127 131 992 5.62213 2968 2968 2968 5092 5092 21934 6.35035 6.35035 6.35035 6.48918 6.48918 6.94169 51460 122106 122106 122106 122106 122106 7.17211 7.56669 7.56669 7.56669 7.56669 7.56669 h(~Np) 3 1 19 25 51 109 153 213 289 1121 1121 3997 7457 12017 12719 20299 24503 24503 25817 128755 128755 219207 456929 761619 883537 1499699 1870227 UX,x) 1.96520 2.60987 3.38472 3.58858 4.05786 4.53127 4.67767 4.96137 5.12442 5.81495 5.81495 6.21634 6.61614 6.81293 6.62151 7.01518 7.01855 7.01855 7.07318 7.47286 7.47286 7.70933 7.80137 8.01103 7.96118 8.21554. 8.19583 (1, 1, 1994872698), (2, ± 1, 997436349), (3, ± 1, 664957566), (4, ± 3, 498718175), (5, ± 3, 398974540), (6, ± 1, 332478783), (6, ±5, 332478784), ., Similarly, for this discriminant, (100, ±53, 19948734). the series (3) begins as the harmonic series 1 1 + 2 + 3 + - + löö TÔT with the first hundred terms positive. We list in Table Ha these class numbers h( —N„) and these functions L(l, x) for both prime and composite Np. The composite cases (with even class numbers) are on the left, as in Table II. These numbers, which are related by 438 D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS (4) L(l,x) = nh(-N)/JN, were computed by the method described in [9]. Returning briefly to Problem I, we note that a Table la would begin : p 3 5 7 11 13 h{N) L(l,x) 2 3.50737 h(N) 1 1 7 1 1 L(l,x) 1.79464 2.41835 3.07844 3.4845Í 3.96332 We have not completed this table as the functions are much more difficult to compute for large positive discriminants. But two comments are in order. First, while these L(l, x) tend to be large, no particular correlation is indicated for the corresponding class numbers. Instead of (4) one has (5) L(1,z)=E,^l_ln(U + ,V^(N) n=l\H/rt JN where u2 — Nv2 = 1 is the smallest Pell solution. Usually, h(N) is quite small, and the largeness of L(l, x) is reflected, instead, in an exceptionally long period for the regular continued fraction for JN. (It is this that makes the computation difficult.) Secondly, while the L(l,x) are relatively large, they are not as large as could be expected by a simple probabilistic estimate. This, again, reflects the peculiarities in the distribution of the pseudo-squares discussed above. While the phenomenon is of interest, we will not pursue it here. The problem which can be thought of as complementary to Problem II is as follows. Problem III. Find N s 3 (mod 8) with e¡ = - ( - l/p¡) for p, g p. The negatives —Np of the solutions of this problem are quadratic nonresidues ( # 0) of all the primes Pi ;_ p. Such numbers were first considered by Euler in connection with quadratic functions whose values have a high density of primes. In fact, the polynomial (6) x2 + x + (N + l)/4 of discriminant —N will not be divisible by 2, or any of the specified primes. Euler hit upon the remarkable N31 = 163, which led to the well-known polynomial x2 + x + 41. Other polynomials of this sort were proposed by Beeger, Poletti, and others [10]-[11]. See also [14]. Since it was established by Stark [12] that 163 is the largest number N with a class number h( —N) = 1, we know that there does not exist another value of N for which the polynomial (6) is a prime for all values of x < (N + l)/4. Nonetheless, further solutions of Problem III beyond iV37 = 163 do provide examples in which the class number h( —N) and L function (3) are apt to be unusually small, while the quadratic polynomial formula (6) possesses an unusually high density of primes. The first two properties are especially obvious when we rewrite (3) in product form : ra m.a.-íz'S.ñ JN " PlJ2p-(-N/p) INTEGER SEQUENCES 439 since we now have (-N/p) = -1 for all small p, and that minimizes all of the corresponding factors. Least solutions Np and least prime solutions N'p for 3 = p ^ 163 are given in Table III. Table Ilia gives the class numbers and L functions. Table III extends an earlier table to p = 107, by Lehmer [13]. Mohan Lai [14] has also computed the h( —Np) through p = 107, and in [14] he, and one of us, discuss some other aspects of this problem. The decrease of L(l, x) with p is, of course, not monotonie. The Legendre symbols beyond {N | p) remain unspecified, and if, in these first solutions, these following symbols have an early preponderance of values ( —N \ p¡) = —1, as in Ni21, the L(l, /) is especially small. Contrary wise, as in N\3g, the L(l, x) is "rather poor". Such small values for L(l,x) relate to an investigation of Chowla, Ayoub and Wal urn [15]. It is known that h( —q) for primes q = 3 (mod 4) can also be obtained from the sums Si(«) ='z vQ= -qh(-q) or from S2(4)=I>2Q= -q2h(-q), and these quadratic character sums are therefore, of necessity, negative. But in [15] it is proven that will be positive for infinitely many primes q. To obtain a positive S3(q) it would suffice if but that is not easy to attain. No entry in Table Ilia is that small, or even close. For all q = N'plisted, we have S3(q)< 0; e.g., S3(163)= -2066677 = -12679 ■163. As was indicated, there is no reason for the first solution N'p to be especially good, in this respect, and we have also examined some subsequent solutions. The best prime q presently known to us has h(-85702502803) = 16259 with L(l, x) = 0.17448. This is a subsequent solution for p = 107. The smallest L(l, x) presently known to us for negative discriminants is that of a large, composite solution for p = 149: N = 84148631888752647283= 6079-30469- 132137-3438209 has h(-N) = 496652272 and U\,%) = 0.17009. 440 D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS Table III for all Pi = p, Pi) N = 8x + 3 p Least Solution Np 3 5,7 11,13 17,...,37 41 43 47 53,59 61 67 71 73,79 83 89 97,101,103 107 109,113 127 131,137 139 149 151,157,163 19 43 67 163 77683 = 131-593 77683 1333963 2404147 20950603 36254563= 127• 285469 51599563 96295483 114148483= 101-463-2441 269497867= 317 •419 • 2029 269497867 585811843= 14081-41603 52947440683 71837718283= 281 ■3709■68927 229565917267 575528148427= 149- 283 • 13648781 1271259755683 1432817816347 Least Prime Solution N'p 19 43 67 163 222643 1333963 1333963 2404147 20950603 51599563 51599563 96295483 146161723 1408126003 3341091163 52947440683 52947440683 193310265163 229565917267 915809911867 1271259755683 1432817816347 It is clear that we are a long way from exhibiting even a single example of S3(q) > 0 unless its necessary condition is substantially more generous than the sufficient con- dition (8). In fact, however, one has [15] (9) S3(q) = q'Jq In Ï L(3,x) - L(\, x) where we have corrected an erroneous factor of \ and where ¿(3,x)= p=2 n-rP - i-q/p) Now L(3,x)>p=2I^Vï pii C(6)= 0.84634, i(3) and this gives the sufficient condition (8). In our cases L(3, x) will be slightly larger; e.g., for q = 163, INTEGER SEQUENCES Table Illa for all Pi = p. Pi h(-Np) N = 8x + 3 h(-N'p) L(l,x) 3 5,7 11,13 17,...,37 41 43 47 53,59 61 67 71 73,79 83 89 97,101,103 107 109,113 127 131,137 139 149 151,157,163 22 22 0.24798 0.24798 432 0.22540 692 1044 1044 1536 0.20348 0.19979 0.19979 0.19937 15204 0.17821 44332 0.18358 L(3,Z)= ^L 163V163 1 1 1 1 33 79 79 107 311 487 487 665 857 2293 3523 13909 13909 26713 29351 59801 66287 70877 L(\, X) 0.72073 0.47909 0.38381 0.24607 0.21971 0.21488 0.21488 0.21680 0.21346 0.21299 0.21299 0.21290 0.22270 0.19197 0.19148 0.18990 0.18990 0.19087 0.19245 0.19632 0.18470 0.18602 = 0.84643, but for p = 41 in Table Ilia we must have 41 „3 p3 -\ l{3,x)< nlJ2 p3 +1 C(3)= 0.84644. Therefore, 3 2tt2 L(3, x) < 0.12865, and since this is smaller than any L(l, x) shown in Table Ilia, we do confirm S3(q) < 0 for all of these primes. In contrast, consider SM = 'l V4fV 442 D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS Now we have (10) SM = <V? n 2 L(3, x) - L(l, x) \_n which may be neatly derived from (9) as follows. For any n _ 0, we obtain Ï v"(9 - v)" Q =0 since ((« - v)/«) = -(v/iX and each term v = a cancels that for v = q — a. For n = 2 and 1 we obtain SM - 2qS3(q) + q2S2(q) = 0, S2(q) - qS^q) = 0, and thus (11) S4q) = 2qS3{q)+ q4h(-q). Combining (11) and (9) now gives (10). Therefore, a sufficient condition for S4(q) > 0 is t(12) ) L(l, y) < ^(6) = 0.25726. K k) 2C(2)C(3) This condition is met by all N'p shown in Table Ilia starting with N'37 = 163. (In fact, from (11) and the previously indicated value of S3(163), we have S4(163) = [1632 - 2(12679)]1632 = 1211 • 1632.) It is reasonable to conjecture that S4(<j)> 0 for all subsequent N'p beyond our table, but probably that would be difficult to prove. Presumably, one should attempt to prove it for all p > Po (hopefully small), and then continue the table (if necessary) up to this lower bound p0. In passing, we note that these character sums may be expressed simply in terms of generalized Euler numbers [16]. For q = 3 (mod 8) we have Hq) = <z(c,.i- 4g2c,,0)/12 (13) SA(q) = q2(cqA - 2q2c,,0)/6. For example, Ci63,0 = 3 and c163il = 166680, and we may verify the previously indicated sums. Problem IV. Find N = -1 (mod 8) as in Problem II, but with e, = - ( - l/p¡) as in Problem III. Since the first factor on the right of (7) is now f instead of § as it was in Problem III, we can expect the values of h( —N) to be about 3 times those of the last problem. It might seem, at first, that these N are of little interest, since we clearly are aiming at small h{—N) and yet we start off immediately in the wrong direction. But there is another viewpoint. The pre-Kronecker formulation of these problems by Gauss and Dirichlet dealt only with even discriminants. One has the forms INTEGERSEQUENCES 443 Au2 + 2Buv + Cv2 of determinant D = B2 - AC for every nonsquare integer D. The class number is now h(4D), and the Dirichlet series, for negative D = —N is now _ nh{-4N) (14) " / -N \ 1 " p M1)= -J4Ñ- - k WTï) 2TTT= }Xp-i-N/p) with Jacobi symbol ( —N/(2k +1)) and Legendre symbol ( —N/p). The quadratic polynomial (6) now becomes (15) x2 + N, and similar questions arise concerning its density of primes, cf. [17]-[18]. It is known that h(-4N) = h(-N) for our present N = —1 (mod 8), while h(-4N) = 3h{-N) for N = 3 (mod 8). This nullifies the previously mentioned factor of 3, and now, using ¿v(l) instead of L(l, x), these two residue classes modulo 8 can be compared on an equal basis, not only with each other, but with any residue class modulo 8. This gives us a much richer population to study. We list the first composite and prime solutions in Table IV, while Table IVa gives the values of h{-N) = h(-4N) and of Ln(1). The smallest LN(1) presently known to us is ¿569078186623(1) = 0.25346; (p = 137). It is smaller than those for any of the N singled out for special mention in the previous problem. These have values ¿71837718283(1) = 0.26731, ¿85702502803(1) (P = 127) = 0.26172, and ¿84148631888752647283(1) = 0.25513. In Problem V below our smallest value is ¿3666575384938(1) = 0.26064 (p = 157). Analogous to our remarks concerning h(— 163) in the previous problem, we call attention to h(-4-l)=\, /i(-4-127) = 5, /i(-4-487) = 7 in Table IVa. These have been proven [19] to be the largest negative determinants with these class numbers. While the same is probably true of the entry 444 D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS Table IV -1 Pi Least Solution N„ P 3.5 7 11 13 17 19 23 29 31 37,41 43 47 53,59,61 67 71 73 79 83 89 97 101 103 107 109 113,127 131 137 139 149,151 157,163 for all p¡ = p, N = 8x + 7 1 127 247 = 13 19 463 487 1423 33247 56743 = 179-317 74743 = 41•1823 118903 348727 = 241•1447 348727 773767 2430943 = 227 ■10709 2430943 2430943 242675623 191-263-4831 393292183 5573• 70571 393292183 393292183 1656835783= 739-827-2711 2713676023= 17747■152909 4352137927= 64661• 67307 8133814327= 643•12649789 8133814327 8363603623= 57047■146609 8363603623 1128864945583= 4943-228376481 3402396344407= 138727-24525841 3402396344407 Least Prime Solution N'p 7 127 463 463 487 1423 33247 73327 118903 118903 454183 773767 773767 86976583 125325127 132690343 788667223 788667223 1280222287 2430076903 10703135983 10703135983 10703135983 10703135983 15605135527 148202808007 569078186623 3506439768967 3506439768967 Unknown M-4 1423)= 9, that remains unproven [19]. But the proposition is not general. For example, h{-4 ■33247) = 53 with L33247(l) = 0.45658 certainly looks unlikely in view of the size of its LN{1),and, in fact, we find in Ordman's table [20] that there is a larger example : h(-4 ■39103) = 53 with L391031.I)= 0.42101. It is instructive to note that this latter determinant (-39103 113) = +1. already fails on p = 13: 445 INTEGER SEQUENCES Table IVa -1 /' 3.5 7 11 13 17 19 23 29 31 37,41 43 47 53,59,61 67 71 73 79 83 89 97 101 103 107 109 113,127 131 137 139 149,151 157,163 h(-4Np) for all pi = p, N = 8x + 7 ¿n„(1) 0.59968 h(-4N'p) 1 5 7 7 7 53 73 83 83 157 185 185 1927 2295 2273 5313 5313 7173 9529 18545 18545 18545 18545 22635 66011 121725 344909 344909 0.59371 0.69693 0.51101 0.51101 0.49826 0.37477 0.45658 0.42346 0.37810 0.37810 0.36594 0.33036 0.33036 0.32456 0.32202 0.30996 0.29718 0.29718 0.31490 0.30364 0.28157 0.28157 0.28157 0.28157 0.28462 0.26934 0.25346 0.28933 0.28933 Unknown Unknown 9 60 66 0.39565 0.37921 136 136 0.36176 0.36176 312 312 312 3064 3718 3718 3718 8096 9826 12384 16602 16602 16760 16760 182424 323392 323392 0.31433 0.31433 0.31433 0.30896 0.29449 0.29449 0.29449 0.31243 0.29629 0.29487 0.28916 0.28916 0.28787 0.28787 0.26970 0.27540 0.27540 ¿n;,(1) Class Number 3 and a Brief Return to Problem HI. The question whether /i(-4-1423) = 9 exhibits the largest determinant having class number 9 is essentially equivalent to that whether ¿,(-907) = 3 exhibits the largest discriminant having class number 3. The primes p = 8x + 7 having h( —p) = 3 or 9 are completely known [19]: h(-p) = 3 forp = 23,31; h(-p) = 9 forp = 199, 367, 823, 1087, 1423; 446 D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS and if we join these sets, respectively, with all p = 8x + 3 having h( —p) = 3, we would obtain the complete set of discriminants with h( —p) = 3, or the complete set of determinants with h{—4p) = 9. The known p = 8x + 3 with this class number are [19] : p = 59, 83, 107, 139,211, 283, 307, 331, 379,499, 547, 643, 883,907 to which we may add p5 = 243 if we do not insist that the discriminant be square-free. There are no other h{—p) = 3 for p ^ 166807 by the tables of Ordman [20] and Newman [21]. Any P = 8x + 3 > 1467 = 32 • 163 having h(-P) = 3 must have L(l, x) < 0.24607. By a systematic calculation, we find that there are only eight p = 8x + 3 < 318028 with an L(l, x) that small, and they have these class numbers: p 90787 166147 h(-p) 23 29 p 210907 222643 h(-p) 35 33 191563 205627 33 35 253507 296587 39 41 Since any further example P must therefore exceed 318028 = 4 ■433, the argument in [19, esp. p. 153, 162], based upon composition of forms, may now be applied as follows. If ( —P | q) = +1, there is a form F = (q, b, c) of discriminant -P. Then Table V ; j for all Pi = p, N = 8x + 5 p Least Solution Np Least Prime Solution N'p 3 5,...,23 29,...,47 53 59 61,67 71 73 79,83 89,97 101,103,107 109 113 127,131,137 139,149,151 157,...,181 5 29 23669 1508789 5025869 7841261 = 227-34543 9636461 18127229= 491•36919 31839341 = 101-239-1319 37989701 240511301 23739440141= 241 • 367 • 268403 44913466781= 13339-3367079 60664576541= 149-407144809 123464393861 1833287692469 5 29 23669 1508789 5025869 9636461 9636461 37989701 37989701 37989701 240511301 41868418349 90664613309 123464393861 123464393861 1833287692469 447 INTEGER SEQUENCES F3 = FH{~F)represents q3 and equals the principal form. Therefore, q3 = u2 + uv + (P + l)t)2/4 or 4q3 = (2u + v)2 + Pv2. Since this is impossible for 4q3 < P, we must have (-P/q)= -1 for every q = 43. By Tables III and Ilia we therefore have P > JV43= 1333963. But, one also has 4-673<N43, 4-1633 < JV'67, and 4-70793 <N'163, so repetition of the argument shows that P ^ N'7079 > JV'i63 = 1432817816347, and (-P/q)= -1 for all q _ 7079, are both necessary. Such a P must also have L(l, x) < 3n/jN'l63 = 0.0000079, and therefore either 907 and 1423 are the last examples of h( —p) = 3 and h( —4p) = 9, or any counterexample would (easily) satisfy S3(P) > 0. We must admit that we would be pleased with either contingency. Table Va for all Pi ^p, P 3 5,...,23 29,...,47 53 59 61,67 71 73 79,83 89,97 101,103,107 109 113 127,131,137 139,149,151 157,...,181 h(-8Np) -2N ,(D N = 8x + 5 h(-SN'p) 2 2 832 0.33002 1148 1648 0.29949 0.32440 39880 59012 65300 0.28749 0.30928 0.29448 46 406 718 950 950 1698 1698 1698 3990 53510 77970 89478 89478 317722 ¿2*1,(1) 0.99346 0.41251 0.33210 0.36713 0.35573 0.33991 0.33991 0.30599 0.30599 0.30599 0.28577 0.29047 0.28762 0.28285 0.28285 0.26064 448 D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS Our next problem is associated with some of the fields having class number 2. Problem V. Find N = 5 (mod 8) with e¡ = -(-2/p¡) for allp¡ =- p. This implies that -2N is a quadratic nonresidue of all odd primes ig p. The solutions are given in Tables V and Va, as before, and note, that in this case, L2N(l) and L(l, x) are identical. The first two entries have ri(-8iV') = 2. Recently, Peter Weinberger [22] proved that h{-8N') exceeds 2 for all N' > 29. We also note that, for all p, hi-W) = 2 (mod 4). This follows from the fact that the only ambiguous form besides the principal form is (2, 0, N'), and this form is not in the principal genus since 2 is a quadratic nonresidue of N'. Therefore, the class number is a multiple of 2, but not of 4. Relative to Table IV, Table V is quite short since many of its least solutions are valid for a whole string of p¡,e.g., 123464393861is valid for six p¡,and then 1833287692469 is valid for six more. We do not know if this phenomenon is of significance, or merely a fluke. A number of these N'„—those for p = 5,29,101, and 157—have exceptionally small values of L2Np(l) for determinants of their size. We round out our choice of quadratic characters by returning to positive discriminants and examining the problem that complements Problem I and extends Problem III into the positive range. Problem VI. Find N = 5 (mod 8) with e¡ = -1, for all p¡ ^ p. The least prime residue of N will therefore exceed p. The least solutions are given in Table VI. Those for p = 43 — 53 were given earlier by N. Beeger and E. Karst [23]. As with Problem I, we have not completed a Table Via and merely show its beginning: p 3 5 7,11 13 17 19,23 29 31,37,41 h(Np) L(l,x) 2 0.29106 4 0.25762 h(N'p) 5 L(\,x) 0.43041 0.54002 0.39091 0.33144 0.26009 0.26045 0.29195 0.26510 In Table VI we have included 3D values of L(l, x) for each JV.These approximations were obtained by a program called SPEEDY that computes the partial products of (7) for p < 132000. It evaluates the needed Jacobi symbols by the Reciprocity Law, and requires only a few seconds on an IBM 7094 for each discriminant. While it is very difficult to bound the error of these partial products with a bound that is both realistic and mathematically sound, we know by comparison with many examples where L(l, x) is known exactly that usually these SPEEDY approximations are correct to 1 part in 1000. The very low value of L(l, x) for N'13) = 49107823133 is of 449 INTEGER SEQUENCES Table VI = -1 for all Pi^P, P 3 5 7,11 13 17 19,23 29 31-41 43 47 53 59 61 67 71 73 79 83 89,97 101,103 107-113 127 131 137, 139 149-163 iV = 8x + 5 Np L(l,x) 5 53 173 293 437=19-23 0.291 9173 24653= 89-277 0.258 74093 170957 214037= 193-1109 0.250 214037= 193-1109 0.250 214037= 1931109 0.250 2004917 44401013= 157-282809 0.212 94948157= 317-299521 0.226 154554077= 97-1593341 0.223 154554077= 97-1593341 0.223 163520117= 2027-80671 0.214 163520117= 2027-80671 0.214 261153653= 8191-31883 0.190 1728061733 9447241877 19553206613= 142211374953 0.177 49107823133 385995595277=19110711188677 0.174 N'p 5 53 173 293 2477 9173 61613 74093 170957 360293 679733 2004917 2004917 69009533 138473837 237536213 324266477 324266477 1728061733 1728061733 1728061733 9447241877 49107823133 49107823133 Unknown L(\,x) 0.430 0.540 0.391 0.331 0.260 0.260 0.292 0.265 0.246 0.224 0.223 0.205 0.205 0.209 0.233 0.224 0.227 0.227 0.194 0.194 0.194 0.181 0.169(5) 0.169(5) Unknown special interest. It is exceptionally small for a discriminant of this size, and appears to be even smaller than the 0.17009 value mentioned in Problem HI. These Table VI integers N have a pleasing property when considered as negative determinants. All negative determinants —N have ratios h{-4N)/jN that are asymptotically bounded as N -» oo by AN~e < h(-4N)/jN < AN +C for any positive e [24]. Our present N satisfy (-N/pi)= -(-I/Pi) (Pi^p) and therefore have q L^-c®F,q_{_m 450 D. H. LEHMER, EMMA LEHMER AND DANIEL SHANKS where the coefficient (P) 3 - 15 + 17 - 111 - Í "" P + (-1/P) converges to 7r/2 as p -» oo, cf. Euler, Landau [25]. These N, therefore, have class numbers h(-4N) approximately equal to JN by (14). But the convergence is, of course, quite slow : h(-4Ni3i) = 145644 = 1.042V/N131, h(-4N'13,) = 224546 = 1.013jN'l3i, rj(-4N149) = 592288 = 0.953jNi4g. There are obviously many similar problems that one can propose and solve with the Delay Line Sieve [2]. The DLS 127 is available to anyone with a suitable problem without charge. We are pleased to acknowledge the assistance of Richard Serafín in computing most of the class numbers. University of California Berkeley, California 94720 1180 Miller Avenue Berkeley, California 94708 Applied Mathematics Laboratory Naval Ship R&D Center Washington, D.C. 20007 1. W. H. Mills, "Characters with preassigned values," Cañad. J. Math., v. 15, 1962, pp. 169-171. MR 28 #71. 2. D. H. Lehmer, "An announcement v. 20, 1966,pp. 645-646. 3. Marshall 758-763. 4. Allan Hall, concerning the Delay Line Sieve DLS-127," Math. Comp., "Quadratic residues in factorization," Bull. Amer. Math. Soc, v. 39, 1933, pp. Cobham, The Recognition Problem for the Set of Perfect Squares, IBM Research Paper, R.C. 1704,April 26, 1966. 5. M. Kraitchik, Recherches sur la Théorie des Nombres. Vol. 1, Paris, 1924, pp. 41-46. 6. D. H. Lehmer, "The mechanical combination of linear forms," Amer. Math. Monthly, v. 35, 1928, pp. 114-121. 7. D. H. Lehmer, "A sieve problem on "pseudo-squares"," MTAC, v. 8, 1954, pp. 241-242. MR 16,113. 8. A. E. Western & J. C. P. Miller, Indices and Primitive Roots, Royal Soc. Math. Tables, v. 9, Cambridge Univ. Press, New York, 1968, p. xv. 9. Daniel Shanks, "Class number, a theory of factorization, and genera." (To appear.) 10. N. G. W. H. Beeger, "Report on some calculations of prime numbers," v. 20, 1939,pp. 48-50. MR 1, 65. Nieuw. Arch. Wiskde. 11. Luigi Poletti, "Atlante di centomila numen primi di ordine quadratic© entro cinque miliardi," 12. H. M. Stark, "A complete determination of the complex quadratic fields of class-number one," UMT 62, MTAC, v. 2, 1947,p. 354. Michigan Math. J., v. 14, 1967,pp. 1-27. MR 36 #5102. 13. D. H. Lehmer, "On the function X2 + X + A," Sphinx, v. 6, 1936, pp. 212 214; v. 7, 1937, p. 40; v. 9, 1939.pp. 83-85. 14. Mohan Lal & Daniel Shanks, "Class numbers and a high density of primes." (To appear.) 15. R. Ayoub, S. Chowla & H. Walum, "On sums involving quadratic characters," /. London Math. Soc, v. 42, 1967, pp. 152-154. MR 34 #4224. 16. Daniel Shanks, "Generalized Euler and class numbers," Math. Comp., v. 21, 1967, pp. 689-694. MR 36 #6343. 17. Daniel Shanks, "On the conjecture of Hardy & Littlewood concerning the number of primes of the form n1 + a," Math. Comp., v. 14, 1960, pp. 320-332. MR 22 # 10960. 18. Daniel Shanks,-"Supplementary data and remarks concerning a Hardy-Littlewood Math. Comp., v. 17, 1963, pp. 188-193. MR 28 #3013. conjecture," INTEGER SEQUENCES 451 19. Daniel Shanks, "On Gauss's class number problems," Math. Comp., v. 23, 1969, pp. 151-163. T. Ordman, "Tables of class numbers for negative prime discriminants," UMT 29, 20. Edward Math. Comp.,v. 23, 1969,p. 458. 21. Morris Newman, "Table of the class number h(-p) forp prime, p = 3 (mod 4), 101987 ápí 166807," UMT 50, Math. Comp., v. 23, 1969, p. 683. 22. Peter Weinberger, Dissertation, University of California, Berkeley, Calif., June, 1969. 23. Edgar Karst, "The congruence 2P~' = 1 (mod p2) and quadratic forms with high density of primes," Elem. Math., v. 22, 1967, pp. 85-88. MR 35 #6612. 24. C. L. Siegel, "Über die Classenzahl quadratischer Zahlkorper," Acta Arith., v. 1, 1935, pp. 83-86. 25. E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen. Bände 2, Chelsea, New York, 1953, §186, "Euler's Reihen," pp. 673-676. MR 16, 904.