Guide to Tables in the Theory of Numbers (1941)

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

I DESCRIPTIVE SURVEY F. THEORY OF NUMBERS a. PERFECT AND AMICABLE NUMBERS AND THEIR GENERALIZATIONS The number nis called perfect if it is equal to the sum of its proper divisors (i.e., divisors <«). Only 12 perfect numbers are known. These numbers are givenby2"-i(2n-l)for«=2,3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127. A list of these 12 numbers, written in the decimal system, has been given recently by TRAVERS 1. Chapter 1 of DICKSON 4 gives a very complete historical account of perfect numbers up to the year 1916 with many references to old lists of these numbers. ARCHIBALD 1 has given a complete up to date historico-bibliographic summary in tabular form. If we use <r(n) to denote the sum of all the divisors of« (including 1 and n), a perfect number is one for which <r(n) = 2n. In case <r(n)>2n the number n is called abundant. A list of all even abundant numbers <6232 is given in DICKSON 2 (Table III, p. 274-277). A rather special list of all primitive abun- dant numbers (i.e., numbers containing no abundant or perfect factors) with exactly four distinct prime factors of which the second in order of magnitude is 5, appears in DICKSON 3. If n is such that <r(«) = kn, then « is called multiply perfect and k is the index of perfection. Thus a perfect number has an index of 2. The first real table of multiply perfect numbers is due to CARMICHAEL 1, who gave a list of 47 such numbers including all < 109. Later CARMICHAEL AND MASON 1 ex- tended this list to 251 numbers. Further lists of such numbers of index k = 5, 6, and 7 appear in POULET 1. The most complete list to date is POULET 2, which gives 334 multiply perfect numbers with 3 ^ k ^ 8. Two numbers ni and «2 such that each is the sum of the proper divisors of the other, or in other words, such that <r(«i) = <r(«2) = «i+«2, are called ami- cable. Euler discovered 64 such pairs, which are tabulated in DICKSON 4. More recent lists are found in MASON 1 and in POULET 2 (p. 46-50), the latter con- taining 156 amicable pairs. A list of 21 new pairs, due to E. B. Escott, appears in POULET 5 together with a table of the distribution of amicable numbers < 1023. A set of k numbers «i, «2, • • • , «*, not necessarily distinct, and such that (7(«i) = o-(«2) = • • • = <r(«*) = «i + «»+•••+«* is called a set of multiply amicable numbers of index k. Lists of such sets of num- [5]

a-bi DESCRIPTIVE SURVEY bers with 2 ^k^ 6 are found in MASON 1, while many more for the same range of k are given in POULET 2. A series of numbers ni, th, • • • each term of which is the sum of the proper divisors of the preceding term is called an aliquot series with leader ni. The ques- tion of whether there exists an unbounded aliquot series is at present unan- swered. DICKSON 2 has considered all aliquot series with leaders < 1000. Table I (p. 267-272) gives most of these series complete. 13 incomplete series are given in Table II (p. 272-274). These are corrected and extended or completed in POULET 2 (p. 68-72) and POULET 3 (p. 188). The longest completed series has 138 as a leader and contains 178 terms. In Table IV of DICKSON 2 (p. 278-290) the first few terms of aliquot series with leaders <6232 are given; in each case enough of the series is given to be sure it is not periodic with a period ^ 6. If an aliquot series is purely periodic with proper period k then the k distinct members of the series are called sociable numbers of index k. Perfect and amicable numbers correspond to k= 1 and 2. POULET 2 (p. 68) has discovered two sets of sociable numbers with in- dices 5 and 28 and with leaders 12496 and 14316 respectively. Tables for facilitating the investigation of perfect, abundant, and amicable numbers, and their generalizations are described under b2 (sum and number of divisors, and allied functions). b. NUMERICAL FUNCTIONS bi. Eider's totient function and its inverse, sum, and generalizations There are but two tables of Euler's totient function </>(«), defined as the number of numbers not exceeding n and prime to n. These are SYLVESTER 2 in which <t>(n) is given for «< 1000 and J. W. L. GLAISHER 27, where (in Table I) the function is tabulated to «=10000. The fact that there are only two tables of this fundamental function may be accounted for by the simple for- mula for <t>(n), by means of which isolated values of <t> may be quickly found, once the factorization of n into its prime factors is known, namely: *(P*iP? •••/>"') = pT~\pi ~ 1)pr~i(P* -!)••• pr~\pt - 1). Both tables were in fact constructed with a view to obtaining numerical data for the less simple functions, the sum and inverse of <t>. There are several small tables of the inverse of <t> giving all n's for which <t>(n) has a given value. For #(«) ^ 100 we may cite LUCAS 5, and KRAITCHIK 4. These also give the number of n's in each case. Two much larger tables exist: CARMICHAEL 2, which extends to #(«)=1000, and J. W. L. GLAISHER 27, where Table II gives all n's up to 0(«) = 2500. A manuscript table of MILLER 1 gives odd solutions n of <t>(n) = N for all possible N ^ 10 000 and was used to verify Glaisher's Table II. The sum function [6]

DESCRIPTIVE SURVEY bi " 3«2 <!>(«) = 2_, <t>(") — h 0(« log «) i— i it has been the subject of numerous papers. A table of *(«) for «^ 100 together with (for comparison purposes) the nearest integer to 3«2/*•2 is given in PEROTT 1. A more extensive table is SYLVESTER 2, which tabulates $(«) up to «= 1000 together with 3«2/?r2, correct to the second decimal place. SARMA 1 has tabulated *(«) for « = 300(50)800 and for 820, and gives for the same values of n the error function £(»)-*(*)-—, T2 which he states is positive for n^ 1000 except for «=820. Values of *(«) and 3«2/7r2 for n= 1000(1000)10 000 are given in GLAISHER 27. Isolated values of #(«), at least for «^ 500 000, are most easily calculated by means of the formula r-i \L V J L " J ! where the values of the Mobius function ju(«) may be taken from MERTENS 1, and its sum function M(x) = £ M(") may be taken from the tables of STERNECK 1, 2. A function ^(n), similar to Euler's <t>(n), which may be defined as the least common multiple of the factors occurring in the above product for #(«) or as the least positive exponent k for which the congruence xk = 1( mod «) holds for all x prime to n, has important applications in the theory of the bi- nomial congruence. CAUCHY 1, 2 contain tables of $(n) for «^l00 and for «±£ 1000 respectively, while MOREAU 1 has a table of the inverse of ^(«) giving all values of n below 1000 (and in most cases many larger values also) for which \f>(n) has a given value g 100. Another special table dealing with the numbers less than and prime to n is due to BACKLUND 1, and gives the frequency of a fixed difference between consecutive members of the set of integers prime to « = 2-3-5 • • • p, for IgrgS. Thus for r = 6, we find that among the <t>(2-3-5- 7-11-13) = #(30030) = 5760 numbers less than and prime to 30030 there are precisely 1690 consecu- tive ones differing by 6. Lists of the actual numbers ^ « and prime to « are given for every «^ 120 in CRELLE 3. [7]

bi-b» DESCRIPTIVE SURVEY If all irreducible fractions between 0 and 1 whose denominators do not exceed N be arranged in increasing order the resulting sequence of &(N) frac- tions is called the Farey series of order N. GOODWYN 1, 2 give the Farey series of orders 100 and 1000 respectively. The Farey series of order N less than 100 or 1000 may be read directly from the corresponding table simply by omitting those fractions whose denominators exceed N. b2. Sum and number of divisors, and allied functions There exists only one large table of the sum <r(n) and the number v(n) of divisors of n (including 1 and n). These functions are given in Table I of GLAISHER 27 for all n up to 10 000. A table of <r(n) for «^ 100 is in GLAISHER 17, where the function is denoted by $(n). Table III of GLAISHER 27 gives all values of n^ 10 000 for which v(n) has a given value, while Table IV gives for each possible value of <r(ri) ^ 10 000 all those «'s for which <r(ii) has this value. DICKSON 2 has published a somewhat similar inverse table of o- extending only as far as «= 1600. These inverse tables are useful in finding multiply perfect numbers, amicable numbers, etc. Another kind of table useful in this con- nection gives the decomposition into prime factors of the values of <r(p") = (P"+i—l)/(p—1)> two examples of which are EULER 1 and KRAITCHIK 7. The former table extends for each prime p as far as a = r" as follows: p 2 3 5 7 11 13 17 19 23 29g/><1000 f" 36 15 9 10 9 7 5 5 4 3 The latter table extends for each p< 1000 over a = 2, 3, 4, 5, 6, 8, 10, 12 and for p< 100 (and for several larger primes) over a=7, 9, 14, 15, 16, 18, 20, 24, and 30. In connection with the function v there is the concept due to Ramanujan of a highly composite number, that is, a number which has more divisors than any smaller number. A list of the first 103 highly composite numbers extending as far as 6 746 3%28 388 800, which is the first number to have as many as 10080 divisors, is given in RAMANUJAN 1. Glaisher has given several tables of numerical functions which depend upon the difference between the number of divisors of n of one specified form, and the number of divisors of n of another specified form. These functions occur naturally in the series expansion of certain elliptic functions and are also con- nected with the number of representations of integers by certain binary quad- ratic forms. The function of this kind most frequently met with is E(n), the difference between the number of divisors of n of the form 4£+1, and the number of those of the form 4£+3. Tables of E(n) are given in GLAISHER 17, p. 164-165 to «=100, in GLAISHER 15, to «=1000. In GLAISHER 18, and in GLAISHER 19, the function £(12«+l) is given for n^ 100. The function H(n) denoting the excess of the number of 3£+l divisors of n over the number of 3£+2 divisors is tabulated in GLAISHER 19 to «=100, and in GLAISHER 24, [8]

DESCRIPTIVE SURVEY b2-ba to «=1000. The function J(n) denoting the excess of the number of 8£+l and 8£+3 divisors of « over the number of 8£ + 5 and 8£ + 7 divisors is tabu- lated for «g 1000 in GLAISHER 25. The function E^(n) denoting the excess of the sum of the squares of the 4£+1 divisors of n over the sum of the squares of the 4£+3 divisors is given for n^ 100 in GLAISHER 17. The sum of the first n values of the above functions has been given by Glaisher as follows: function range of fi asymptotic formula reference £ a(k) «= 1000(1000)10 000 «V/12 GLAISHER 27, p. viii t-i f>(4) «= 1000(1000)10 000 « log «+(2C-l)« GLAISHER 26, p. 42 t-i «= 100(100)1000(1000)10 000 «r/4 GLAISHER 26, p. 193 «= 100(100)1000(1000)10 000 HT/3V3 GLAISHEH 26, p. 204 «= 100(100)1000 »w/2\/2 GLAISHER 26, p. 213 *-i In each case the values are compared with the corresponding asymptotic for- mula. For a table of all the divisors of each number up to 10 000 see ANJEMA 1. bs. Mdbius' inversion function and Us sum The function n(n) defined for positive integers « by M(l) = 1, v(p) = ~ 1, M(/>") =0 for a > 1 n(mn) = n(ni)n(ri) (m and « coprime), plays a very fundamental role in the theory of numerical functions, and has the value +1 or — 1 if n is a product of an even or odd number of distinct primes, but vanishes for all other numbers n> 1. This function is so easy to evaluate for isolated numbers whose factors are known that tables of j*(«) are rare and were constructed to study the behavior of a more complicated allied function. GRAM 1 gives n(n) together with the sum Sn=^ll.in(k)k-i for «^300. This was published before Euler's conjecture that Sn—>0 as «—> w had been rigor- ously proved. MERTENS 1 contains a table of /*(«) and of the sum M (n) =2Xi/*(*) for «<10 000. STERNECK 1 tabulates M(n) for all «<150 000, while in STERNECK 2, M(n) is given for n= 150 000 (50) 500 000. Finally in STERNECK 4, 5 a table of M (n) is given for 16 values ranging from 600 000 to 5 000 000. These tables were computed with the hope of shedding some light on the still unsolved problem of the order of magnitude of M(x), a problem intimately connected with the Riemann hypothesis. These tables, however, may also be used to advantage in computing other sum functions, as indicated [9]

bs-b« DESCRIPTIVE SURVEY above in connection with <£(«). A list of numbers <104 which are primes or products of distinct primes is given in boldface type in Table III of GLAISHER 27. These are arranged, in increasing order, into sets according as n is a prod- uct of 1, 2, 3, 4 or 5 distinct primes. This list is useful in evaluating and invert- ing series involving /*(«)• b,|. The quotients of Fermat and Wilson The integer qa=(a"~i—l)/p, where p is a prime, is known as Fermat's quotient and occurs in several branches of the theory of numbers. Its connec- tion with the so-called first case of Fermat's last theorem, which dates from 1909, accounts for most of the tables of qa. MEISSNER 1 tabulated q* modulo p for /><2000. This table was extended from 2000 to 3697 by BEEGER 3t who discovered a second example p = 3511 of 92=0 (mod p), the first being p= 1093. The table of HAUSSNER 2 gives qi (mod p) for p^ 10 009. BEEGER 4 extended his table from 3697 to 13999, and recently this high limit has been raised to p< 16 000 in BEEGER 8. Extensive tables for qa exist only for a = 2. HAUSSNER 3 gives a table of all known cases of ya = 0 (mod p) in which a<p. Tables such as MEISSNER 2, BEEGER 1, and CUNNINGHAM 5 which give all solutions x of xp~i^l (mod p*) are described under d4 (solutions of special binomial con- gruences). The integer w"= [(/>—!) !+1]//>, where p is a prime, is known as Wilson's quotient. Only two small tables of w" (mod p) exist, namely BEEGER 2, for p<300, and E. LEHMER 1, for ^211. The congruence w" = 0 (mod p) has only two known solutions p = 5, 13. b6. Sums of products of consecutive integers Two tables may be cited in this connection: GLAISHER 23 which gives the sums of products,£at a time, of the integers 1, 2, 3, • • • , «for all k<n and for «<22, and MORITZ 1 which gives the sums of products k at a time of the in- tegers m+l, m+2, • • • , wt+«ior0^wt^10, I^«gl2and lg*^ 12. Tables of the sums of like powers of 1, 2, • • • , n, as well as tables of Bernoulli num- bers and polynomials, will be cited and described in another report of this Committee, Section I. be. Numerical recurring series There are a number of recurring series which have been computed to a great many terms, in particular LAISANT 1, in which the Fibonacci series «n(0, 1, 1, 2, 3, 5, • • • ) and its associated series »„ = **!„/«„ are both tabulated up to n= 120. In most cases these series are rather special and were computed for factorization purposes. These will be described under e2, but may be cited as follows: HALL 1, LAISANT 1, D. H. LEHMER 2, KRAITCHIK 4, LUCAS 1, POULET 3. [10]

DESCRIPTIVE SURVEY br-c b?. Triangular numbers There are three tables of triangular numbers «(«+l)/2. The earliest and most extensive is JONCOURT 1, which gives the first 20 000 triangular numbers. KAUSLER 1 has a table of the first 1000 triangular numbers, with their doubles and their halves whenever these latter numbers are integers. More recently BARBETTE 1 has given the first 5000 triangular numbers. Figurate numbers of higher order, namely n(n+ l)(« + 2)--. («+*- I)/*!- are essentially binomial coefficients, tables of which numbers will be cited and described in another report, Section I, of this Committee. c. PERIODIC DECIMALS Although tables for the conversion of ordinary fractions into decimals be- long properly to another report of this Committee, Section A, there are a few such tables which are of number-theoretic interest inasmuch as they give in each case the complete period of the repeating decimal. Perhaps the best known table of this sort is due to GAUSS 5, and was in- tended for use (according to the title) in finding the complete period of the repeating decimal for P/Q, where Q< 1000. Strictly speaking this is true only for Q<467 but the table is also available for an unlimited number of other fractions. We can, of course, suppose that P<Q and prime to Q and by partial fractions we may express P/Q by pi"i p*"l pk"k where Q=P"'p? • • • />?*, the p's being distinct primes, and the P's being in- tegers. Hence we need consider only fractions of the form P/Q, where Q is a prime or a power of a prime 7* 2 or 5. Therefore we set Q = p", <t> — <t>(Q) = P"~i(p—l) = e-f, where e is the exponent of 10 and / its residue-index (mod P"). Let g be any primitive root of p" so that g'= 10 (mod p"). Then if P=gi (mod p") we can write j = kf + v (0 ^ k < e, 0 g v < /). Then (mod />-), which shows that P and g' have essentially the same decimal expression, or in other words it suffices to tabulate the/ really distinct periodic decimals corre- sponding to the/ fractions 1 g I2 g'~i — , — , — , . . . , - . P" P" P" P" [11]

c-d DESCRIPTIVE SURVEY In particular if 10 happens to be a primitive root of p" there is only one period to give. Such a table is given in GAUSS 5 for />"<467. For 467g/>"< 1000 only the periods for l/p" are given. The primitive roots used for each p" are given on page 420. In actual practice it is seldom necessary to anticipate which of the/ fundamental decimal periods corresponds to a given P/p", since after the first few digits are determined this can be recognized from the table. There are three other tables similar to GAUSS 5. In fact this table is an ex- tension of an earlier one for p< 100 given in GAUSS 1. Another table for p^347 due to Hoiiel is given in LEBESGUE 2 and is reproduced in HOUEL 1. Another and more complete set of tables which serve the same purpose more expeditiously is due to Goodwyn. In GOODWYN 3 are given the possible periods of every fraction P/Q with Q^1024, while the possible non-periodic part of the decimal (if any) may be read from GOODWYN 2. GOODWYN 1 con- tains the same material as GOODWYN 2, 3 but is limited to fractions with de- nominators <100. These rare tables are described in greatest detail in GLAISHER 4. Tables giving a complete period when a rational fraction is converted into a "decimal" in a scale of notation different from 10 are as follows: BELLAvms 1 has given a tablei similar to GAUSS 5 for />^383 but with the base 2 instead of 10. CUNNINGHAM 12 gives the complete period of l/n for base 2, for «< 100, while CUNNINGHAM 18 contains a table of the same extent for the bases 3 and 5. d. THE BINOMIAL CONGRUENCE The congruence x"—a=0 (mod m) is the subject of a great many tables many of which can be classified in several ways. The case « = 2 is not consid- ered here but is discussed under i. There is, of course, an intimate connection between the binomial congruence and the binomial equation xn — a = 0, espe- cially when a= 1. Tables having to do with this equation are treated under o. Every solution * of the binomial congruence gives a factor m of the number x"—a. Hence tables of factors of x"—a or even xn — ayn, which are described under 62, give, indirectly, solutions of the binomial congruence. It is difficult to give an orderly description of the tables relating to the binomial congruence without making some conventions as regards nomencla- ture and notation. Thus the real integer x (if it exists) will be called the base, n will be called the index of a for the base x modulo m, and a will be called an «th power residue of m, and we shall write (a/«t)"= 1 to indicate that x exists. The term solution of a binomial congruence will be reserved to denote the re- i To save space such a decimal as 1/25 = .00001010001111010111* 00001010001111 • • • is written simply 41113, thus indicating that the first half of the period (to the left of the star) begins with 4 zeros, followed by 1 one, 1 zero, etc. The second half of the period is complementary to the first. [12]

DESCRIPTIVE SURVEY d-di suit of solving the congruence for the unknown base. The modulus m is almost always a prime or a power of a prime, and when a table extends to all such moduli not exceeding L we shall write p"^L, where it will be understood that When o=l, the following nomenclature will be used. If n = e is the least positive number for which xn=l (mod p), then for brevity e is called the ex- ponent of x (mod p).i The integer /= (p— l)/e is called the residue-index of x (mod p), (after Cunningham), and is found more frequently than e in tables on account of its small average size. Moreover, if /= 5 for instance, then, by Euler's criterion, a; is a fifth (but not higher) power-residue (mod p). Hence tables of / give indirectly, by setting /= k, 2k, 3k, • • • , a list of those primes which have x as a kth power-residue, or a list of those x's which are kth power residues of a given prime. Those numbers x (positive or negative) for which /"= 1 are called primitive roots of p. di. Primitive roots There are <l>(p— 1) incongruent primitive roots of p. The fact that there are so many primitive roots causes no difficulty in the theory of the binomial congruence but has caused considerable confusion in the tabulation of primi- tive roots. There are only four tables giving the full set of primitive roots of p. These are OSTROGRADSKY 1, for p< 200, reproduced in CHEBYSHEV 2, CAHEN 1, and GRAVE 3, and extended in CHEBYSHEV 2t, to p^353; CRELLE 1 for p^ 101, except f or p = 7 1 , and KULIK 2, where 103 ^ p g 349. In most applications it is sufficient to know only one primitive root of p. All the others, if need be, may be generated from a single one by finding the residues of g\ gr', • • • , gT* (mod p) where n, TI, • • • , T> are the <t>(p— 1) numbers less than and prime to p—l. For /><1000 the Canon Arithmetic™, JACOBI 2, gives these various powers. For this reason authors of extensive tables of primitive roots have been con- tent to give only one or sometimes two primitive roots for each p. A confusion exists, however, as to which root should be given, some authors giving always the least positive root, some the absolutely least root, some both, but fre- quently any convenient root, especially + 10 when possible. It is often pointed out that primitive roots with small absolute values, especially + 10, are easier to raise to high powers (an operation which is most frequently met with) than large roots. When p is quite large however this argument now-a-days has less weight, for in this case it is not a question of computing |* by successive multi- plications by g, but of calculating |* for isolated values of k. This is best done by a computing machine writing k to the base 2 and using the method of i Reuschle (1856) and, more recently, Cunningham use the terminology "e is the hauptexpo- nent of x." This, and the above nomenclature is somewhat opposed to the older and more lengthy "e is the exponent to which x belongs," in which e is thought of as possessing x. [13]

DESCRIPTIVE SURVEY successive squarings modulo p in which case one soon loses sight of the original root g. Perhaps the best reasons for insisting on least positive primitive roots are 1) that this permits the collating of tables of primitive roots, and 2) that there is considerable theoretical interest in the question of the distribution of primes with large least primitive roots. The following is a tabular description of the 20 extensive tables of primitive roots arranged according to the highest value of p tabulated. Tables of Primitive Roots reference range of t factorization olp-i type of root indication that i0 is a root JACOBI 2 1-1000 yes 3 y* WERTHEIM 1 1-1000 no 1 vcs KULIK 2 1-1009 no 1 no WERTHEIM 2 1-3000 yet 1 yet CAHEN 3 200-3000 no 1 yet WERTHEIM 3 3000-3500 yet 1 no KORKIN 1 1^000 yes 3 no REUSCHLE 1 1-5000 yet 1,3 no WERTHEIM 4 3000-5000 yet 1 yes POSSE 1 4000-5000 yet 3 no POSSE 3 1-5000 yet 3 no WERTHEIM 5 1-6200 no 1 yet DESMAREST 1 1-10 000 no 3 no> POSSE 2 5000-10 000 ygi 2 no POSSE 4 5000-10 000 yet 2 no GOLDBERG 2 1-10 160 1 KRAITCHIK 1 1-25 000 no 3 no /CUNNINGHAM 1-25 409 no 1,1' no \WOODALL and CREAK 1 f CUNNINGHAM 1-25 409 yet 1,1' no \WOODALL and CREAK 2 /KRAITCHIK 4 1-27 457 no 3 no Up. 131-145) i Yes on page 308. The majority of tables give the factorization of p— 1 into powers of primes, information essential to the application of primitive roots to the binomial congruence. Whether or not this is given in a particular table is indicated in the center column above. The types of roots tabulated are as follows: 1. least positive primitive root 1'. greatest negative primitive root 2. absolutely least root 3. some primitive root usually not exceeding 10 in absolute value modulo p. REUSCHLE 1 gives the type 1 root for p< 1000 and one or two roots of type 3 beyond 1000. CUNNINGHAM, WOODALL and CREAK 1, 2 give both 1 and 1' for each p. These tables are perhaps the most reliable of all. The authors also give interesting data on the frequencies of least positive and greatest negative roots. Some tables give an indication whether or not 10 is a primitive root of p. Thus JACOBI 2 bases each table of his Canon Arithmeticus (described under ds) [14]

DESCRIPTIVE SURVEY di -d; on the primitive root 10 whenever it exists. Other tables, as indicated in the last column of the above tabular description, mark with an asterisk the primes having 10 as a primitive root. Although this is not done in KRAITCHIK 4 (p. 131-145), he gives a separate list (p. 61) of the 467 primes < 10 000 of which 10 is a primitive root. On p. 55-58 are given lists of those primes < 10 000 whose least positive primitive root has a given value, and also the number of such primes. A more extensive table of the number of primes whose least positive and greatest negative primitive root have a given value is given in CUNNING- HAM, WOODALL and CREAK 1, for p£ 25 409. It is remarkable that primes have such small primitive roots,i and this fact has been of great assistance in the preparation of tables described above. d2. Exponents and residue-indices Interest in the exponent of x modulo p first arose in the special case of *= 10. It was observed that for p j* 2 or 5 the length of the period of the circu- lating decimal representing l/p was a certain unpredictable factor e of p — 1, and that the number 10*— 1 was divisible by p if and only if k was divisible by e, long before it was realized that these phenomena form only a part of a general theory of the binomial congruence (in which the base 10 is in no way peculiar), and in terms of which they are best described and investigated. As this bit of history has repeated itself in the case of countless individuals who have approached the theory of numbers from an interest in circulating deci- mals, we shall consider first the tables devoted to exponents of 10. The earliest table is due to BURCKHARDT 1 who completed the last page of his factor table with a table of exponents of 10 for /><2550, and 22 larger primes. This table was reproduced with certain corrections by JACOBI 2 who used it in constructing his Canon Arithmeticus. Tables of exponents and resi- due-indices of 10 for various ranges of p may be given the following tabular description. reference range of modulus exponent residue-index BURCKHARDT 1 p<2S5Q yes no DESMAREST 1 p<\0 000 no yes REUSCHLE 2 /><15 000 yw yes SHANKS 1 p<20 000 ye* no KRAITCHIK 1 p<25 000 yw no f CUNNINGHAM / />"<10000 yes yes \WOODALL AND CREAK 1 \10000<^25 409 BO yes SHANKS 3 20000</><30 000 yet no KRAITCHIK 4 (p. 131-145) />g27 457 no yes SBORK 1 /><100 000 no yes if >2 HERTZER 1 100000</><112 400 no yes if >2 SHANKS 4 30000</><120 000 yes no Tables of Exponents and Residue-indices of 10 i All but 163 out of the 2800 primes under 25 410 have 2S«S12. The smallest prime known to have its least positive primitive root £71 is />=48 473 881. 1 This table is due to F. Kessler. [I5]

d2 DESCRIPTIVE SURVEY A short table for composite as well as prime moduli (based on GOODWYN 3) has been given by GLAISHER 4. This has for argument every number q^ 1024 and prime to 10, and gives the exponent e of 10 modulo q as well as <t>(q) and <l>(q)/e, where <t> is Euler's totient function. Tables of exponents and residue-indices of 2 may be tabulated in like man- ner as follows: Tables of Exponents and Residue-indices of 2 reference range of modulus exponent residue-index CUNNINGHAM 4 />"<1000 yes yes 'MEISSNER! /><2000 no yes 'BEEGER3 2000 < p < 3700 no yes REUSCHLE 1 £<5000 yes yes iHAUSSNER2 />g!0009 no yes 'BEEGER4 3700</><14000 no yes 'BEEGER8 14000 <p< 16 000 no yes KRAITCHIK 1 p<25 000 yes no I CUNNINGHAM f p"<lO 000 yes yes \WOODALL and CREAK 1 \ 10000 </>S 25 409 no yes CUNNINGHAM and WOODALL 7 /><100 000 no yes if > 2 KRAITCHIK 4 (p. 131-191) p< 300 000 no yes There are four tables of Kraitchik which give residue-indices of 2 for primes of special forms up to high limits as follows: KRAITCHIK 4, p. 53 p = k2n+l, 3^£^99 (odd), 22^«g36, and 2 108</><10i2 KRAITCHIK 4, p. 192-204 p = 512k+l<l01 KRAITCHIK 6, p. 233-235 p=k2"+l, 10"</><10i2, £<1000. Tables of exponents and residue-indices of other bases are less numerous and less extensive and give this information for several bases at once. They may be described as follows: reference bases range of modulus exponent* residue-indices REUSCHLE 1 3,5,6,7 /><1000 yes yes KRAITCHIK 4 (p. 65) 2,3,5,10 /><1000 no yes f CUNNINGHAM f2, 3, 5,6, 7 f p"< 10000 yes yes \WooDALLandCREAKl \10,11,12 \ 10000 <p£ 25409 no yes Another special table of CUNNINGHAM and WOODALL 1 gives for />^3001 the least positive a for which 10° 2*+ 1=0 (mod p) has a root x, and also the least such .-•. Two, more elaborate tables, of the same type, are given in CUNNINGHAM, WOODALL and CREAK 1. These give for each p"< 10 000, and for each of the four values y = 3, 5, 7, and 11, a set of three numbers (xQ, OQ, xQ ) satisfying (for a certain choice of signs +) the two congruences _ t" = + ya>, tx'y"> +1=0 (mod />"), _ i These tables give residue-indices as incidental data. The residue-indices were obtained from the other tables in this list. [16]

DESCRIPTIVE SURVEY d2-d3 where «o is the least possible such number for which xo and x£ exist, and where *o and *o are also as small as possible. In the first table (p. 33-64), t = 2, while in the second (p. 65-96), t= 10. These tables were used by the authors for find- ing exponents of y (mod p) from the known cases y= 2 and y= 10. There exist also two small tables of KRAITCHIK 4 (p. 63-65), which give the least positive number .r for which 2*=h (mod p) for all p< 1000 for which such an x exists, together with a list of all p < 1000 for which no such x exists. The first table deals with h = 3, and the second with h = 5. An analogue of the series of numbers a"— 1 (« = 0, 1, 2, • • • ) is the Fibonacci series 0, 1, 1, 2, 3, 5, 8, 13, - • • defined by «„ = wn-i + «„-,, «0 = 0, MI = 1. Corresponding to the exponent of a (mod p) we may define, after Lucas, the rank of apparition of p as the least positive value e' of n for which «" = 0 (mod p). Except for p = 5, e' is a certain divisor of p+l (more precisely p—(5/p}), and the quotient/'=(/>+ l)/e' is the counterpart of the residue- index. KRAITCHIK 4 (p. 55) gives, for each /><1000, the corresponding value of/'. An inverse table giving those p's for which the exponent of a (mod />) has a given value e, would be a table of so-called primitive factors of a'— 1. Such tables are discussed under e2. A similar table in which the residue-index/is given would be a table of those p's of which a is an exact/th power residue. Such tables are described under d6. da. Powers and indices If g is a primitive root of p then the p— 1 successive powers 00 pi .2 . . . oP-2 5 I 6 > 6 ' > 6 taken modulo /> are congruent, in some order, to the numbers 1, 2, 3, • • • ,p- 1. A table for a fixed prime p of powers of a primitive root g giving for each number i, 0^i^p — 2, the least positive number « for which g' = n (mod />) may be thought of as similar to a table of the exponential function f. An in- verse table, giving for each number «^0 (mod p) that index t=Ind,,« (mod />—1) for which the above congruence holds, would correspond to a table of natural logarithms, and can be used, as suggested by GAUSS 1 who published such a table of indices for each prime p< 100, in precisely the same way as a [17]

di DESCRIPTIVE SURVEY logarithm table for finding products, quotients, powers and roots modulo p. There is one practical difference, however, between a table of logarithms and a table of indices; the logarithm table can be used inversely to find anti-loga- rithms with perfect ease because log a: is a strictly increasing function of x, whereas a table of Ind n (mod p— 1) for «= 1, 2, 3, • • • , p— 2 has its values scattered in such confusion that, except when p is small, there may be some diffi- culty in finding the value of n (mod p) corresponding to a given value of Ind « (mod />—!). It therefore adds considerably to the effectiveness of a table of indices to print a companion inverse table of powers of g (mod p). This ap- pears to have been done first by OSTROGRADSKY 1 for all primes <200 in 1837-8. This table has been reproduced in CHEBYSHEV 2 and GRAVE 3, and extended to /> = 353 in CHEBYSHEV 26. CAHEN 3 has reproduced the table for p<200 from Chebyshev but has introduced many new errors. An entirely independent calculation of a set of tables of similar extent (including also powers of primes <200) was made by HOUEL 1, who based his table on absolutely least primitive roots. This table was first printed in LEBESGUE 2 in 1864. Two years after the appearance of Ostrogradsky's work, JACOBI 2 published his monumental Canon Arithmetic™, which extends to />°<1000. The part for p<200 was reproduced from OSTROGRADSKY 1. Following Ostrogradsky, Jacobi uses the primitive root +10 whenever possible, otherwise usually a primitive root whose square, cube, or other low power is congruent to ± 10 (mod />). This exceedingly useful table is still in print after 100 years. A small table for moduli p" and 2p" < 100 appears in WERTHEIM 5. Another table for p< 100 appears in USPENSKY and HEASLET 1. A somewhat similar table entitled A Binary Canon has been given by CUNNINGHAM 4. This gives for each p" < 1000 a pair of tables, one giving values of 2* (mod p"), and the other giving, inversely, whenever it exists, that value of i<p"~i (p— 1) for which 2' has a given value (mod p"). For such moduli p" as have 2 for a primitive root this pair of tables is equivalent for most purposes to the corresponding pair in Canon Arithmeticus. For the other moduli the tables are smaller or have blank entries since not all the powers of 2 will be distinct, and certain indices are necessarily non-existent. This table is intended chiefly for studying the binomial congruence with base 2. The Canon Arithmeticus may be said to have reduced any problem to which it is applicable to at most a simple pencil and paper calculation. The question of extending the Canon to, say, p < 10000 is one which presents certain practical difficulties. If the original form were preserved it would occupy several thou- sand pages. With modern computing machines in use, however, such an ex- tensive table is really unnecessary. In fact, as remarked above, the problem of finding gk for an isolated value of k (mod />) is one that presents very little difficulty. This means that we may dispense with that half of the Canon com- prising the tables giving powers of g. The remaining tables of indices of all [18]

DESCRIPTIVE SURVEY numbers <p may now be condensed by listing only indices of primes since we have the multiplicative relation Ind (mn) = Ind («) + Ind (m) (mod p — 1). Finally if q is a rather large prime then by use of one of the relations Ind (q) = Ind (q + p) = Ind (q ± 2p) • • • (mod p - 1) one soon finds a number q + kp all of whose prime factors are rather small. Hence we may tabulate only the indices of rather small primes. A similar condensation is possible for the modulus p" («>1). A table based on such a scheme has been published in KRAITCHIK 4 (p. 216-267), which gives for each modulus p"< 10000 the indices of all primes <100. This is an extension of a previous table KRAITCHIK 3 giving for p" < 1000 the indices of every prime <50. KRAITCHIK 4 (p. 69-70) has also a table of the indices of odd primes ^37 for moduli 2", n^20, and 5", «^16. Tables giving powers but not indices are either of a small extent or else are of rather special types. There is the table of KULIK 2 which gives for each p ?£ 349 all powers (modulo p) of the least primitive root. This table is described in the introduction as extending to p= 1009 but its publication was abruptly discontinued in the middle of the table for /> = 353. A small table giving all powers of all numbers (modulo p) is due to BUTTEL 1 . It extends as far as p = 29. LEVANEN 1 constructed a table giving for each wi<200 and prime to 10 the absolutely least value (mod m) of 10" for « = 0, 1, • • • , e/2, where e is the exponent of 10 (mod m). CUNNINGHAM 11 has given for each /><100 and for some much higher primes the values (modulo p) of the f unctions En= 2 2", 2B*, 33", 56" for all values of «. The primitive root tables of KORKIN 1 and POSSE 1, 2, 3, 4 described under di give for each prime in the range considered certain powers of a primitive root modulo p. The notation for the various powers tabulated is as follows f = p("~i)/21, /' = g(p~i)/2*, f" = g(p~i)/24, • • • z = g"-, z = U = o<P-»/« «' = g<P-i>/«* «" = o(p-i>/«' . . . O " O " ' O ' where q is a prime factor >3 of p— 1. d4. Solutions of special binomial congruences Tables of powers and indices of a primitive root (described under ds) such as JACOBI 2 serve to solve the general binomial congruence (1) xn = r (mod p). In fact, armed with such a table, this congruence may be replaced by the equivalent linear congruence [19]

d4 DESCRIPTIVE SURVEY « Ind, x = Inda r (mod p — 1). In spite of the availability of this general method, there exist many tables giving explicit solutions of binomial congruences of more or less special type, partly for the same reason that, in spite of the existence of tables of logarithms, there are numerous tables of square and cube roots, and partly because such tables have in most cases some important connection with the problem of factorization, a fact which accounts for the many extremely special tables de- scribed in what follows. There is in fact only one table giving explicit solutions of the general con- gruence (1), and this table is very limited. It appears in CRELLE 1, and is re- produced in CRELLE 2, and gives for each n all solutions x (mod p), if any, of xn ss r (mod p) 1 £ r £ p — 1, p ^ 101. The degree n ranges over all integers <p in case p<3l, but for 31^/>?£ 101, n assumes only those values which are prime factors of p— 1. Tables of solutions of the more specialized congruence x" = 1 (mod p") are more numerous and extensive. REUSCHLE 3 contains tables of solutions of this congruence with a= 1, p< 1000, and n^ 100, besides «= 105, 120, and 128. There is a table for each value of n giving only the #(«) "primitive" solutions of the congruence for each /> = £«+1< 1000. The « — $(«) imprimi- tive solutions can be taken, if need be, from the tables corresponding to the several divisors of n. Similar tables with a= 1 and 2 (and for small p's, many higher values of a) have been given in CUNNINGHAM 5. However, these extend only to p^ 101. A more extensive table is due to CUNNINGHAM and CREAK 1. This is arranged according to p" and extends to p"<l0 000. For each such modulus p" there is given the least positive solution x of xn=l (mod />"), where n runs through the divisors of <t> = p"~i (p—1) with the exception of the trivial cases «= 1, and n = <t>. The other solutions can be found if necessary by taking successive powers (mod p") of the tabulated solutions. Cunningham's Binomial Factorisations (CUNNINGHAM 28-34, 38, 39), 9 volumes of which have appeared, contain extensive tables of the <t>(n) primi- tive solutions of *"=! (mod p") for />"<100 000 and for numbers « from 3 to 17 and their doubles. Various smaller tables are given in which p"< 10 000 (in some cases 50 000) for the odd numbers «<50 and their doubles, and also for a few higher composite values of «. The more extensive tables for a fixed n are not confined to one volume but are distributed over three or four volumes as indicated below. The sequence of prime arguments in the tables is often interrupted to insert a sequence of prime power arguments. On the whole the arrangement leaves something to be desired. The following scheme gives some account of what values of n are considered in the various volumes. [20]

DESCRIPTIVE SURVEY values of « volume numbers 4, 8, 16, 32: 3, 6, 12, 24: • • • 1, 4, 8. 5, 10, 15, 20, • • • 2, 6, 8, 9. 7, 14, 21, • • • : 9, 18, 27, • • • 3, 7, 8, 9. 11, 22, 33, • • • : 13, 26, 39, • • • 5, 7, 8, 9. 17, 34, • • • : 19, 38, • • • : 23, 46, • • • 8, 9. 9. For « = 8, Cunningham's table of the solutions of x*+l=0 (mod p) (CUNNINGHAM 28, 29) has been extended from p= 100 000 to / > = 200 000 by HOPPENOT 2. So far we have discussed the special congruence xn = 1 (mod p") in which « is fixed throughout the table. There are several tables in which « = />—!. Tables of solutions x of the congruence (2) x"-i = I (mod />2) which occurs, for instance, in the discussion of Fermat's last theorem date from JACOBI 1, who gave all solutions of (2) for 3^p^37. BEEGER 1 gives a more extensive table, in fact for /><200. MEISSNER 2 gives only one root x of (2) for /><300, and a root of x"~i = 1 (mod p3) for p < 200. A very short table of all solutions of a;"-i = 1 (mod p") 1 g a ^ 12, p £ 13 is given in BERWICK 1. Another set of tables in which n depends on p is that of CUNNINGHAM 22 in which roots of *"*= + ! (mod />•") are tabulated, and in some cases roots of xir* = + i (mod p")t q=2,3,5,6 p" < 10000, p g 19. Special tables of the general binomial congruences x" = r (mod p) or axn = 1 (mod p) may be cited as follows: CUNNINGHAM 21, giving solutions of x4 = + 2 (mod p) and 2x* = + 1 (mod p) for p < 1000, and GERARDIN 3, giving all 4 solutions of [21]

DESCRIPTIVE SURVEY 2x* m 1 (mod p) for 1000 < p < 1600, extended by VALROFF 1 up to /><5300. CUNNINGHAM and WOODALL 9 have given tables of roots of the congruences 2" = w (mod p"), 2' = — z (mod p"), v2» = 1 (mod />"), x2* = — 1 (mod />"), for/><50, and />=73, 89, 127, 257, and for />"<1000 when«>l and />g!7; for 43^/>^199, values of w, z, y if ±£ 100 and values of x if ^250; for 199 ^/>< 10 000, values of wand z if ^100; for 199 ^p< 1000, and for certain selected primes < 10 000, values of y if g 100, and values of x if ^ 250. Finally we may cite here a rather special table of LAWTHER 1 which gives for each integer ^V< 140 the least positive solution x of X* = ± l (mod N), which is "primitive" in the sense that of ^ + 1 (mod AO for any positive b<d. Here d is the largest possible exponent for which such an x exists. For example if N is a prime, then d=(p—1)/2 and x is the least quadratic non-residue of p. This table is for use in the splicing of telephone cables. d6. Higher residues By a higher residue modulo p we shall mean the residue of an «th power, where «Sj3. The case n = 2 will be dealt with separately under i2. A list of all the «th power residues modulo p may be found by taking every «th entry in a table of powers of a primitive root as described under d3. If the greatest common divisor of n and p— 1 is S, this process will give in fact all the 5th power residues, or in other words one can confine oneself to the case in which n divides p— 1 so that p is of the form nx+1. KRAITCHIK 3 has given a table of all «th power residues for n = 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18 with respect to the first 20 or 25 primes p = nx+l in each case. A table of all three-digit cube-endings, i.e., cubic residues, modulo 1000, is given in MATIES 1. For the case n = 4, GAUSS 2 has a short table giving for each /> = 4x+1< 100 not only its biquadratic residues but also those numbers <p which have each of the other three biquadratic characters. The corresponding table for cubic characters by STIELTJES 1 extends to p = 6x+1^6l. A rather special table of NIEWIADOMSKI 1 gives all the pth power residues (mod p*) for each ^<200, and is used in connection with criteria for Fermat's last theorem. Some tables give lists of those primes p having a given number a as an [22]

DESCRIPTIVE SURVEY d6-d» nth power residue. It has been pointed out before that such primes may be picked out of the tables, described under d2, which give the residue-index of the base a modulo p. DESMAREST 1 and GERARDIN 1 each gave lists of primes < 10 000 of which 10 is an «th power residue. Similarly, KRAITCHIK 4 gives lists of primes < 10 000 of which 2 and 10 are «th power residues for all possi- ble «^2. REUSCHLE 1 has listed all primes p<50 000 having 10 for a cubic residue, and all primes p<25 000 having 10 as biquadratic and octic residues. CUNNINGHAM 2 lists all primes < 25 000 having 2 as an octic residue, indicating those which have 2 as a 16th power residue. COSSET 1 has a table for finding the biquadratic character of q with respect to p = a2+b2 in case the value of b/a (mod q) does not exceed 8 in absolute value. Tables in CUNNINGHAM and COSSET 1 serve to determine the biquad- ratic character (q/p)* when q contains no prime factor exceeding 41, and the cubic character (q/p)s when q contains no prime factor exceeding 47. These tables are reproduced in CUNNINGHAM 36 (p. 130-133). These restrictions on q are less drastic than would appear at first sight, since it is frequently easy to replace a given q by another congruent to it modulo p, and having only small prime factors. The "quadratic partitions" p = a2 + 62 and 4/> = Z,2 - 27M2 are supposed to be known. Tables of these partitions are cited and described under J2. Finally there are tables giving merely the frequency of primes having a given number a as an «th power residue. These have been obtained from tables of residue-indices by counting the number of p's having a given entry. CUN- NINGHAM and WOODALL 7 give the number of primes p in each 10 000 up to 100 000 for which (2/p)n= 1 for all n £ 40. These are based upon corresponding enumerations of primes having given residue-indices.i CUNNINGHAM 23 has given similar tables for each of the bases 2, 3, 5, 6, 7, 10, 11 and 12. For the bases 2 and 10 the number of primes in each 10 000 up to 100 000 for which (2//>)n= 1 and (10//>)n= 1 respectively is given for n ^ 40. A smaller table gives, for each of the bases mentioned above, the number of primes less than 10 000 having this base as an «th power residue («^40). These are based on a set of tables giving for each base the number of primes having a specified residue- index. d6. Converse of Fermat's theorem It is a well known fact that the fundamental theorem of Fermat (1) jn=a (mod n), if n is a prime has a false converse. Four tables giving examples of composite numbers n for which the congruence (1) holds may be cited here. Two of these are sufficiently i The number of primes £x for which (a/p)n= 1 is clearly the sum of the numbers of primes Sat for which the residue-index of a has the value kn (k = I, 2, 3, • • • ). [.23]

DESCRIPTIVE SURVEY complete to be used in connection with the problem of identifying primes, and will be described from this point of view under g. Isolated examples of composite numbers n satisfying the congruence (1), usually with a = 2, date from 1819. In 1907 ESCOTT 1 gave a list of 50 miscel- laneous composite numbers n for which (2) 2"=2(mod«). Another miscellaneous list is given by MITRA 1 for a = 2, 3, 5, 6, 7, and 10. D. H. LEHMER 6 gives a list of all 8-digit composite n satisfying (2), and having their least prime factor />>313. The factor p is given with each «. This list has been augmented by POULET 4, who has listed all composite «<108 for which (2) holds. Each n is given with its least factor provided this factor ex- ceeds 30, otherwise the largest prime factor is given. The list comprises 2037 numbers. Many of these numbers n are such that (1) holds for every a prime to « and are accordingly marked with an asterisk. e. FACTOR TABLES No other kind of table in the theory of numbers is as universally useful as a factor table. The problem of factoring has long been recognized as a very fundamental one, and factor tables, as a partial solution of this problem, have a long and interesting history. This is especially true of the first of the two kinds of factor tables described below which we have called "ordinary." These factor tables were constructed for general use, the entries being found either by a sieve or by a multiple process. Tables of this sort, in which the entries are obtained readily, but not in their natural order, and in which an isolated entry cannot be easily found by direct calculations, exemplify the ideal table in the theory of numbers. The history of ordinary factor tables may be found in Chapter 13 of DICKSON 4, and in the sources there referred to, where an account will also be found of the numerous very old tables that are of historical interest. More recently, a bibliographic list of 16 ordinary factor tables, both old and new, beyond 100 000 has been given by Henderson in PETERS, LODGE and TERNOUTH, GIFFORD 1 (p. xiii-xv). Tables of factors of numbers of special form are as a rule not published separately, but are scattered through periodical literature. An effort has been made to give a reasonably complete account of such tables. d. Ordinary factor tables By an ordinary factor table we mean a table which gives at least one di- visor > 1, or indicates the primality, either of every number within its range, or else of all the numbers not divisible by the first k primes. We can classifyi such tables into types, according to values of k. A factor table of type 0 would i To be sure, there are a number of small factor tables which omit only multiples of 2 and 5, and these escape our classification. [24]

DESCRIPTIVE SURVEY 6i be a table dealing with all integers in its range, a type 1 table would consider all odd numbers in its range, a table of type 3 would deal with numbers prime to 30, etc. All large tables are of types 3 and 4. Theoretically the higher the type the more condensed the table becomes since a higher proportion of the natural numbers is thereby excluded. A table of type 25, for example, dealing with only those numbers whose least prime factor exceeds 100, would thus eliminate from consideration 88% of all numbers as compared with about 77% for a table of type 4. It is not difficult to see that the advantages of condensa- tion gained by raising the type number are soon more than offset by the diffi- culties of arranging and ordering the table, if indeed one is to maintain the usual condensed form in which the number, whose least factor is given, is indicated merely by the position which that factor occupies in the body of the table. A factor table of high type and of very considerable extent could, how- ever, be arranged in a form similar to a list of primes in which the last few digits of each number considered are given together with some symbol for its factor. The almost universal use of computing machines makes the omission of small factors from a table of high type a less serious objection than formerly. Factor tables may also be classified according to the range of numbers about which information is given and also according to the amount of informa- tion given. The only table which gives the fullest information possible is that of ANJEMA 1. This rare table lists for each number ^ 10 000 the complete set of all its divisors. A dash (or two dashes in case « is a square) separates those divisors which are < \/« from the others. This table is quite useful for experi- mental work on certain numerical functions and Dirichlet series. All other tables give either the canonical factorization into products of powers of primes, e.g., 360 = 2s-32-5, or else the least prime factor of each number considered. Of the many small factor tables to 10 000 or thereabouts GLAISHER 27 (which was taken from BARLOW 1) and STAGER 2 are typical in that they give the canonical factorization of every number less than 10 000 and 12 000 respec- tively, and are at the same time quite reliable. An unusual table to 10 000 is due to CAHEN 2. It is a table of type 5, which omits primes as well. Only the least factor is given of each composite number, prime to 2-3-5- 7-11, and less than 104. Some idea of the condensation this achieves may be gained from the fact that it occupies only three and one half small pages. Turning now to medium-sized factor tables we find 10 tables with upper limits ranging from 50 000 to about 250 000. The most useful and reliable of these are KAVAN 1 and PETERS, LODGE and TERNOUTH, GIFFORD 1. Both are of type 0 and give canonical factorizations of all numbers up to 256 000 and 100 000 respectively. The arrangement in the latter table in which consecutive numbers lie in the same column rather than in the same line, is more conven- ient for many of the purposes for which such a table would ordinarily be used. Other tables in this group giving canonical factorizations are of type 3. These are [25]

ei DESCRIPTIVE SURVEY reference upper limit POLETTI 2 50 000 CARR 1 99 000 GIFFOKD 1 100 390 VEGA 1 102 000 LIDONNE 1 102 003 GOLDBERG 1 251 647 Lidonne's table is actually of type 0 as far as 10 000. The tables of Gifford and Goldberg should be used carefully, since each contains numerous errors. Poletti's table is of a handy pocket size but has quite a number of misprints. The other tables in this group give only the least prime factor. LEBESGUE1, which is a table of type 4, extends to 115 500. INGHIRAMI 1 deals with all num- bers prime to 10 and less than 100 000, but is quite unreliable. GRAVE 3 is a type 3 table extending to 108 000. The largest table giving canonical factorizations is the monumental Cribrum Arithmeticum of CHERNAC 1. This is a type 3 table and it extends to 1 020 000. It is remarkably accurate considering the number of entries and the era in which it was produced (1811), although a complete examination of this table has never been undertaken. All other large tables list only the least prime factor of the number n con- sidered, blank entries indicating that n is a prime. If the entry is a prime p >\/n, then the quotient n/p is also a prime. If p^^/n, it might be necessary to consult the table again (or perhaps some smaller more convenient table) for the least factor of n/p in case the complete decomposition of n is desired. A single examination of the table yields the often sufficient information that the number n is composite. The nineteenth century saw the production and publication of such factor tables for the first 9 millions. BURCKHARDT 1, 2, 3 set the style with his table of the first three millions. These tables, almost always bound together, are, because they deal with the first three millions, more frequently useful than those of J. GLAISHER 1, 2, 3 for the fourth, fifth, and sixth millions and those of BASE 1, 2, 3, for the seventh, eighth, and ninth millions. All nine tables are of type 3 and are quite uniform in their arrangement. The page is split into 3 parts by two horizontal partitions, and entries in the same line, but in ad- jacent columns, refer to numbers differing by 300. This arrangement makes for ease in entering the table. This advantage to the user was paid for at the price of numerous errors (many of which occur in the eighth million) due to the fact that the practically mechanical and self-checking stencil or sieve proc- ess could not be employed to advantage for primes p much beyond 300 on account of the lengthy stencils required. Instead, recourse was had to the "multiple method," and numerous entries were put in the wrong place in the tables. In referring to nineteenth century tables mention should be made of the huge manuscript table of KULIK 3 which extends from 4 000 000 to 100 330 201. [26]

DESCRIPTIVE SURVEY ei-«! This is a type 3 table arranged exactly like Burckhardt's tables, except that the two horizontal partitions which divide the page into three parts are missing. Kulik used a system of one- and two-letter symbols to represent the primes, so that no entry requires more space than two letters. In this arrangement the use of stencils was feasible up to p = 997, the "multiple method" being used for 4-digit primes. Early in this century D. N. Lehmer began the construction of his monu- mental Factor Table for the First Ten Millions (D. N. LEHMER 1), which ap- peared in 1909. This is a type 4 table with a simpler arrangement than that used by Burckhardt, Glaisher, and Base; that is to say, the arrangement is simpler for construction, but less simple for use. Entries in the same column, but in adjacent rows, refer to numbers differing by 210 = 2-3-5-7. There are naturally #(210) = 48 columns. This arrangement enabled the use of stencils throughout the construction of the table. The user will find it a little more troublesome to enter this table than, for example, Burckhardt's. An auxiliary sheet enables one to find the exact row and column in which the least factor of one's number is given. This loose sheet, entitled "Auxiliary Table," which is reproduced on the reverse side of page 0, is apparently missing by now in many copies, since many writers contend that in order to enter the table it is necessary to divide the given number by 210, the quotient giving the page and line numbers, and the remainder giving the column number. Although this is not necessary, it is certainly sufficient and those users, to whom an electric calculating machine with automatic division is available, will find this method very effective where frequent use of table is required. The user can be turning to the proper page while the machine is operating. No error has as yet been found in the 2 372 598 entries of Lehmer's table. A manuscript table for the sixteenth million was computed by DURFEE 1. The table, which is on 500 sheets of heavy paper, appears to have been copied from a type 5 table. Those numbers, whose least factor is 11, were later inter- polated in red ink. The result is a type 4 table. GOLUBEV 1 computed manuscript tables of the eleventh and twelfth mil- lions. Cunningham and Woodall have published many short tables beyond 10 million incidental to their determination of successive high primes. These tables will be cited under fi where these lists of primes are described. Similarly, KRAITCHIK and HOPPENOT 1 have two factor tables for the ranges from 10i2 to 10i2± 104. These are of type 1, and give only the least divisor. The first of these from 10i2—10* to 10i2 was reproduced in KRAITCHIK 12. e2. Tables of factors of numbers of special form The factorization of numbers defined in some special way has been the subject of countless investigations. In many cases short tables giving the re- sults of a particular investigation have been published, mostly in periodical [27]

e: DESCRIPTIVE SURVEY literature. Sometimes these results are used to obtain further factorizations. Often, however, each entry represents a great deal of hard work, in no way lessened by the existence of the other entries of the table. Occasionally, the complete factorization of a certain number is not known, but only one or two small prime factors are given. Again, there are often gaps in the table where even the prime or composite characters of the corresponding numbers are un- known, and may well remain so for centuries to come. It would therefore be difficult, and perhaps valueless, to give a precise account of just what factoriza- tions are given in each of the many ancient and modern tables of factors of numbers of special form. Fortunately, writers have a tendency to reproduce the old tables along with their new entries. Thus it has been possible to neglect quite a number of historically interesting tables and to cite in each case the two or three modern ones by which a particular class of tables has been super- seded. By far the majority of tables of factors of numbers of special form deal with what are, in the last analysis, the factorization of certain cyclotomic functions. The Fermat numbers 22"+l, the Mersenne numbers 2"— 1, and more generally the numbers 2"+1,10"± 1, a"+1, a" + b", the Fibonacci num- bers, the functions of Lucas and their generalizations comprise the class of numbers referred to. If we denote by Qn(x) = **<»> + • • • = n (*»/« - !)»«> I/H the irreducible cyclotomic polynomial whose roots are the <t>(n) primitive «th roots of unity, so that we have the factorization *- - 1 = n Qt(x), • l/n then t'he tables referred to may be said to give the factors of x"— 1, when x is integral or rational, or (when x is algebraic) of the norm of x"— 1 taken with respect to the field defined by * or a subfield of that field. In all cases Qn(x) or its norm is the essential factor, the other factors Qt(x) (5 <«) having appeared before in the table. Thes'e other factors are quite often given separately and are called the algebraic or imprimitive factors; occasionally they are omitted entirely and only the factors of Qn(x), styled as the irreducible or primitive factors are given. To begin with, up-to-date tables of the factors of the Fermat numbers 22"+l are given in CUNNINGHAM and WOODALL 10 (p. xvi) and in KRAITCHIK 5, 6 (p. 221). These give one or more factors of 2^+1 for« = 5, 6, 9, 11, 12, 15, 18, 23,36, 38, and 73. For « = 0, 1, 2, 3 and 4, 22"+l is a prime as noted by Fermat. The numbers 22 +1 and 22 +1 are composite, but no factor of either [28]

DESCRIPTIVE SURVEY e2 number is known. Another table, lacking the entry for «=15, is given in KRAITCHIK 3 (p. 22). A table of the latest results on Mersenne numbers 2P— 1, where p is prime, is given in ARCHIBALD 1. Here the reader will find a history of the problem with complete references to the original sources. A short table giving merely the number of prime factors of 2P—1 for p^257 known in 1932 appears in D. H. LEHMER 4. Older tables of the factors of Mersenne numbers are in CUNNINGHAM and WOODALL 10 (p. xv), CUNNINGHAM 19 and WOODALL 1. This last table includes the forms of the factors of the numbers not then com- pletely factored. KRAITCHIK 4 (p. 20) gives a list of small factors of 2"— 1 for 59 primes p, 79^p< 1000, together with a list of the 85 primes p between 100 and 1000 for which no factor of 2"—1 is known. Tables of the factors of the numbers 2"±1 really begini with LANDRY 1, reproduced in LUCAS 1 (p. 236), who gave in 1869 the complete factorization of 2"±1 for all values of « = 64, except 26i±1 and 264+l. Recent tables are due to CUNNINGHAM and WOODALL 10 (p. 1-9), and KRAITCHIK 7 (p. 84-88). The first of these gives all information known in 1925 as to the factors of 2"± 1 for n odd and <500, and of 2"+1 for « even and = 500. Naturally, for such large ranges of n many entries are incomplete or even blank. However no factor <300 000 has been omitted. The table really gives the factors of Qn(2) for n odd and <500, and for n even and ^1000. The KRAITCHIK 7 (1929) table is an extension of one given in KRAITCHIK 3 (1922) and gives complete factorization of 2"± 1 as follows: 2--1 « odd, «= 1-77, 81, 87, 89, 91, 93, 99, 105, 107, 117, 127. 2"+l n odd, n= 1-65, 69, 75, 77, 81, 83, 87, 91, 97, 99, 105, 111, 135. 22*+i_2*+i+l,4£+2 = 2-138, 150, 154, 162, 170, 174, 182, 198, 210, 270, 330. 2"+i+2*+i+l, 4^+2 = 2-130, 138, 146, 150, 154, 162, 170, 174, 182, 186, 190, 198, 210, 234, 258, 270. 24*+l, 4*=4-84, 96. Primitive and algebraic factors are given separately. The facts that 2ioi _ l, 2ios _ I, 2i09 - 1, 2i" - 1, 2i39 - 1, 22" - 1, 2i28 + 1, 2266 + 1 are composite are also entered in the table. No factors of these numbers are known. Three factors of 2ii'— 1 are also given. i The comparatively insignificant table of REUSCHLE 1 (p. 22) antedates this by 13 years. [29]

d DESCRIPTIVE SURVEY This table has been brought up to date in 1938 in KRAITCHIK 13. Fac- torizations are given here of 2" - 1 for n = 79,85, 95*. 111. 2" + 1 for n = 73, 93, 95. 22*+i _ 2*+i 4. I for ^k + 2 = 146*, 186*, 190*, 234*, 250*. 22*+i + 2*+i + ! for 4k+ 2 = 142,158*, 222*. 24* + 1 for 4k = 88, 100*, 108, 120. where * indicates that there is some doubt that certain large factors of these numbers are actually primes. The number 224i— 1 is given as composite but without known factors, but there is no mention of the fact that the number 2i4*—1 belongs in the same category. A table giving the factors of 24*+l for 4£ = 4 — 88, 96 appeared in KRAITCHIK 8. A table (p. 24-26) of KRAITCHIK 4 gives all prime factors <300 000 of 2"± 1 for n odd and <257 and of 2u+2+l for 4k+2 < 500 in those cases where the complete factorization of these num- bers had not then been found. Next to the numbers 2"— 1, the numbers 10"— 1 have been most frequently under consideration. These correspondingly larger numbers are especially in- teresting from the point of view of repeating decimals. The rational fraction k/p has a decimal expansion of period n if and only if p divides 10"—1. This period is "proper" only in case p is a primitive factor of 10"— 1. An early table of factors of 10"—1 is due to REUSCHLE 1. It is limited to «^42, and is naturally incomplete in many of its entries. Another old but readily accessible table is due to SHANKS 2, which gives all factors <30 000 of 10"—1 for n< 100. Actually only the factors of Qn(10) are given. In twenty- five cases « is marked with an asterisk to indicate that the factorization is complete. As a matter of fact it is also complete for «= 19, 23, 25, 26, 27, 34, 36, 38, 46, 48, 50 and 62. Similar tables are found in BICKMORE 1, 2, and G^RARDIN 1. In 1924 KRAITCHIK 4 (p. 92) gave the complete factorization of 10"-1 for n odd, «=1-21, 25, 29 and of 10"+1 for«=1-17, 21, 23 and 25. CUNNINGHAM and WOODALL 10 give all factors < 120 000 (if any) of 10" ± 1 for n odd and ^ 109 and of 10"+1 for n even, ^ 100. There are of course many incomplete entries. Many new complete factorizations have been discovered since the publication of this table. The most up-to-date tables of the complete factorizations of 10"+1 are in KRAITCHIK 7 (p. 95). These give all prime factors of 10"— 1 for all odd «^ 29, and of 10»+1 for «=1-21, 23-25, 27, 30, 31, 36 and 50. (The case of 1036-1 is in doubt.) Besides the numbers 2"-1 and 10"—1 other numbers of the form a"—1 have been the subject of factor tables. Thus REUSCHLE 1 gives the factors of a"—I for o = 3, 5, 6, 7, for «g42, and similar tables by BICKMORE 1 give corre- [30]

DESCRIPTIVE SURVEY d spending results for a = 3, 5, 6, 7, 11, 12 for «5=50. (Both these tables deal also with o = 2 and 10 as mentioned above.) These tables are far from complete. The most extensive tables of this kind are CUNNINGHAM and WOODALL 10, reproduced in KRAITCHIK 7. For the bases a = 3, 5, 6, 7, 11 and 12 Cunning- ham and VVoodall give, together with many complete factorizations, all prime factors /><100 000 dividing either a"+l for n odd and ^109, or o"+l for n even and ^ 100. Only the factors of Qn(a) are given. For these bases little attempt to factor individual numbers was made by the authors, the results being obtained indirectly from tables of exponents. As a result a goodly num- ber of blank entries have now been filled in by various computers since the volume appeared. Most of these for the bases 3, 5, 6, 7, have been included in KRAITCHIK 7 (p. 89-94). This gives the complete factorization of a"±l as follows: 3» - 1 « odd, = 1-41, 45, 47, 49, 51, 75, 105. ^ 6k + 3, = 1-31, 35, 37, 40, 41, 42, 47, 48, 60, 84. - ~ - = 6* + 3, = 3-117, 135, 165. 5" - 1 n odd, = 1-29, 33, 35, 45, 75. 5» + 1 « = 1-22, 24, 25, 27, 30, 34. 6" - 1 n odd, = 1-23. 6" + 1 n = 1-22, 24, 26, 28, 30, 33, 35, 42. 7" - 1 n odd, = 1-17, 27. 7" + 1 n = 1-16, 18, 21, 22, 35. A small separate table giving the latest information on the factors of 6"+l appears in KRAITCHIK 11. This gives the complete factorization of 6"+1 for «= 1-32, 42. For the bases a from 13 to 30 (exclusive of 16, 25 and 27) CUNNINGHAM 37 has given as far as known the factors of a" +1 for all n ^ 21. Thus far we have spoken of tables of factors of numbers of the form a"± 1 in which a may be thought of as small and fixed while n ran to high limits. There is also another set of tables in which n is small and fixed, while a varies. Obviously the numbers in these tables do not increase as rapidly as those in the tables in which a is fixed and n varies. On the other hand less information about the possible factors of these numbers is available. The first table of this sort is due to EULER 2 (1762). This is a factor table for numbers of the form a2+l extending to a^ 1500. Only factors < 1000 are given as the table was constructed by a sieve process. Surprisingly enough, this is the only factor table of its sort ever published, although other such tables have existed in manuscript from which have been extracted lists of primes of the form a;2+l to be mentioned under fs. There are [31]

C2 DESCRIPTIVE SURVEY two tables giving factors of a2+l for very large but scattered values of a. The first of these is GAUSS 8, which gives the complete factorization of a2+l or of (a2+l)/2 for 712 values of og 14 033 378 718, in those cases in which no prime factor exceeds 200. This table is only one of a set of 9 tables giving the factors of a2+62 to be described presently. The other special table of factors of a2+l is CUNNINGHAM 8. If (x, y) is a solution of the Pell equation *2 — Dy* = — 1 , then the factors of *2+ 1 = Zty2 are obtained from those of D and y. A list of the 97 values of x between 104 and 10i2 for which the factorization of *2+l is thus possible (for D<1500) is given, together with the factorizations of the corresponding D's and y's. This table is extended and greatly ramified in CUNNINGHAM 28 (p. 106-112). Tables of factors of a"+ 1, with «>2 and fixed, occur in REUSCHLE 1 for a< 100 and n^ 12, with many gaps. The largest collection of such tables occurs in the first, second, third and fifth volumes of Cunningham's Binomial Factorisations: CUNNINGHAM 28, 30, 32, 33. Many of these tables are extremely special and short. The essential factor Qn(a) of a"— 1, though an irreducible polynomial in a, may become re- ducible as a polynomial in x when a is replaced by any one of a large number of appropriate functions of x. Thus we get cases of relatively easy factorizations of numbers of the form Qn(a) where a is of special type. The 185 factorization tables in these four volumes are largely of this special type. Nineteen refer to Qn(a) and are in no way special. Their extent and location are given as follows: » limit of a volume 5 1000 2 106,108,110, ••• 118 7 250 3 154-158 8 1000 1 113-119 9 250 3 178-181 10 1000 2 107, 109, • • • 119 11 100 5 104-105 12 1000 1 157-163 13 100 5 113-114 14 250 3 154-158 15 200 2 185-188 16 200 1 140-141 18 250 3 178-181 20 200 2 177-178 21 40 3 172 22 100 5 104-105 24 200 1 215-216 26 100 5 113-114 30 200 2 185-188 36 54 3 191 There are also tables where « is a multiple of the n's listed above, but these are more than half blank. Most of those entries in the above tables which are complete factorizations have been reproduced, with a few additions, in a more compact form by KRAITCHIK 7. Here one finds tables of the factors of Qn(a) for a< 100 and for [32]

DESCRIPTIVE SURVEY «=1-12, 14, 15, 16, 18, 20, 24, 30 (p. 96-107), with some gaps, together with many supplementary results for other values of n up to 60. Numerous tables are given of the factorization of xn+ 1 (really of Qn(x) and Qtn(x)) for values of «<50. These are without gaps and extend to various limits of x as indicated in the following scheme. This description includes special tables in which the factorization of Qn(x) is rendered easier for the special values of x indicated, on account of an algebraic decomposition as mentioned above. A simple ex- ample of this phenomenon is Factorization of *"-i x"+l » general x special x general x special x 4 5 *<400 (p. 118-119) *g.409 (p. 116-117) (p.'122~-123) *<400 (p. 120-121) s<400 (p. 126-127) 6 *=2o',o<130 (p. 128-9)1 a;=6o1,a<70 ] *=7a',o<20(p. 130) 7 8 9 10 *S 50 (p. 130-131) * 550 (p. 132-133) *S5O (p. 130-131) x<, 32, 34, 36 (p. 132) * 5 50 (p. 132-133) * £ 60 (p. 135) *=2a2'o<25 1 *=10a',o<8(p. 135)/ For larger values of n, in fact for «= 11-16,18, 21, 22, 24,26,27,30,33, 35, 39, 42, and 49 there are small tables with many gaps. For further addenda in Cunningham's tables see BEEGER 5 and HOPPENOT 1. There are several tables giving factors of numbers of the form p" + 1. We have already pointed out that several tables of primitive roots give in addition the factorization of p— 1. These are described in di. Similarly, Cunningham's tables of quadratic partitions (described under J2) also give this information. These tables are found in CUNNINGHAM 7, p. 1-240, and CUNNINGHAM 36, p. 1-55. These lists have been useful in discussing primes of the form £«+l. CUNNINGHAM and CREAK 1 (p. 1-91) give all divisors of p— 1 (except 1 and/>— 1) forp<W. EULER 1 gave factorizations of <r(p") = (p"+i— !)/(/>— 1) as noted under b». A more extensive table is in KRAITCHIK 7 (p. 152-159). This gives factors of p" ± 1 for a 5= 15, as also noted under b2. Two small special tables may be noted. GERARDIN 2 gives a table of the factorization of those numbers of the form (/>+l)(/>2+l), /><1000, all of whose factors are less than 1000. GLAISHER 21 gives the factors of p« —(—l)("-»/2 for all p< 100, ex- cept p = 79 and 83. Finally, there are two small tables of factors of n"— 1. LUCAS 1 (p. 294) gives the complete factorizations of (2w)2m—1 for m=7, 10, 12, 14 and 15, while CUNNINGHAM 24 gives factors of y"±l for y^50, many incomplete. [33]

d DESCRIPTIVE SURVEY Turning now to more general numbers a" + b" with b>l, we find a few tables of their factors. The earliest is a special table of GAUSS 8 for «=2, al- ready referred to in connection with a2+l. The complete table gives for 2452 numbers of the form a2+62, 6^9 their complete factorization. The numbers a are so chosen that all the prime factors of a2+6" are less than 200. For each value of b there is an inverse table showing for each ppssible p all those a's for which the greatest prime factor of a2+62 is p. The fact that the number of these a's appears to be finite in each case must have led Gauss to conjecture for the first time that the largest prime factor of x*-\-A tends rapidly to infinity with x, a fact established by Ivanov in 1895. However, this table was really intended to be used in discovering arccotangent identities. Numerous small tables of factors of a"+ 6" occur in Cunningham's Bi- nomial Factorisations as follows: form v. pages 5 106,107,109,111 1 217 5 115-116 3 169-171 2 189,193 2 192-193 1 143 xis+y" 3 191-192 3 173-174 5 112 3 193 2 195 form T. pages x*+y* 1 99 x>+y> 1 149-150,152,221 *•+/ 1 120-129,220 jf — yl 2 120-123, 130, 133-146, 148, 154, 158 x*+y* 2 124-129, 131-133, 147-149, 155, 159 x'+yt 1 164-171, 174-179, 181-189, 220 x<±yi 3 160-168 *>+y> 1 142-143 x'±y' 3 185-187, 189 xi'+yi' 2 179, 183 KRAITCHIK 7 (p. 107-109) contains the complete factorization of 3" ±2" as follows: 3" - 2", n odd, = 1-27, 33, 35, 105 3" + 2", n= 1-27, 29, 30, 31, 33, 35, 36, 42, 45, 54, 63, 70 and 75. CUNNINGHAM 26, which is an extension of CUNNINGHAM 17, contains tables of the factors of xn±(x-1)" for w = 3, 5, 7, 9, 11, and 15, with x^ 100, 100, 50, 50, 40, and 40, respectively. CUNNINGHAM 27 gives factors of xn±(x—n)n for « = 3, 5, 7, 9, 11, and 15 and for x^74, 187, 60, 74, 43, and 49 respectively, with some gaps. Both of these tables reappear in Binomial Factorisations as noted above. A short table of the factors of x*v + y*v for 15 pairs (x, y) is given in CUN- NINGHAM 24 (p. 74). The essential factor a*^Qn(a/b) of a" — b" can, by a formula of Aurifeuille, be expressed in the form X2 — nabY*, where X and Y are certain homogeneous polynomials in a and b, tables of whose coefficients are described under o. In case n, a and b are so chosen that nab is a perfect square this essential factor, generally irreducible, breaks up into two factors. Tables of factors of a" + b" [34]

DESCRIPTIVE SURVEY e2 in this case have been given by KRAITCHIK 2. Here b, ag 100, and n is usually less than 50. Quite a large number of factorizations are within the range of factor tables. There are comparatively few blank entries. The technique of factorization developed for a" + b" is also applicable, with slight modifications, to the function £/„ = («"—/?")/(«—/3) of Lucas (and its generalizations) in which a, /3 are algebraic integers. For example the Fibonacci series 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, • • • , Un, • • • ; Un+i = Un+ £/„-i, where a=(l + V5)/2, 0 = (1 — V5)/2, has been the subject of factor tables. The first such, due to LUCAS 1 (p. 299), gives the complete factorization of Un for «^60. KRAITCHIK 4 (p. 77-80) gives the factors of both Un and Vn = Utn/ Un as follows: Un, n odd, = 1-71, 75, 81, 85, 87, 95, 99, 105, 129 Vn, n ^ 5 (mod 10), = 1-72, 77, 78, 80, 81, 84, 87, 90, 93, 99, 102, 111, 120 F", n = 5 (mod 10), = 5-175, 195, 205, 215, 225. Another factor table of what is essentially a Lucas function is due to D. H. LEHMER 2, and gives for «^30 the factors of yn, where i?n—2yl=l, (xn, >0 being successive multiple solutions of this Pell equation. The Fibonacci series increases more slowly than the series of numbers 2"—1, and hence more terms can be factored before the numbers become too large. A more slowly increasing series than the Fibonacci series has been fac- tored by HALL 1. Here the complete factorization of the norm N(a"—l), a function introduced by T. A. Pierce, in the field denned by the root a of a;3—*—1 =0, is given for n^ 100. Still slower series are factored by POULET 3. In case/(a;) is an irreducible reciprocal equation, the norm N(a"— 1) taken with respect to the field defined by the root a off(x) =0 will be a perfect square. The sequence Un = -\/N(an — l) is a recurring series of order at most 2r, where 2r is the degree of/(#), and the possible factors of Un are restricted to certain linear forms nx+b, permitting the factorization of quite large numbers £/„, especially when Un increases slowly. POULET 3 has published a number of series Un and Vn= Utn/Un, the terms of which are completely factored. He gives 7 series of order 2 (Lucas' functions) 7 series of order 4 1 series of order 8 to 138 terms 1 series of order 16 to 250 terms 1 series of order 32 to 382 terms 1 series of order 64 to 230 terms. The least rapidly increasing of these is the series of order 32 defined by the reciprocal equation [35]

e, DESCRIPTIVE SURVEY a;i0 + xg - x1 - x* - a;6 - *4 - x* + x + 1 = 0. In fact [7,82=360 429 381 874 489 = 16199093-22249973. The average value of Un+i/Un is only about 1.0845. The author mentions the construction of about 40 other series of this sort and gives many algebraic formulas of use in constructing such series. The conjectured parts of this memoir have been proved by the present writer. We turn now to the consideration of tables which give factors of binomials which are not cyclotomic, such as for example ka"+l or a4+464. Some of the methods and tables employed in the cyclotomic case are applicable here also. KRAITCHIK 6 (p. 222-232) has given a complete factor table of all numbers of the form £2"+1 lying between 108 and 10i2 with £<1000. Only the least fac- tor is given. This is an extension of the previous table, KRAITCHIK 4 (p. 12-13), for numbers of this form between 2- 10" and 10i2, with £<100, and 21g«g38 with some gaps. D. H. LEHMER 10 gives factors of numbers of the form k2"— 1 for k = 3, 5, 7, and 9, and n ^ 50 with some gaps. Factors of 6ks + 1 have been given by BEEGER 6. CUNNINGHAM and WOODALL 1 gave a table of factors of 10°2X+ 1 for o^ 10, x ^30 (with gaps) and for several higher values of a and x. CUNNINGHAM 25 gives the factors of xv + y* for 128 pairs of integers (x, y). CUNNINGHAM AND WOODALL 9 has considered the factors of 2"±q and of q2"+ 1. All factors are given for q^66. For67^g^260 only small factors are given of q2"+ 1. These numbers are remarkable for being nearly all com- posite. CUNNINGHAM 21 has tables of factors of y4± 2 and of 2y*± 1. These extend to y ^ 100, and to several higher values of y. A short table in KRAITCHIK 4 (p. 14) gives the complete factorization of the numbers pipt • • • />„+ 1, where />„ is the «th prime, for all «^8. LEBON 1 contains a table (part II) of all factors of numbers of the form Nk=2-3-5-7- 11- 13£+1 for such values of £5S4680 as make Nk composite. Tables of factors of numbers not associated with binomials are as follows: CUNNINGHAM and WOODALL 8 contains the factorization of numbers of the form 2"±2x± 1 for x<a<27, and several higher numbers of this form. VANDIVER 1 gives a list of small factors of Bernoulli numbers Bn. All values of n^(p — 3)/2 are given for which the numerator of Bn is divisible by p for ALLIAUME 1 has published decompositions of n\ for all n< 1200. In Table I he gives the factorization of «! into products of powers of primes, while in Table II, «! is expressed as a product of powers of "prime factorials" pipt • • • pr, where p, is the rth prime. This table is useful in computing values of log «!. PETERS and STEIN 1 have a table of the canonical factorization of the binomial coefficients up to those of the 60th power. Finally, we may cite the table of CUNNINGHAM 36 (p. 162-170) which gives [36]

DESCRIPTIVE SURVEY canonical factorizations of all numbers ^ 10', all of whose prime factors are < 13. This table has a number of interesting uses, especially in connection with the calculation of logarithms and the binomial congruence. Tables of the same sort, but very much more extensive, are given in WESTERN 4, together with tables showing the mere number of numbers N having small prime factors only, for many very large values of N. MILLER and LODGE 1 gives the number of numbers ^ 10' having a given prime p as least (and also greatest) prime fac- tor for all possible primes p. f. LISTS OF PRIMES AND TABLES OF THEIR DISTRIBUTION Tables of this sort naturally fall into two groups according as the primes considered are consecutive or not. Tables giving information on distribution phenomena are mostly concerned with consecutive primes. Lists of primes themselves have mainly two uses: 1) they may enable one to decide whether a given number is a prime or not, and 2) they serve as a source of statistical information about properties of primes. In spite of the existence of ordinary factor tables, the first use, whose importance is often not fully appreciated by those interested in distribution phenomena, is perhaps the best reason for the publication of lists of primes. Here, again, lists of consecutive primes are more useful than lists of primes of special form. fi. Consecutive primes Lists of consecutive primes are of two sorts, those giving all primes less than a given limit, and those giving all primes between two high limits. Most lists of primes of the first sort occur as arguments in numerous tables, such as those of the binomial congruence (di, d:), and certain "quadratic partition" tables cited under j2. Among the more extensive of these lists we may cite for example KRAITCHIK 4 (p. 131-191), giving a list of primes to 300 000. The tables of SIMONY 1 and SUCHANEK 1 contain a list of primes to 2U= 16 384, and from 2i4 to 100000 respectively. These tables give the primes also in the binary scale, or rather in a condensed form of binary scale in which, for ex- ample, the prime 2243 instead of being written 100011000011 is abbreviated to .3242, the dot being the symbol for 1. Among those lists of primes which are not the incidental arguments of other tables, many small ones are to be found in textbooks on the theory of numbers, and even in certain handbooks for engineers. J. GLAISHER 1 has a convenient list of primes to 30 341, giving also a column of differences which occasionally is useful. LEBESGUE 1 has given a list of primes to 5500 at the same time showing how each prime may be represented by a pair of symbols, a device similar to that employed by Kulik in his factor table. By far the most extensive list of primes is Lehmer's list of primes from 1 to 10 006 721 (D. N. LEHMER 2), which appeared in 1914. This list, containing 665 000 primes, 5000 on each page, is based on his Factor Table (mentioned [37]

fi DESCRIPTIVE SURVEY under 6i), and on previous factor tables. The arrangement makes possible the rapid determination of n when the prime />„ is given; the user should be careful to note that here 1 is counted as a prime. Other fairly extensive lists of primes are VEGA 1, for primes from 102 001 to 400 313, and POLETTI 2 (p. 3-67) for primes under 200 000. The latter, being in a handy pocket size, is quite convenient for occasional use. We turn now to lists of consecutive primes between high limits (beyond 10 million). There are, surprisingly enough, as many as 69 such lists. Most of these cover only a short range of natural numbers and all but 8 of them have their lower limit ^ 100 000 000. The following list has been kindly prepared by Dr. N. G. W. H. Beeger, who is the best authority on large primes. In each case are given the upper and lower limits of the range in which all the primes are determined. If, in addition, the author includes a factor table for the range considered, this fact is indicated by an asterisk. range reference 10 000 000- 10 001 020* CUNNINGHAM and WOODALL 5 10 000 000- 10 100 000 POLETTI 1 10 000 000- 10 100 009 POLETTI 2 10 076 676- 10 078 712* CUNNINGHAM 35 10 088 152- 10 088 651 CUNNINGHAM 35 10 324 364- 10 324 517 CUNNINGHAM 16 10 761 411- 10 761 949* CUNNINGHAM 16 11 000 000- 11 000 250 CUNNINGHAM 20 11 110 889- 11 111 333 CUNNINGHAM and WOODALL 5 11 184 451- 11 185 169 CUNNINGHAM and WOODALL 4 11 184 451- 11 185 169 CUNNINGHAM and WOODALL 2 12 093 036- 12 093 435 CUNNINGHAM 35 12 201 521- 12 201 702 CUNNINGHAM 16 12 206 762- 12 207 301* CUNNINGHAM 16 12 499 750- 12 500 250 CUNNINGHAM and WOODALL 5 13 421 558- 13 421 988 CUNNINGHAM and WOODALL 6 13 450 870- 13 451 536 CUNNINGHAM 35 14 285 429- 14 286 000 CUNNINGHAM and WOODALL 5 14 285 715- 14 300 000 POLETTI and STURANI 1 14 347 889- 14 349 923* CUNNINGHAM and WOODALL 4 14 912 970- 14 913 191 CUNNINGHAM 16 15 116 295- 15 116 794 CUNNINGHAM 35 16 275 683- 16 276 399* CUNNINGHAM 16 16 666 334- 16 667 000 CUNNINGHAM and WOODALL 5 16 776 197- 16 778 233* CUNNINGHAM and WOODALL 4 16 776 197- 16 778 233 CUNNINGHAM and WOODALL 3 19 173 819- 19 174 103 CUNNINGHAM 16 [38]

DESCRIPTIVE SURVEY f. range 19 486 153- 19 488 187* 19 999 600- 20 000 400 20 155 059- 20 155 725 20 176 304- 20 177 303 21 522 822- 21 523 899* 22 369 263- 22 369 980* 24 413 524- 24 414 600 24 999 500- 25 000 500 26 843 346- 26 843 745 30 232 589- 30 233 587 32 258 065- 32 261 290 33 332 667- 33 334 000 33 553 417- 33 555 451* 33 553 417- 33 555 451 34 482 759- 34 486 206 40 352 608- 40 354 606* 43 045 643- 43 047 800* 43 478 261- 43 482 608 44 738 910- 44 739 575 48 827 047- 48 829 201* 49 999 000- 50 001 000 52 631 579- 52 636 842 58 823 530- 58 829 411 60 465 177- 60 467 175* 61 621 560- 61 711 650* 67 107 787- 67 109 941* 76 923 077- 76 930 769 99 998 000- 100 002 000* 100 000 000- 100 001 000 100 000 000- 100 001 000 100 000 000- 100 001 699 100 000 000- 100 005 000 100 000 000- 100 010 0il 100 000 000- 100 100 000 134 216 729- 134 218 727* 999 999 001- 1 000 119 119* 1 000 000 000- 1 000 001 000 1 000 000 000- 1 000 010 000 1 000 000 000- 1 000 100 009 999 999 990 000-1000 000 000 000* 999 999 990 000-1000 000 000 000* 1000 000 000 000-1000 000 010 000* reference CUNNINGHAM 35 CUNNINGHAM and WOODALL 5 CUNNINGHAM 35 CUNNINGHAM 35 CUNNINGHAM 16 CUNNINGHAM and WOODALL 6 CUNNINGHAM 16 CUNNINGHAM and WOODALL 5 CUNNINGHAM 16 CUNNINGHAM 35 POLETTI 2 CUNNINGHAM and WOODALL 5 CUNNINGHAM and WOODALL 4 CUNNINGHAM and WOODALL 3 POLETTI2 CUNNINGHAM 35 CUNNINGHAM 16 POLETTI2 CUNNINGHAM 16 CUNNINGHAM 16 CUNNINGHAM and WOODALL 5 POLETTI2 POLETTI2 CUNNINGHAM 35 BEEGER 9 CUNNINGHAM and WOODALL 6 POLETTI2 CUNNINGHAM and WOODALL 5 KRAITCHIK 4 (p. 10) CUNNINGHAM 36 (p. 76) W. DAVIS 1 PAGLIERO 1 POLETTI2 POLETTI and STURANI 1 CUNNINGHAM 16 BEEGER 9 KRAITCHIK 4 (p. 10) POLETTI 1 POLETTI 2 KRAITCHIK and HOPPENOT 1 KRAITCHIK 12 KRAITCHIK and HOPPENOT 1 [39]

fi DESCRIPTIVE SURVEY Tables having to do with the distribution of consecutive primes pn are of 5 types. (A) Tables of w(x), the number of primes ga;, with or without the corre- sponding values of some approximating function. (B) Tables of ir(nh)— x{(n— 1)A}, i.e., tables of the number of primes in each successive interval of length h of the natural numbers. (C) Frequency tables, giving the number of centuries having a prescribed number of primes in each of a series of intervals. (D) Tables of anomalies in the distribution of primes. (E) Tables of £ „/,-» and of H"Sz ( 1 - />-') . In tables of type A values of w(x) usually have been extracted from lists of primes and factor tables. Meissel and Bertelsen have however evaluated r(x) independently for use in checking factor tables. As already mentioned, isolated values of ir(x) for x<W can be determined at a glance from D. N. LEHMER 2. A graph of ir(x) for x < 12000 is given in STAGER 1, 2. A small table of r(x) for consecutive integers x is included in GRAM 1, where ir(x) is tabulated along with the function *(*) = E log p p"Sx for all *<300, and for x = p", 300 <p"< 2000. All other tables give ir(x) for wide intervals of x. The best such table is D. N. LEHMER 2, where *•(*) is tabulated for x = 50 000(50 000) 107 and for x = k-lff}, k = 2, 9, 10, 100. These last four entries, due to Bertelsen and Meissel, are compared with the corresponding values by Riemann's formula All other entries of this table are compared not only with Riemann's formula, but also with those of Chebyshev and Legendre, which are /' •'i dx x and respectively. log x log x - 1.08366 Other tables of *•(*) may be cited and described briefly as follows: GLAISHER 16. This gives *•(*) for x= 100 000(100 000)9 000 000 compared with formulas of Riemann, Chebyshev and Legendre. This table is repro- duced in J. GLAISHER 3. GLAISHER 5 gives *•(£• 10«) for k= .25(.25)4 compared with various modifications of Legendre's formula. GRAM 2 gives «•(*) for a; = *-106, £ = .1(.1)1(.025)3(.1)7(.05)9(.1)10, as well as £ = 20, 90, 100, 1000. These values due to Bertelsen as already mentioned were computed directly by Meissel's method. All but the last four were verified by direct count in Lehmer's Factor Table. POLETTI 2 (p. 243) gives w(x) for [40]

DESCRIPTIVE SURVEY fi x= k• 10«, k = .2(.2) 1 (1) 10 and k = 20, 90,100, and 1000, with comparisons with the formulas of Riemann, Legendre, Chebyshev, and Cesa.ro. Tables of type B are more numerous than those of type A and are more indicative of the average density of primes in the region under consideration. The scope of each type B table which gives the number of primes in each suc- cessive interval of h natural numbers between the limits a and b may be given the following tabular description: reference a k b GAUSS 6 1 1 000 1 000 000 1 000 000 10 000 3 000 000 1 000 000 1 000 000 3 000 000 GLAISHER 1 1 50 000 1 000 000 8 000 000 50 000 9 000 000 GLAISHER 3 1 10 000 100 000 100 000 50 000 400 000 400 000 100 000 3 000 000 GLAISHER 2 6 000 000 100 000 9 000 000 GLAISHER 6 1 250 000 3 000 000 6 000 000 250 000 9 000 000 GLAISHER 11 3 000 000 10 000 4 000 000 1 250 000 4 000 000 GLAISHER 13 4 000 000 10 000 5 000 000 1 100 000 5 000 000 1 250 000 5 000 000 GLAISHER 14 5 000 000 10 000 6 000 000 1 100 000 9 000 000 1 250 000 9 000 000 1 1 000 000 9 000 000 HUSQUIN 1 1 1 000 000 10 000 000 DURFEE 1 15 000 000 100 16 000 000 Tables of type C date from GAUSS 6 and give for all possible n the number of centuries containing n primes in each successive interval of h natural num- bers between the limits a and b, and the total number of such centuries for the whole range a to b. The distribution always has a single mode about which there is a vague symmetry. The frequency tables in GAUSS 6 are due to Gold- schmidt and, though inaccurate, are more detailed than any published later. There are 20 tables, each covering a range (a, b) of 100 000 between 1 000 000 and 3 000 000 for which h= 10 000, and two summarizing tables for the sec- ond and third million in which h is now 100 000. Other tables of type C may be given the following description: [41]

fi DESCRIPTIVE SURVEY reference a k b GLAISHER 7 f 1 10« 3-10« [10" 9-106 GLAISHER 3 1 10* 3-108 GLAISHER 2 610" 106 9- 10" GLAISHER 11 3-10' 106 4-106 GLAISHER 13 4- 10" 106 5-106 1 10« 5- 10" GLAISHER 14 1 10« 9-10" KRAITCHIK 4 (p. 16) 1 10« 106 HUSQUIN 1 1 10« 10" KRAITCHIK and HOPPENOT 1 l0^-104 10s 10i2 KRAITCHIK and HOPPENOT 1 10^ 10* 10i2+10* KRAITCHIK 12 10i2 101 The table of HUSQUIN 1 and that of GLAISHER 13 show several discrepan- cies. Presumably this is due to errors in old factor tables. Tables of type D mainly relate to large gaps in primes, that is, long series of consecutive composite numbers. A few tables relate to the distribution of "twin primes" differing by 2, "triplets," etc. GLAISHER 7 gives for the ranges 1-3 000 000 and 6 000 000-9 000 000 all those gaps of 99 or more (79 or more for the first million) in the list of primes. Gaps of 111 or more for the same millions are given in GLAISHER 6. Gaps of 99 or more for the fourth million are listed in GLAISHER 11, for the fifth million in GLAISHER 13, for the sixth million in GLAISHER 14, where one also finds the largest gap in each of the first nine millions. Finally in GLAISHER 16 all gaps greater than 130 in the nine millions are given, arranged in order of length of gap. The largest gap in the first 10 millions is 153, following the prime 4 652 353. DURFEE 1 discovered an equally large gap following the prime 15 203 977. All the tables of types A-D cited so far that are due to Glaisher have been reproduced by J. GLAISHER 1, 2, 3 in the introductions to his factor tables of the fourth, fifth and sixth millions. Tables relating to the full 9 millions ap- pear in the introduction to the last of these volumes. WESTERN 3, using in part the data of Glaisher, constructed a table of those primes />n<107 whose difference pn—pn-i exceeds that of all smaller primes. This useful table has been reproduced by CHOWLA 1. The first 13 such primes had been listed by KRAITCHIK 4 (p. 15). There are a few tables giving facts about the distribution of twin primes. GLAISHER 8 gives the number of twin primes in each successive chiliad (1000) in each of the first hundred chiliads of the first, second, third, seventh, eighth, and ninth millions. There is also a companion table giving the number of these chiliads containing a prescribed number of twin primes. A summary of these [42]

DESCRIPTIVE SURVEY fi-f» results in GLAISHER 9 gives the number of twin primes in each of the ten suc- cessive myriads of the first 100 000 numbers of the above mentioned millions. POLETTI 2 (p. 244-245) gives the number of twin primes in each of the first 10 myriads beyond 10* for * = 0, 5, 7, and 9. STACKEL 1 gives the number of twin primes not exceeding x for *= 1000(1000) 100 000, while BUTTON 1 tabulates the same function for the same values of x and for the more extensive range x= 10 000(10 000)800 000. Short tables relating to twin primes and triplets appear in HARDY and LlTTLEWOOD 1. Five tables of type E, which date from Euler, may be cited. MERRIFIELD 1 gives 15-place values of 2" = £ P~" f°r 1 < « ^ 35. t This table is reproduced in GRAM 1 (p. 269). GLAISHER 20 gives 24-place values of 22* and of (1/A)22» for 2^2/z^80. The corresponding entries S" for n odd have been supplied by H. T. DAVIS 1, where 2" is given to 24 decimals for all integers n from 2 to 80. There are only 2 tables of the function ffm In LEGENDRE 1, 2P(x) is given to 6 decimal places for *^1229, except in LEGENDRE li, where x ^353. In GLAISHER 22, P(x) and its common logarithm are given to 7 decimals for x< 10 000. fs. Primes of special form As in the case of consecutive primes, lists of primes of special form often occur as arguments of tables giving further information about these numbers. Thus in giving primitive solutions of the binomial congruence xk = 1 (mod p) one needs to consider only those primes that are of the form kn+1. Lists of these primes therefore occur in tables cited under d4, especially in CUNNING- HAM 28-34, 38, 39, where lists of primes of the form kn+l, for n^ 17, are given up to p< 100 000, and for many larger values of « up to p< 10 000. These lists are sometimes useful in searching for small factors of numbers of the form ak-b". Other lists of primes of the form kn+1 are in GLAISHER 17 for /> = 4«-f-l <13 000, and KRAITCHIK 4 (p. 192-204) for /> = 512«+l<10 024 961. Other important special forms of primes are those linear forms associated with a given quadratic residue. Those primes p for which the Legendre symbol (D//>) has a given value (+1 or — 1) belong to certain linear forms depending [43]

f» DESCRIPTIVE SURVEY on D, tables of which are described under i2. Tables of "quadratic partitions" of primes p = xl — Dy* naturally extend over those primes p for which (D/p) = +l. Hence such tables (described under j2) give incidentally lists of these primes. In particular the tables of CUNNINGHAM 7, 36 give at a glance those primes p< 100 000 and 100 000 <p$ 125 683 respectively, for which the symbols (—!//>), ( — 2/p), ( —3//>) have given values, taken separately or to- gether. The factor stencils of D. N. LEHMER 3, 4 (described under g) give, in effect, all those primes g 48593 and ^ 55073 respectively for which (D/p) has a given value for | D\ <239, and | D\ <250 respectively. A rather special table relating to primes belonging to linear forms is due to DICKSON 1. This gives all sets of 3 primes which for a fixed value of «^10, are values of ain+bi, o2«+62, a3n+b3 for 64 selected sets of three such linear forms. Tables giving the number of primes belonging to given linear forms and less than certain limits date from SCHERK 1 (1833). This table gives the num- ber of primes belonging to each of the forms 4«+ 1 in each chiliad up to 50 000. GLAISHER 12 gives this information for each myriad between £-10* and k-10'+106 for k = 0,1, 2, 3, 6, 7, 8. These results are summarized in GLAISHER 10. GLAISHER 9 gives this information for k = 0, 1, and 2 only. CUNNINGHAM 14 gives for « = 4, 6, 8, 10, 12 the number of primes <10* of each of the forms nx+af (* = 0, 1, • • • ) for each on<n and prime to n. For the special form nx+1 and for n = 2k<60, and 15 higher values ^210, the number of primes — x of this form is given for x =10* and 10*. For « = 8/>, 100</><250, the same information is given for x =10' and 5-106. These re- sults extend those given in CUNNINGHAM 7. These numbers are compared with ir(x)/<t>(k'). The number of primes in each successive myriad up to 10' and be- longing to the form kn-\-l for all n from 1 to 30, for all even n from 30 to 60, and for 19 other values >60 is given in CUNNINGHAM 23. POLETTI 2 (p. 244-245) gives the number of primes > 5 of each of the 8 pos- sible forms 30n+r (r= 1, 7, 11, 13, 17, 19, 23, 29) in each of the 10 successive myriads beyond 10* for £ = 0, 5, 7, 9. Tables of the number of primes of each of the forms 6n+1, 10«+1, 10«±3 in the first and second 100 000 numbers, and of the form 4«+l and 8«+l in the first myriad appear in KRAITCHIK 4 (p. 15-16), where also is given the number of primes of the form 512«+l in each 100 000 numbers and in each million from 1 to 107. KRAITCHIK and HOPPENOT 1 give the number of primes of each possible form (modulo ni) in each chiliad between 10i2—10* and 10i» for w = 4, 6, 8, 10 and 12. The same information for the range 10i2 to 10^+104 is given in KRAITCHIK and HOPPENOT 1 and also in KRAITCHIK 12. Twin primes (p, p + 2), p>5, are of three sorts, according as />=10«+1, 10«+7 or 10«+9. The number of twin primes of each sort in the 100 000 numbers beyond 10* for k = 0, 7 and 9 is given in POLETTI 2 (p. 246). We turn now to lists of primes of the form a" ± 6" or prime factors of such [44]

DESCRIPTIVE SURVEY f2 numbers. These are in large part by-products of factor tables of numbers of this form (described under e2). Under this heading come lists of primes of the form / > = a2+62 already mentioned under the "quadratic partitions" tables of J2, to which section of the report the reader is again referred. The special case in which 6=1 is, how- ever, particularly interesting, and more extensive lists of these primes have been prepared. These date from EULER 2, who gave a list of all primes /> = a2 + l less than 2 250 000 as well as all values a < 1500 for which (a2+l)/fc is a prime for £ = 2,5, and 10. CUNNINGHAM 6 gives lists of all primes beyond 9-10* of the forms a'+l and (a2+l)/2 with a ^5000. KRAITCHIK 4 (p. 11) lists the 312 numbers a for which a2+l is a prime < 10'. WESTERN 1 gives the number of primes of the form a2 + l less than x for various values of x up to a; =225 000 000 as compared with Hardy's conjec- tured formula: .68641 Li(xi1*) Many lists of high primes dividing an + b" appear in Cunningham's Bi- nomial Factorisations. These may be given the following tabular description: form limit no. of primes v. pages **+! 225 -10" 4430 1 238-244 x*-l 225-10* 4884 1 245-252 x'-y3 10* 472 1 259-260 *+? 10i0 778 1 253-255,281-284 *6+! 10i0 1565 2 200-210 *•+/ 10i° 1065 1 256-257,261-264, 285-288 x7±/ 10'° 183 3 196-198,203 *"+/ 4-10i2 9 1 258 ««±y« 10i° 182 3 200-202 xi0+/° 10i0 87 2 211-212 xii±yii 10i0 42 5 119 *«+/* 10i0 20 1 258 xit±yi6 10i0 172 2 211-214 Some of these lists have been published separately as follows: form limit reference (a"-l)/(a-l) 16 000 000 CUNNINGHAM 6 a3—(a—I)3 1 000 000 CUNNINGHAM 17 a4+64, o8+68 10i° CUNNINGHAM 10 o'±66 10i0 CUNNINGHAM 13 oB+l 25 000 000 CUNNINGHAM 3 We now turn to lists of primes which are binomials other than of the cyclo- tomic form a" ±6" just considered. [45]

f: DESCRIPTIVE SURVEY Lists of primes represented by the binary quadratic form x* ± Uy2, in which x and y are also given, are listed under j2. However, we take this occasion to cite the list of 188 primes of the form *2+1848y2 lying between 10 000 000 and 10 100 000 of CUNNINGHAM and CULLEN 1, reproduced in CUNNINGHAM 36 (p. 74-76). Three tables have been published of large primes of the form £-2"+l. KRAITCHIK 4 (p. 53) gives 43 primes of the form £-2"+l between 2-10* and 10i2 with 3g£<100. This was later extended in KRAITCHIK 6 (p. 233-235) to include all such primes between 108 and 10i2 with £<1000. CUNNINGHAM 36 (p. 56-73) gives a list of primes of the form £-2" + l, 9g«^21 up to various high limits < 108. DINES 1 has lists of k and 5,6 ^ k ^ 10, for which 6*5 + 1 are primes for all 5 less than 100, and in some cases 400. Certain cases left in doubt have been dis- posed of by BEEGER 6. All primes of the form 2I3»5'+1<107 have been given by KRAITCHIK 4 (p. 53). The 184 sets (x, y, z) corresponding to these primes appear on p. 9-10. Poletti, Sturani and Gerardin have constructed by a sieve process factor tables up to high limits of numbers of the form A-n?-\-Bn-\-C (n=l, 2, • • • ) for different choices of A, B, C, from which they have extracted long lists of high primes. The actual primes are not always given, but instead the values of n for which the function An*+Bn+C is a prime are tabulated. The chief interest in such tables lies in the empirical information which they give con- cerning the distribution of primes of this form. Whether their number is finite or not is an unsolved problem. The first such table is due to POLETTI 2 (p. 249-255), and gives all primes of the form «2 — n— 1 up to 10 400 000. POLETTI 3 gives all primes between 10 018 201 and 24 123 061 of the form 5«2+5«+l. POLETTI and STURANI 2 list those n's for which either of the two numbers 2«2+2«+l is a prime < 250 000 000. A table is given of the number of primes in each 1000 terms of the series 2« + 1, «2 + n ± 1, 2«2 + 2n + 1 up to «=11 000. PoLETfl 4 gives all primes <121 millions of the form «2+«±l with a table of their distribution. POLETTI 5 contains a table of nearly 17 200 primes, arranged in increasing order, and extracted from the series «2+«±l, 2«2+2«± 1, «2+«+41, 41«2+«+1, 6«2+6«+31. In attempting to construct quadratic functions containing more primes than Euler's E(n) = n*+n+41, Lehmer and Beeger have suggested L(n) = «* + n + 19 421, B'(n) = n* + n + 27 941, B"(n) = «»+ « + 72 491. Poletti has investigated the frequency of primes in all four functions and his results are given in BEEGER 7 (p. 50), where is found the number of primes represented by each function for n<x, a;= 1000(1000) 10 000. These facts [46]

DESCRIPTIVE SURVEY would suggest that B'(n) and B"(n) are more, and L(n) less, fruitful sources of primes than £(«). POLETTI 7 gives all primes represented by L(n), B'(n), and B"(n) between 10' and 2 • 107. POLETTI 6 contains primes represented by about 200 different quadratic functions An*+Bn+C, 107</><3-109. GERARDIN 6 contains over 2000 values of « for which An*+Bn+C is a prime > 107 for the following polynomials and ranges of n 2n2 + 2n + 1 for 15800 g « g 23239 101«2 + 20« + 1 for 315 g « ^ 1542 122«2 + 22« + 1 for 286 ^ « g 1369 10«2 ± 6« + 1 for 3161 g « ^ 4620 26«* ± 10« + 1 for 1216 g n £ 1774. High primes represented by the trinomial 2" + 2I+l for x<a<27 and many more pairs (x, a) are given in CUNNINGHAM and WOODALL 8. KRAITCHIK 9 gives a list of the 94 largest primes known, and in KRAITCHIK 10 is a list of 161 primes exceeding 10i2. g. TABLES FOR FACILITATING FACTORING AND IDENTIFYING PRIMES Besides factor tables and lists of primes there are tables available for the easy application of known methods of factoring and tests for primality. For instance, the method of factoring depending on quadratic residues, as described by Legendre, makes use of certain lists of linear forms or "linear divisors" of quadratic forms x*-Dy*. These are described in detail under is. To render this method still more effective, D. N. LEHMER 3, 4 devised the factor stencils. These give in place of the linear forms an actual list of the primes belonging to these forms. More particularly, in D. N. LEHMER 3, all the primes ^48593 belonging to linear forms dividing x* — Dy*, or what is the same thing, all the primes having D for a quadratic residue are given for | D\ <239. Actually the primes for each D are not printed but are represented by holes punched in a sheet of paper. Since the primes for D = k*Di are the same as those for Di, only the Z>'s without square factors, of which there are 195, need be considered. Each of the 195 sheets is ruled in 5000 square cells, 25 to the square inch, 50 columns by 100 rows. A cell, by virtue of its row and column number, represents one of the first 5000 primes p, and if (D/p) = +1, it is punched out. All factors ^ 48593 of a given number TV havingD as a quadratic residue are among those primes whose corresponding cells are punched out of the stencil for D. Having found a suitable number of quadratic residues D of N, the mere superposition of the corresponding stencils reveals only a few open holes, among which the factors ^ 48593 of N must then lie. In this way, the discovery of all factors of N (if any) below this limit is reduced to the dis- [47]

g DESCRIPTIVE SURVEY covery of a certain number, not exceeding ten or a dozen, of quadratic residues less than 239 in absolute value. Thus the device will handle completely all numbers less than the square of 48611, i.e., 2 363 029 321, and, of course, can be used in factoring much larger numbers. In D. N. LEHMER 4, the same method is used in a different form. Here use is made of Hollerith cards of 80 columns and 10 rows. For each D there are 7 cards of different color, each color dealing with 800 primes. By superposing cards of the same color for different D's, all prime factors of N less than 55 079 may be found. Besides extending the number of primes from 5000 to 5600 Elder has extended the range to | D\ <250. The new edition has been entirely recomputed by Elder and, in addition to being more reliable, is more con- venient to use than the old, especially when N is comparatively small, so that only two or three colors are needed. The tables of D. H. LEHMER 6 and POULET 4 serve to test for primality any number n below 108 in 20 to 25 minutes at most. These tables give lists of composite numbers n for which 2"= 2 (mod «) together with a factor of n. The table of Lehmer is restricted to contain only such entries «> 107 as have their least factor >313, while the more extensive table of Poulet contains all possible n's up to 108. In using the Poulet table one notes first if the given number n is in the table. If so, a factor of n is given. If not, then 2" = 2 (mod n) is a necessary and sufficient condition for primality of «. Whether this congru- ence holds or not can be decided quickly by a method of successive squarings described in D. H. LEHMER 6. In using Lehmer's table, there is the additional possibility that n contains a small factor ^313. If so, this factor can be quickly discovered by a greatest common divisor process therein described. Factorization methods, depending upon the representation of the given number by quadratic forms such as x* — y3, x*+y*, x* — Dy'L, are greatly facili- tated by the use of certain tables cited and described under ii. The list of 65 Idoneal numbers D (such that the unique representation of » by x*+Dy* insures the primality of n) is given for example in MATHEWS 1 and CUNNINGHAM 36 (p. ii). SEELHOFF 1 contains lists of binary quadratic forms especially devised for factorization purposes. Tables giving the final digits of squares are sometimes used in factoring small numbers. These are cited under ii and is. A table of this sort, especially designed for representing n by x*±y* with x<y<2500, is given in KULIK. 1 (p. 408-418). A table of reciprocals of primes < 10 000 to 8 significant figures with differ- ences is given in PETERS, LODGE and TERNOUTH, GIFFORD 1. This is intended to replace trial divisions by a series of multiplications by the given number, and is useful when the available computing machine has no automatic division or no keyboard. The detailed account of the application of commercial and specially made [48]

DESCRIPTIVE SURVEY g-h computing devices to the problem of factoring numbers and identifying primes will appear in another report of the Committee: Z. h. TABLES OF SOLUTIONS OF LINEAR DIOPHANTINE EQUATIONS AND CONGRUENCES The solution of the general linear Diophantine equation aixi + atxt + • • • + anxn = k depends ultimately upon the solution of (1) ax + by = c and tables of solutions of such equations with more than 2 unknowns are non- existent. A solution (x, y) of (1) gives at once a solution x of the linear congru- ence (2) ax = c (mod b) and conversely, a solution of (2) gives a solution of (1) with y=(c—ax)/b. The equation (1), if it has a solution, can be reduced by cancelling common factors of a and b to the case in which a and b are coprime. All solutions (x, y) of (1) are then given by the formulas x = kb + £c y = — ka + rjc, where k is any integer, and (£ , TJ) is any solution of (3) a£ + br, = 1. Hence it is sufficient to tabulate a solution of (3) or of the congruence (4) <z£ = 1 (mod 6). CRELLE 3 gives a solution of (3) for each coprime pair (a, 6) with A similar table by CUNNINGHAM 36 extends to o<100, 6<100. Tables of solutions of the linear congruence (4) may be found in WERTHEIM 5, KRAITCHIK 4 (p. 27), and CUNNINGHAM 36. In these tables b is taken as a prime p, the composite case being readily reducible to this case. In Wertheim's table a<p< 100. It is even possible to restrict a to be a prime, and this is done in Kraitchik's table where a, b< 100, and are both primes. Cunningham's table (p. 158-161) gives for each prime /><100 solutions of both congruences a£= + 1 (mod p) for every a<p. KRAITCHIK 4 (p. 69) has a table for the combination of two linear congru- ences, whose moduli are 2" and 5". In fact the two congruences [49]

h-ii DESCRIPTIVE SURVEY N = rt (mod 2") N = rt (mod 5") give when combined N = Atrt + Atrt (mod 10"). The coefficients At and At, are tabulated for «g 16. For the combination of many linear forms, a problem which arises in many different ways, graphical and mechanical methods are available. These are dis- cussed in another report of this Committee (Z). A special table due to J. L. BELL 1, useful in checking Bernoulli numbers , gives for each « ^ 62 a solution (an, bn) of the congruence anN ,+,„-i = bJDy+^-i (mod q), where q is any odd prime not in the set of excluded primes there listed. i. CONGRUENCES or THE SECOND DEGREE ii . Solutions of quadratic congruences The general quadratic congruence in one unknown may be reduced by a linear substitution to one of the form (1) x* = D (mod m). When m is not too large, this congruence, when possible, is easily solvedi. Nevertheless, it is very convenient in many applications to have these solu- tions tabulated. Existing tables are of two sorts: according as m is a power of 10, or a prime (or prime power). Tables of the first sort occur in tables of the endings of squares. KULIK 1 gives for each possible D, the two solutions of *2ssD (mod 104), which are < 2500 from which all solutions may be discovered. Similar tables for the moduli 103 and 104 occur in CUNNINGHAM 36 (p. 90-92). Tables of the second sort date from EULER 2, who gave solutions +x of (2) x* + 1 s 0 (mod P") (a ^ 1) for all primes p = 4k+l up to p"<2000. A table of solutions of (2) with a= 1, and /> = 4£+l<1000 is given in KRAITCHIK 4 (p. 46) and for /><100 000 in CUNNINGHAM 28, 29. The quadratic residue tables of GERARDIN 4 and CUNNINGHAM 36 give solutions ±x of (1) with m = p, for all possible D (mod p) and for />< 100. The latter table contains in addition solutions of (1) for m = p"£ 125, («>1). There are several very useful tables of solutions of quadratic congruences in two unknowns. The first of these is due to GAUSS 10 and gives all solutions (x, y) (mod />) of the congruence fx* + gy* = A (mod p) i Especially if one uses the new stencil device of ROBINSON 1. [50]

DESCRIPTIVE SURVEY ii for all possible congruences of this sort with p^23. KULIK 1 gives solutions x of the congruence ** ± y2 = N (mod 104). That is to say, the last four digits of possible numbers x in the equation N = x*±y* are given for all possible four-figure endings of N. A similar table for 3-digit endings is given in BIDDLE 1. KRAITCHIK 3 (p. 187-199) gives tables of all solutions a, b, x, y, z, t of the congruences *2 - y* = N (mod />"), a2 + 62 m N (mod />"), z2 + w2 = N (mod p") and P+nv* = N (mod p") for all possible N (mod />"), where r is any quadratic residue, and n any quadratic non-residue (mod pa) for all primes /><50, and all />"^128, except 121. An abridged table (p. 200-204) gives solutions x of the congruence (3) ** + Dy* = N (mod /><") for all possible D and for N = 1 and n (mod £"), where « is the least non-residue (mod />"), for p< 100, and for all powers of 2, 3, 5, 7, 11 up to 2i2, 3«, 54, 72 and II2. A short table showing all solutions x of (3) with D= — 1 in case certain numbers R are known to be quadratic residues of N occurs in KRAITCHIK 4 (p. 87). The moduli considered are p" = S, 16, 32, 3, 5, 7, 11 and 13, while the values of R are — 1 and ± 2, when p is even, and (— l/p)p, when p is odd. A more complete table of the solutions of (3) with D— — 1 occurs in KRAITCHIK 6. Here are found the solutions x for all possible N and for all primes p^67. The table is in two parts, thus separating the two cases (N/p)=+l. In case (N/p) = -\-l, half the solutions x are impossible if it is known that (—l/p)p is a quadratic residue of A'. CUNNINGHAM 36 (p. 103-123) gives, for all possible N, solutions x of (3) for D= -1,1, 2, 3, for all />g41, and />"g64 (a> 1), as well as for the modulus 100. D. H. LEHMER 8 gives, in effect, all solutions x of a*2 + bx + c = y2 (mod p") for all possible a, b, c, (mod p") and for all p"^ 128 with the exception of 125 and 127. All these tables are, of course, designed for the application of Gauss' method of exclusion and serve to reduce such problems as the representation of a number by a given binary quadratic form to the mere combination of linear forms, and thus to make applicable a certain graphical and mechanical technique fully described under another report of this Committee: Z. [51]

i2 DESCRIPTIVE SURVEY i». Quadratic residues and characters and their distribution There are many small tables of quadratic residues giving for the first few primes p the positive quadratic residues of p arranged in order of their size. The more extensive of these may be described as follows: BUTTEL 1 gives for each p^ 101, the list of its quadratic residues and non- residues. FROLOV 1 gives quadratic residues for all p^97, omitting, for p^23, those residues which are actual squares. CUNNINGHAM 36 (p. 100-102) gives quadratic residues and non-residues for all primes />^131. KRAITCHIK 3 (p. 205-207) gives quadratic residues for all p < 200. CUNNINGHAM 36 (p. 93-95) gives lists of residues (mod p") for p< 100, and p"^ 169. These are arranged in the order of their least positive square roots. Since the even powers of a primitive root of p" are the quadratic residues of p", while the odd powers are the quadratic non-residues, a table of powers of a primitive root gives in particular a table of residues and non-residues. Such tables were cited and described under ds. Quadratic residues and non- residues for p"< 1000 are thus obtainable from JACOBI 2. There are several tables of quadratic residues modulo 10*. These are usu- ally described as tables of "square endings," since they give the possible last k digits of squares. These are of two kinds: those which list all the actual end- ings in order of magnitude, and those tables which enable the user to decide at a glance whether a given ending is a square ending or not. A list of all 159 three-digit square endings appears in SCHADY 1. KULIK 1, SCHADY 1, and THEBAULT 1 list all the 1044 four-digit square endings. In Schady's table with each four-digit ending are given all possible fifth digits. Thus the entries • 2489 and #4676, for example, indicate respectively that any digit may precede 2489, while only even digits may precede 4676. CUNNINGHAM 1 has a one page table showing at a glance whether a pro- posed 1, 2, 3, or 4-digit ending is a square ending or not. This table is repro- duced in CUNNINGHAM 36 (p. 89). A similar table of three-digit square endings to the base twelve, due to Terry, appears in E. T. LEHMER 2. A few tables give the values of the Legendre symbol (a/b) of quadratic character. GAUSS 1 gives the value of (a/q) for every odd prime q< 100, and for every prime a< 100, as well as a= — 1. This table is extended in GAUSS 4 to <7^503 and a < 1000. In both these tables a dash indicates either that (a/q) = +1 or that a = q, while the absence of any entry indicates that (a/q) = -1. A small table in WERTHEIM 5 gives (p/q) for all p< 100 and q< 100, and is intended to give a graphic representation of the Law of Reciprocity. A. A. BENNETT 2 gives for all odd primes />f£317 and for all positive num- bers n<p, the value of x in («//>) = (—1)*. That is, the table gives * = 0 or x= 1 according as n is or is not a quadratic residue of p. D. N. LEHMER 3,4 give the values of (a/q) for all q£ 48 593 and q = 55 073 [52]

DESCRIPTIVE SURVEY i2-is and for | a| < 239, and | o| < 250 respectively. In fact in the stencil (or stencils) for a the «th cell is punched out or not according as a is or is not a quadratic residue of the «th prime. Finally four tables relating to the distribution of quadratic residues may be cited. GAUSS 3 gives the number of quadratic residues in each of the r intervals of length p/r of the numbers from 1 to p for the following values of r and the corresponding ranges of p: r = 4, p = 4« + 1 < 400 r = &, p < 400 r = 12, p = 4« + 1 < 275. For r = 4 the actual number of quadratic residues in each quadrant is not given, but follows at once from the given values of m by the formula (p— 1 — (— l)*4m)/8, where k=l, 2, 3, 4, is the number of quadrant. A. A. BENNETT 3 gives the number of consecutive quadratic residues and non-residues for all primes p^3l7. KRAITCHIK 4 (p. 46) gives for each p ^ 47 the least non-square N" of the form 8«+l which is a residue of all odd primes ^p. This table is extended to p^61 in D. H. LEHMER 1. D. H. LEHMER 7 gives for each r < 28, the positive integer Nr = 8«+3 such that — Nr is a quadratic non-residue of all odd primes not exceeding the rth prime pr. Also Nn>5-10». i> Linear forms dividing x* — Dy~ The term linear divisor of a;2 —Zty2 is due to Legendre, who published the first real tables of such forms. These linear forms are nothing more nor less than the arithmetic progressions in which lie all primes p for which (D/p) = +1, these being the only primes which will divide numbers of the form x* — Dy*, in which x is prime to Dy. The linear forms dividing a;2 — WDiy* are clearly those dividing x* — Ay2, so that tables of these forms deal only with those D's which have no square factor > 1. In general we may speak of the linear di- visors of any binary quadratic form / as the set of arithmetic progressions to which any prime factor of a number properly represented by/must belong. The tables of LEGENDRE 1 list the linear forms for each of the reduced (classi- cal) quadratic forms of determinant D for — 79^D^ 106. If all such forms for a fixed D are taken together we obtain the set of linear divisors of x* — Dy*. Legendre's tables are the only ones in which this separation of the linear di- visors of xl-Dy* is attempted. The tables of CHEBYSHEV 1 really give a part of this information, however; in fact for each D<33 are given the possible forms (mod 4D) of those numbers which are properly represented by the forms *2 — Dy* or Zty2 — x*. [53]

ia-j DESCRIPTIVE SURVEY The tables of Legendre were reproduced and extended somewhat by CHEBYSHEV 2, who gave all linear forms dividing x* — Dy* for | D\ ^101, carrying over most of the many errors in Legendre's table. Chebyshev's table is reproduced in CAHEN 1 with more errors. KRAITCHIK 3 published a table of linear forms for \D\ <200. When D>0, the form 4D+x is always accompanied by the form 4Z>—x so that only those x's which are <2D are given with the understanding that both +x are to be taken. This table is extended in KRAITCHIK 4 where 200 < | D\ <250. These are the only large tables of linear divisors published. Unfortunately all contain numerous errors. D. N. LEHMER 5 extends to \D\ =300 and was used by him and Elder in the preparation of the factor stencils (D. N. LEHMER 3,4). Three small tables of linear forms may be cited. LUCAS 4 gives the linear forms dividing x* — Dy* for | D\ <30. WERTHEIM 5 has a similar table for \D\ <23. The table of CAHEN 3 gives linear forms mx+r (m = 2D or 4D) dividing x* — Dy* for | D\ <50. This table is peculiar in that the r's are chosen to be absolutely least (mod m) and are arranged according to increasing ab- solute values. CUNNINGHAM 36 gives a small table of linear divisors and non-divisors of x* — Dy*. That is to say, the forms of primes for which (£//>) =+1 and (D/p) = -1 are listed for | D\ < 12. The tables of LEVANEN 2 give for 62 se- lected binary quadratic forms of negative determinant >—385 the corre- sponding linear divisors. j. DIOPHANTINE EQUATIONS OF THE SECOND DEGREE The solution of a large number of interesting problems in the theory of numbers, algebra and geometry may be made to depend on Diophantine or "indeterminate" equations. Problems resulting in equations which are of the second degree are particularly interesting, and solutions of such equations have been subjects of a great many tables. These tables fall naturally into three classes: those giving information about the equations (1) ** - Dy* = v, v= ±1,± 4, where D is a positive non-square integer, those dealing with the more general equation (2) x2 - Dyl = N, and those dealing with quadratic equations involving more than two unknowns such as o;2+y2 = z2. The equations (1) have long been recognized as funda- mental and are known as Pell equations, although the term "Pell equation" is sometimes restricted to the case of <r= 1, and sometimes generalized to cover (2). The equations (1) and those equations (2) for which N<^/D are inti- [54]

DESCRIPTIVE SURVEY j-ji mately connected with the continued fraction expansion of \/~D, tables of which are cited and described under m. ji. The Pell equations x* — Z7y2 = <r, <r=±l, ±4 Although these equations, especially with <r = 1, have a very long history, the first tables of their solutions (x, y) were given by Euler. Since Euler's time the importance of the Pell equation to the theory of binary quadratic forms and of quadratic fields K(\/D) has been fully realized and Euler's original tables have been greatly extended. The first sizable table of the solutions of a;2 - Dy* = + 1 appeared in LEGENDRE 1 in 1798. The table extends to non-square D'sg 1003, except in the second edition of LEGENDRE 1, where D^ 135. The fundamental solution of (3) *2 - Dy* = - 1 is given whenever possible, otherwise of (4) x* - Dy* = + 1. A glance at the final digits of x, y and D tells which of these two equations is satisfied by the given x, y. This table for D^ 1003 is reproduced in LEGENDRE Table 1 of DEGEN 1 gives solutions of (4) for Dg 1000. Table 2 gives solu- tions of (3) for all possible D not of the form «2 + l, in which case the funda- mental solution is obviously the trivial one (x, y) = (n, 1). Unlike Legendre's table, Degen's Table 1 contains also the elements of the continued fraction for\/Z>. CAYLEY 6 may be considered as a continuation of Degen's Table 1 for 1 000 <Dg 1500, except that when (3) has a solution, that solution is given in place of the solution of (4) as indicated by an asterisk. This table was com- puted by Bickmore. WHITFORD 1 gives for 1500 <D^ 1700 solutions of (4) and also of (3) if possible, the latter being easily distinguished by their relative smallness. The corresponding continued fraction developments are given separately for These are the main published tables of the solutions of (3) and (4). D. H. LEHMER 9 gives these solutions for 1 700 < D ^ 2000. An announced table, GERARDIN 7, up to Z? = 3000, is probably incomplete. There are 6 small tables giving the solutions of (3) and (4) for non-square D's <100. These are CAYLEY 6 (p. 75-80), WERTHEIM 5, CUNNINGHAM 7, PERRON 1, CAHEN 3 and KRAITCHIK 4 (p. 48-50). The tables of Cayley and Perron give in addition the continued fractions for \/D. The tables of Cayley [55]

ji DESCRIPTIVE SURVEY and Cunningham give solutions of (4) and also of (3) when possible. The others give solutions of (3) when possible, and otherwise of (4). A special table of NIELSEN 1 gives solutions of (4) for those D's of the form a2+62 for which the expansion of the continued fraction for \/Z> has an odd period with D< 1500. INCE 1 gives solutions of (3) or (4) with D^k*Di whenever (5) *2 - Dy* = + 4 has no coprime solutions (x, y) for D<2025. The omission of the solutions of (4) when (3) has a solution (x, y) is not important since the fundamental solution of (4) is in that case (2*2+l, 2xy). The problem of telling "in advance" whether or not (3) is solvable has never been satisfactorily solved. Three small tables give information on this question. SEELING 3 gives the list of all those D's <7000 for which (3) is solvable. A similar list only for D^1021 appears in KRAITCHIK 4 (p. 46). NAGELL 1 gives the number B(n) of D's not exceeding n for which (3) has a solution together with the number A(n) of non-squares ^« which are sums of two coprime squares, and also the difference A(n) — B(n) for «= 100, 500, 1000(1000)10 000. Thus far we have been speaking of fundamental (or least positive) solu- tions of (3) and (4). If (xi, yi) is such a solution of (4), the successive multiple solutions of (4) are given by (*„, yn), where *. + x/Fy. = (*i + x/FyO" (« = l, 2, • • • ) and are connected by the second order recursion formulas yn+i = If, on the other hand, (xi, yi) is the fundamental solution of (3), then (.-c2n, y2n) and (xtn+i, ytn+i) are all the solutions of (4) and (3) respectively. Only two tables give multiple solutions of (3) and (4). CUNNINGHAM 7 gives the first multiple solutions of both equations for Z>^20. A table of yn in a£— 2y* = +1 is given for «^30 in D. H. LEHMER 2. Four tables give solutions of (5) and of (6) *2 - Dy* = - 4. These are used in constructing automorphs of indefinite binary quadratic forms, or the units of the real quadratic field K(\/D). Equation (5) is always possible since a solution is (2x, 2y) where (x, y) is a solution of (4) and by the same device (6) may be solved when (3) is pos- sible. These solutions are uninteresting, however. For some D's (5) and (6) have no coprime solutions. In fact it is necessary that D = 0, 4, or 5 (mod 8). [56]

DESCRIPTIVE SURVEY ji-j2 The first two cases are uninteresting since, if D = 4 A, a solution (x, y) of (5) or (6) implies and is implied by the solution (x/2, y) of (4) or (3) respectively (with D=Di). Therefore tables of the solutions of (5) and (6) are concerned solely with D = 5 (mod 8). The first such table is ARNDT 2 which gives solutions of (6) when possible, otherwise of (5) if possible for D^ 1005. A similar table for D^997 is due to CAYLEY 1. Solutions of (5) and (6) are given whenever possible with 1005 <D^ 1997 in WHITFORD 2. INCE 1 gives solutions of (5) or (6) whenever possible for IK 2025 as units of the field K(\/D). If (6) has a fundamental solution (x, y) (for D = 5 (mod 8)) the solutions of (5), (3) and (4) are respectively (*2 + 2, xy), ((*3 + 3*)/2, y(*2 and ((x' + 6*4 + 9x* + 2)/2, y(x* + !)(«• + 3*)/2). If (5) has a fundamental solution (x, y) with D = 5 (mod 8), then that of (4) is ((x3 — 3*)/2, y(x*— 1)/2). Hence these tables may be used to find solutions of (3) and (4) if necessary. Many writers have suggested methods for solving Pell equations, which avoid the explicit use of continued fractions. It is safe to say however that those methods which are practical for solving isolated equations like, for ex- ample, x*— 1141y2= 1 in which x and y have 28 and 26 digits, are equivalent to the continued fraction method. The application of the continued fraction algorithm by modern mechanical methods will be treated in another report of the Committee: Z. J2. Other equations of the form x*±Dy* = + N Besides the tables of the Pell equations, there are tables of solutions of the equation (1) x3 - Dy* = + N (N 7* 1, 4). These are of two kinds, according as D is positive or negative. In tables of the former kind, N is comparatively small. Those of the latter kind extend over prime values of AT up to high limits for a very few negative values of D. An important special case of (1) for D>0 is that in which N<\/rD. In this case the continued fraction development of ^/D will disclose whether or not (1) is possible. In fact, by a theorem of Lagrange, ± N will appear in the denominator of a complete quotient (when these are taken with alternating signs) if and only if (1) is possible, and the corresponding convergent x/y will be the solution of (1). Hence tables of the continued fraction developments of \/I> (cited and described under m) give information for solving (1) in this case. The table of KRAITCHIK 4 gives the least positive solution (x, y) of (1) for N<VD, and for IK 100. CAYLEY 6 gives for each non-square IK 100 the [57]

jt DESCRIPTIVE SURVEY least positive solution of (1), where + N are the denominators of the complete quotients in the continued fraction of \ff) taken with alternating signs, so that N<2-\/D. For larger values of N the continued fraction method is no longer applicable. There remains however the multiplicative property implied by the formula (xi — Dyi)(x2 — Dyt) = (xixt ± DyiytY — D(xiyi + «2yi)2 known to Brahmagupta. This product to which Cunningham has given the descriptive name "conformal multiplication" enables one to derive from solu- tions of • o 2 '* xi — Dyi = NI and xa — Dyi = NI a pair of solutions of In particular from the infinity of multiple solutions of 2 2 x> — Dys = we can derive an unlimited number of solutions of (1) from a single initial solution. Conformal multiplication is the basis of the extensive tables of solu- tions of (1) prepared by Nielsen. His largest table is NIELSEN 4 (p. 1-195) which gives small solutions of (1) for AT<1000 and for 2^£)^102, and for several larger D's up to 401. NIELSEN 2 contains a smaller table for N < 1000 and for D = 34, 79, 82 and 101, and certain products of these numbers by squares. NIELSEN 3 gives similar results for D = 30, 41, 51 and 130. Information about the solvability of (1) is given in NIELSEN 5, which lists for each A^I0, all those D's <10 000 for which (1) has a solution. With each D is given a solution (t, u) of /2 — Nu2 = D. A small table of solutions of the equation (1) appears in OETTINGER 1, where fundamental and five multiple solutions are given for D^20, and N=l, 2, • • • , 10,3*, 5*, 7* with l^fc^4. Conformal multiplication is also applicable to equations of the type (2) Ax* - By* = N (AB = D), which become of type (1) on multiplication by A. Three tables of solutions of such equations have been given. ARNDT 1 gives solutions (x, y) of Ax* - By*= 2 (AB = D) when possible, otherwise of Ax* - By* = 1 [58]

DESCRIPTIVE SURVEY j2 for all D^I00S which have no square factor, nor are primes or doubles of primes of the form 4«+l. That pair of factors (A, B) of D is chosen which gives the smallest solution (x, y). NIELSEN 4 (p. 199-234) gives small solutions (x, y) of (2) with AT<1000 and AB = D ranging over composite numbers from 10 to 346 with some gaps. This is an extension of the smaller table in NIELSEN 3, where ^45 = 30, 41, 51 and 130, mentioned above. Turning now to tables of the second kind in which D is negative, we find that in almost all cases W is a prime. This is permissible in view of conformal multiplication. These tables give the solutions (x, y) of (3) & + y2 = p p = 4m + 1 (4) x* + 2y* = p p = 8m + 1, 3 (5) x* + 3y2 = p p = (m + 1 (6) *2 + 27y2 = 4/> p = (m+l. These representations or "quadratic partitions" (to use Cunningham's termi- nology) of p are possible if and only if p is of the linear form (or forms) indi- cated, and when possible, are essentially unique (in (3) it is customary to insist that y be even). These quadratic partitions are chiefly used in determin- ing the character (a//>)n for « = 3, 4, 8, 16 for small bases a, especially o=2, and have been a great aid as a preliminary to finding the exponent of a (mod p). The distribution of quadratic residues (mod p), and certain class number and cyclotomic problems also depend upon these partitions. The first extensive tables of quadratic partitions were published by JACOBI 3 in 1846, and were computed by Zornow and Struve. These give the partitions (3) for p£ 11981, (4) for />g5953 and (5) for p^ 12 007. A table of the parti- tions of (3) for p^ 10 529 occurs in KULIK 1. REUSCHLE 1 gave the partitions (3) and (4) for p^ 12 377 and for all those primes p from 12 401 to 25 000 of which 10 is a biquadratic residue. The parti- tion (5) is given for p ^ 13 669 and for all those primes from 13 669 to 50 000 of which 10 is a cubic residue. The partition (6) is given for p£ 5743. CUNNINGHAM 7 gives all four partitions for /><100 000. This table is ex- tended from 100 000 to 125 683 in CUNNINGHAM 36, where also are found several other tables giving quadratic partitions of primes of special form as follows. On p. 56-69 are given the partitions (3), (4) and if possible (5) of all primes of the form 2*a>+1, k ^ 9 up to high limits L depending on k as follows: k 9 10 11 12 13 14 L I0» 1.25- 10" 2.5- 10» 5-10" 8.5- 10» 9- 10" On p. 70-73 are given the partitions (3) and if possible (5) of all primes p of the form 2*u+l, k^9, 107</><108. These tables were used in factoring Fermat's numbers 2*"-\-l. [59]

jr-js DESCRIPTIVE SURVEY A similar table occurs in KRAITCHIK 4 (p. 192-204) where the partition (3) and if possible (4) and (5) are given for all primes /> = 2«*+1^10 024 961. As a matter of fact a, b, c, are given in the equations x* + (4a)2 = p, x* + 2(46)* = p, x* + 3(4c)2 = p. CUNNINGHAM 36 also gives partitions (3) and (4) whenever possible of all primes between 108 and 108+103. The representation of all possible primes p by the idoneal form p = x* + 1848y2 for 107 < p < 107 + 106 appears on p. 74-76. Actually (x, 2y) is tabulated. All solutions (x, y) are given of x* + y2 = «2 and x* + 3y* = «2 for all possible «<3000 together with the corresponding partition of n when n is composite (p. 77-87). Other tables of quadratic partitions different from (3), (4), (5) and (6) may be given the following tabular description. These give the least solutions (t, u) of t* - Du* = kp for the values of k and D indicated, and for all possible primes p not exceeding the limit L: Reference CUNNINGHAM 7 TANNER 2 CUNNINGHAM 7 D » L 2 1 25 000 3 1 10 000 5 4 10 000 5 4 10 000 -5, ±6, ±7, +10, 11 1 10 000 11 4 10 000 ±13, ±14 1,2 1 000 ±15, ±17 1,9 1 000 ±19 1,4 1 000 2 1 25 000. BICKMORE and WESTERN 1 In the last mentioned table, /> is restricted to the form 8«+l, and t to the form 4a;+l. This paper also contains a small table giving all the representations of each possible number less than 1000 as the sum of two squares. js. Equations in more than 2 unknowns, rational triangles All but a few tables of this sort have to do with rational triangles, and most of these are lists of rational right triangles. Many such lists have been given in obscure places, and have been superseded by larger lists in more readily available sources. [60]

DESCRIPTIVE SURVEY ji It is well known that the sides of all integral right triangles are given by the formulas a = 2mn, b = m* — n*, h = mt + «*, where It is the hypotenuse, and where m and n are integer parameters. If one wishes to exclude the less interesting non-primitive right triangles in which a, b, and h have a common factor one restricts m and n to be coprime, and to be of different parity. There remains only the question of arranging the list of triangles thus generated. Two extensive tables arranged according to values of m and n may be cited. The first, BRETSCHNEIDER 1 gives all primitive triangles generated with n<m^25. With each triangle is given also its area and its acute angles to the nearest 10th of a second. A more extensive list is given in MARTIN 1 (p. 301- 308). This contains864 triangles arranged according tow and« with n<m^65, and is the largest list of rational triangles ever published. With each triangle is given its area. An old list of 200 right triangles was published by SCHULZE 1 in 1778. These are arranged according to the size of the smallest angle of the triangle. The tangent of half this angle is made to assume every rational value between 0 and 1 whose denominator does not exceed 25. The arrangement most frequently used is according to increasing values of the hypotenuse. Such tables for h ^ 1109 are given in SAORGIO 1 and SANG 1. The latter gives also the angles to within 1/100 of a second. The most ex- tensive tables with this arrangement are found in MARTIN 2 and CUNNINGHAM 36. Both these tables give all 477 primitive triangles whose hypotenuses h do not exceed 3000. The Cunningham table is in two parts in which h is respec- tively prime and composite. This same arrangement is used in KRAITCHIK 6 which extends only to &<1000 however. CUNNINGHAM 28 (p. 190-194) has another table complete to A = 2441 with 28 other h's <3000. A table of TEBAY 1 (p. 111-112) gives a list of right triangles arranged ac- cording to their area A up to A =934 800. This table is reproduced in HALSTED 1 (p. 147-149) with nine additions. BAHIER 1 (p. 255-258) gives a list of all primitive triangles one of whose legs has a given value < 300. A table of KRISHNASWAMI 1 is arranged according to semi-perimeters and lists all primitive right triangles whose semi-perimeters do not exceed 5000. References to other tables of right triangles, mostly small and obscure, are given in MARTIN 2. Several small tables giving special right triangles may be mentioned. MARTIN 1 (p. 322-323) gives 40 right triangles whose legs are consecutive integers and 313 triangles whose hypotenuses exceed one leg by 1 or by 2. BAHIER 1 (p. 260-261) gives the values of certain recurring series for use in solving such problems. There is also given (p. 259) the list of 67 triangles one of [61]

j3-k DESCRIPTIVE SURVEY whose sides is 840. WOEPCKE 1 has given for each of the 33 primitive right triangles with A<205, 12 associated congruent numbers. MARTIN 2 contains many sets of right triangles with special properties too numerous to mention. There are a few tables of rational triangles which are not right triangles. TEBAY 1 (p. 113-115) lists 237 rational triangles arranged according to area, the greatest area being 46 410. This table is reproduced in HALSTED 1 (p. 167- 170) and amplified in MARTIN 1 by 168 additions. SIMERKA 1 lists all 173 rational triangles with sides < 100. There is also given the area, the tangents of the half angles and the coordinates of the vertices of each of these triangles. SANG 1 gives the list of 137 triangles, one of whose angles is 120°, and whose largest side is less than 1000. CORPUT 1 has listed all primitive rational isosceles triangles (a, a, c) of altitude h, and base angles A, arranged according to a from a = 25 to a < 160 000. The table gives for each triangle the values of \/a, c/2, A/24, tan G4/4), Vo cos (A/2) and Va sin 04/2). PARADINE 1 gives 1120 triangles, each having integral sides and one integral median. Finally we cite tables of solutions of diophantine equations of the second degree in more than 2 unknowns which do not refer to triangles. CUNNINGHAM 28 (p. 185-189, 194) gave solutions of x* = y'! — 3z* arranged according to y complete to y^1591 with 99 more y's <2774. EELLS 1 has tabulated 125 solutions of x*+y*+z* = a* for various a's from 13 to 88 621. JOFFE 1 has given a complete list of 347 solutions of this equation for Ka^ 100. BISCONCINI 1 has given 50 solutions of 2.2,2 1 xI + X2 + x> = xt. k. NON-BINOMIAL CONGRUENCES OF DEGREE ^3 Very few tables exist in this category. The term non-binomial is used here in its technical rather than its strict sense. That is to say, tables of solutions of such congruences as (xi* - l)/(*4 - 1) = x* + x* + 1 = 0 (mod />) have been classified under the binomial congruences (d4) in spite of the fact that it is a trinomial congruence of the eighth degree. We may cite here however the table of REUSCHLE 3 which gives not only the primitive solutions of the congruence x" - 1 = 0 (mod p), but also the solutions of F(x) = 0 (mod p) where F (x) are the polynomials whose roots are the several sets of "periods" [62]

DESCRIPTIVE SURVEY k-1 of the «th roots of unity (described more fully under o) for all n = 2-100, 105, 120 and 128, and for all /><1000. Another table having to do with cyclotomy may be cited here also. JACOBI 3 gives for each m<p— 1 and different from (p— 1)/2 a number m' such that 1 + gm = gm' (mod p), where g is a given primitive root of p for 7 ^p^ 103. This table has been ex- tended by DICKSON 10 to /><500, and for those primes between 500 and 700 which are not of the form kq+1, where q is a prime and k — 2, 4, 6, 12. The table of FLECHSENHAAR 1 gives for each prime p = 6m+l from 7 to 307 a pair of numbers (b, c) such that be = 1 (mod p) b" + 1 = (b+ 1)" (mod#2) cP+ I = (c+ 1)" (mod />2). BANG 1 gives a list of primes p = mx+l< 1000 for which the congruence „m + jm _ cm = o (mod p) has solutions for m^ 25. A rather special table of KRAITCHIK 4 gives for each n^ 1019, except 4, 5, and 7 a number a, and a prime p such that «!+l = a(mod/>), — = - 1, thus showing that except for « = 4, 5, and 7 the diophantine equation «!+ 1 = m2 has no solutions (n, m) with n^ 1019. 1. DIOPHANTINE EQUATIONS OF DEGREE >2 Actual tables of solutions of Diophantine equations of degree d>2 exist only for d = 3 and 4, although short notes giving occasional solutions of such equations with d>4 are scattered throughout the literature on the subject. A list of about 6000 solutions of equations of the form x* ± y°- = D, arranged according to | D\ , with | D\ ^2000, is found in G£RARDIN 3. A table of all integral solutions (x, y), when possible, of with 1^x^101 and D^1024 is given in BRUNNER 1 together with the class number h (\/ — D). [63]

1 DESCRIPTIVE SURVEY Rational solutions of such equations are given in BILLING 1. "Base points" are given here from which all rational solutions of y*=x*-Ax-B 1^\A\<.3, 1 g | -B | g 3 y* = x3 - B \ B \ ^ 25 y2 = *' - Ax | A | g 50 may be generated. K.ULIK 1 gives solutions (x, y) of n = *' — y* and n = x3 + y3 for all possible odd n not exceeding 12097 and 18907 respectively. The rare table of LENHART 1 gives, for more than 2500 integers A < 100 000, solutions of *3 + y) = As* in positive integers. A small table of solutions of this equation for each of the 22 possible .4's ^50 is given in FADDEEV 1. Two tables of Delone relate to the integral solutions of the binary cubic (1) ax* + bx*y + cxy* + dy* = 1 with a negative discriminant D. DELONE 1 gives all solutions (x, y) of (1) for all non-equivalent equations with — 300<D<0. This table is reproduced in DELONE 2, where also are given all sets of integers (n, p, q) for which the dis- criminant D of the cubic xs— nx* — px— q has a given value with — 172^£><0. The ternary cubic x* + Dy* + DV - SDxyz = 1, like the Pell equations, has an infinity of solutions. A table of solutions (x, y, z) for each positive non-cube D< 100 is given in WOLFE 1. A list of 16 solutions of in OETTINGER 1 may be cited. CUNNINGHAM 28 (p. 229) gives 44 solutions of x* — y* = z2 and (p. 234-235) solutions of ** + cy* = 32 fore ^100. A. A. BENNETT 1 gives a table of solutions of what is in effect a ternary cubic equation [64]

DESCRIPTIVE SURVEY 1-m arccot xi + arccot xt = arccot yi + arccot yt. All solutions are given in which 0 <*i+a;2< 25. Finally the quaternary cubic equations <s + x3 ± y3 + z8 = 0 are considered in RICHMOND 1. All solutions (t, x, y, z) in which the variables do not exceed 100 are given. Turning to quartic equations we find only a few tables. CUNNINGHAM 15 gives all solutions (x, y, z) of x* + / = OTZ2 in which the right member does not exceed 107, and all solutions in which x= 1, and y< 1000. CUNNINGHAM 28 gives two or more solutions of x* ± ky* = ± z2 k g 100 (p. 230, 236), and of x* - kx*y* + y* = z2 k < 200 (p. 232-233). OETTINGER 1 gives 16 solutions of a-2 - y2 = z*. VEREBRIUSOV 1 tabulates all non-trivial solutions of 444 444 x + y + z = xi + yi + zi in which the variables do not exceed 50. This table is reproduced in VERE- BRIUSOV 2. m. DIOPHANTINE CONTINUED FRACTIONS A number of useful tables of the continued fraction developments of alge- braic irrationalities have been published. Most of them refer to the regular binary continued fraction 1 1 1 6 = qo + — — — qi + ?2 + ?s + • • • and, of these, nearly all refer to the case in which 6 is a pure quadratic surd \/Z>. If we write vo = 0 = qa + l/*i ?o = [6] [65]

m DESCRIPTIVE SURVEY then the xk are called complete quotients, and the qk incomplete (or partial) Quotients of 8. and 1 1 0 = <?o + — — qi + q* for every k > 0. In case 0 = \/~D the complete quotient xk takes the form *» = (VD+ Pk)/Qk where Pk and Qk are integers such that 0 <Qk< Several tables give Qk as well as qk. The numbers Qk are important in many applications, especially in connection with the question of solving the equation a;2 - Dy* = N. The numbers P* are less useful, and have (with one exception) never been tab- ulated. They may be obtained from the Q's by the formula P\ = D - QkQk-i and have been used for solving quadratic congruences (mod D). All three se- quences Pk, Qk, qk, are periodic for £>0. The main tables of the continued fraction development of \/D are DEGEN 1, CAYLEY6, and WHITFORD 1. Each table gives both qk and Qk up to the middle of the period, about which point the period is symmetric. The table of DEGEN 1 extends from D=2 to D= 1000, that in CAYLEY 6, which was computed by Bickmore, from D=1001 to D=1500, while that of WHITFORD 1 extends from 1501 to 2012. The table of SEELING 2 gives for D^602 the first half of the period of the partial quotients qk, but not Qk. In addition it gives in each case the number of terms in the period of the continued fraction, a function about which little is known. Lists of D's are given which correspond to periods of given length and type. Those D's < 7000, which have an odd number of terms in the expansion of \/J), are listed in SEELING 3. A tabular analysis of the continued fraction for \fD arranged according to the length of the period is given for D< 1000 in KRAITCHIK 6, where also is given a similar analysis of (— l+\/4/T+T)/2 for A<I00. Only the partial quotients are given. [66]

DESCRIPTIVE SURVEY m The table of ROBERTS 1 gives partial quotients only for the expansion of •%/JD for D a prime of the form 4«+l not exceeding 10 501. Another special table is that of VON THIELMANN 1, which gives partial quotients for \/pq where both p and q are primes of the form 4£+l, and pq<i000Q. The trivial cases pq = x*+l, *2±4 are excluded. The table is in two parts, the first of which contains expansions with an odd number of terms in the period. NIELSEN 1 gives for D< 1500 and the sum of two squares both qk and Qk for the expansion of \^D in case the period has an odd number of terms. A small table of the partial quotients in the first half of the period for \/Z) is given in PERRON 1 and extends to D< 100. INCE 1 gives in effect Pk and Qk, but not qk in the expansion of \fD for all ZK2025 of the form D=4£+2, 4*+3, and without square factors. These occur in the first cycle of reduced ideals. Thus for D= 194, the first cycle given is 1, 13~25, 12 ~ 2, 12 This may be taken to indicate that Pk and Qk have the values * 0 i 2 3 4 5 6 7 8 Pt 0 13 12 12 13 13 12 12 13 Qk l 25 2 25 1 25 2 25 1 The other cycles, if they exist, correspond to certain irregular continued frac- tions for \ff>. For D = 4«+l the corresponding information is given for Those convergents An/Bn to continued fractions which satisfy the equation A* — DB*= ± 1, +4 occur in tables of the Pell Equation as described under ji. Other convergents are given only rarely. A small specimen table in CAYLEY 6 gives all convergents in the first period of VZ> for D< 100. SEELING 1 gives expansions of many higher irrationalities such as \/D for D=2, 3, 4, 6, 7, 9, 10, 15 and several other numbers of the form Diik up to k = 13. Since by a theorem of Lagrange none of these expansions can be periodic the entire expansions cannot be given, so that only the beginnings of the ex- pansions are found. Complete as well as partial quotients are given. Daus has published three tables of the expansion of cubic irrationalities in a ternary continued fraction (Jacobi's algorithm). Such expansions are ultimately periodic. In place of partial quotients g* we have partial quotient pairs (pk, qk) which determine the expansion. DAUS 1 gives a table of partial quotient pairs in the expansion of ^/D for DJS30. Similar expansions of the largest root of the cubic equation *s + qx- r = 0 | 91 ^ 9, 1 g r g 9 [67]

m-n DESCRIPTIVE SURVEY occur in DAUS 2. DAUS 3 gives expansions of cubic irrationalities in certain cubic fields with a minimal basis. The fields are defined by a root 6 of the cubic equation *s - px + q = 0 | /> | g 9, | g | g 9 in which (1,0, 62) is not a basis. n. NON-LINEAR FORMS, THEIR CLASSES AND CLASS NUMBERS The theory of forms, especially of binary quadratic forms, has a number of applications in other parts of the theory of numbers. Tables having to do with the application of forms have been cited under other sections of this report, in particular under b2, e2, f2, g, is, j, 1, o and p. There remains however a large number of tables without view to immediate exterior application, giving information about the theory of forms itself. To the amateur number-theorist, not an expert in the arithmetical theory of forms, most of the tables about to be described will doubtless appear to be sterile, if not useless. If so, the writer has been successful in his classification of these tables, as the tables here described are of interest mainly to experts. Existing tables refer to four sorts of forms: binary quadratic, ternary quad- ratic, quaternary quadratic, and binary cubic forms. The theory of binary quadratic forms arose from the problem of solving Diophantine equations of the second degree, and early tables reflect this origin. We have on the one hand the tables of the Pell equations x* - DyJ = + l, fully described under ji, and on the other hand tables for the representation of a large number N by the form x* - Dy>- = N, described under g, ii, k and j2. This latter problem was at once seen to be a key to the question of factoring large numbers N and it was with this application in mind that Gauss began his epoch-making investigation into the theory of binary quadratic forms. Among the many by-products of this research three may be mentioned as being the source of tables described elsewhere. These are the theory of the number of representations of a number by a binary quadratic form, the repre- sentation of cyclotomic functions as binary quadratic forms, and the theory of quadratic fields. Tables of the functions E(n), H(n) and J(n) have been cited under b» and are contained in GLAISHER 15, 17, 18, 19, 24, 25 and 26. These functions are related to the number N(n=f(x, y)) of representations of n by the binary quadratic form f(x, y) as follows: [68]

DESCRIPTIVE SURVEY n N(n = *2 + y2) = 4E(«) tf (« = *2 + 2y2) = 27(«) (« odd) N(n = *2 + 3y2) = 2H(n) (n odd). GLAISHER 19 also contains a table of the function G(«) = N(n = (6*)2 + (6y + I)2) = N(* = (6x + 2)' + (6y + 3)2) for n= 12*+!^ 1201. Tables of the coefficients of the polynomials Y(x) and Z(x) in the represen- tation of the cyclotomic function 4(*» - !)/(* - 1) = F2(*) - (- l)<»~»/*/iZ*(*) and related tables are cited under o and begin with GAUSS 1. The theory of quadratic fields is of course very closely related to that of binary quadratic forms, their difference being largely one of nomenclature. Hence many of the tables cited under p are instances of tables related to binary quadratic forms. Tables of reduced binary quadratic forms begin with LEGENDRE 1. Table I gives all reduced forms ay2 + 2byz — cz* of determinant A =62+oc for all possible A :£ 136. Table II gives similarly re- duced forms Ly* + Myz + Nz* (M odd) with 0<A/2-4LAT^305. Tables III, IV, VI, and VII list the reduced forms ay2 + 2byz + cz2 of determinant A = ft2 — ac with — 106 ^ A ^ 79 together with the corresponding linear forms of the odd divisors of <2 — aw2 (as described under i3). Similarly Table V gives for the reduced forms Ly* + Myz + Nz* with a = 4LN — M* or LN — M*/4, according as M is odd or even, for 0<a = 4*- 1^103. Gauss must have constructed extensive tables of reduced forms but never published any. He in fact considered the publication of such tables as unneces- sary since any isolated entry can be so easily obtained directly. His table of the classes of binary quadratic forms to be cited presently was published post- humously. CAYLEY 2 tabulated the representatives of each class of forms of non- square determinant D with their characters and class group generators for [69]

n DESCRIPTIVE SURVEY | D\ < 100 together with 13 irregular determinants D between —100 and —1000 noted by Gauss. For D>0, the periods of the reduced forms are given. This table was continued from D= —100 to D= — 200 by COOPER 1. CAHEN 3 gives a table of primitive classes of positive definite forms of dis- criminant D<200 omitting those cases in which there is but a single class. There is a similar table for indefinite forms of discriminant > — 200. WRIGHT 1 has given an interesting table of reduced forms ax*-{-2bxy-\-cy* of determinant —A with A 5^ 150, and 800^ A ^848 arranged so that b and c can be read on entering the tables at a, A. The values of b are periodic functions of A for each fixed a. This table has been extended to A si 1200 in Ross 1. Two tables of indefinite binary quadratic forms are included in Ross 1. The "basic" table gives reduced forms (a, b, —c) with 0<o^c and 2b^c, for determinants up to 1500. A second table lists the periods of reduced forms, as in CAYLEY 2, for determinants from 100 to 1000. GAUSS 7 gave extensive tables of the number of classes for mostly negative determinants. More definitely the determinants considered are — D for all D's of the «th century for «= 1-30, 43, 51, 61-63, 91-100, 117-120 and, in another arrangement, for D's of the 1st, 3rd and 10th chiliad and for D of the form — (15«+7) and —(15«+13), «<800. The positive determinants considered are those of the «th century for n= 1, 2, 3, 9,10. For each group of determinants above mentioned are listed those determi- nants which have a prescribed number of genera (I, II, IV, VIII, • • • ), and a prescribed number of classes in each genus. Under each specified number of genera are given the number of determinants having that number of genera, and the total number of classes. At the end of each group these numbers are combined to give the total number of genera and classes in that group together with the number of improperly primitive classes and the number of irregular determinants, the latter being indicated in the tables by asterisks, and in most cases the index of irregularity is also given. E. T. BELL 1 contains a table of the number of odd classes of binary quad- ratic forms of determinant — D for D<100. SURYANARAYANA 1 gives a list of primes D of the form 4«+3 for which the class number of D is 2 and 0<Z><5000. For the purpose of factoring large numbers N or proving their primality, forms which have only a few classes in each genus are advantageous to use in representing the given number N. The 65 "idoneal" forms x* + Ay2, A > 0 of Euler are such that each genus contains but a single class. The idoneal A's have been given in numerous places such as MATHEWS 1 and KRAITCHIK 6 (p. 119). Besides these idoneal forms, SEELHOFF 1 has given 105 others for which each reduced form in the principal genus is of binomial type ax*+cy* to be used for factoring as mentioned under g. Forms of practical use in fac- [70]

DESCRIPTIVE SURVEY n toring are not confined to definite ones. CHEBYSHEV 1 has given for each indefi- nite form x* — Dy* (0<DS33) limits on x and y depending on N between which it is sufficient to look for representations of N. The applications of the theory of binary quadratic forms to elliptic modu- lar functions have produced tables of class invariants and other tables relating to the complex multiplication theory. These tables will be described in another report of this Committee under G: Higher Algebra. We turn now to the consideration of tables related to ternary quadratic forms. Interest in such forms originated from the problem of representing binary quadratic forms by ternary forms, and the earliest table involving ternary forms is concerned with this problem, and is found in LEGENDRE 1. Table VIII (in the first edition Tables VIII and IX) lists for all possible c^ 251, the re- duced forms py* + 2qyz + rz2, c = pr — q* and expresses each of these as a sum of three squares of linear forms. SEEBER 1 gave the first table of reduced ternary forms. This gives the classes of positive ternary forms of odd Gaussian determinant — D for D<25. This table was revised by EISENSTEIN 1 who gave the characters and classes in each genus. EISENSTEIN 2 gives a table of primitive reduced positive ternary forms of determinant — D for all D< 100 as well as D = 385. EISENSTEIN 3 lists all automorphs of positive ternary forms. These are given also in DICKSON 6 (p. 179-180). BORISOV 1 gave a table of properly and improperly primitive reduced (in the sense of Selling) positive ternary forms for all determinants from 1 to 200, assigning to each representative form a type and the number of automorphs. Tables, due to Ross, of reduced (in the sense of Eisenstein) positive ternary forms, both properly and improperly primitive of determinant d^50, giving also the number of automorphs, occur in DICKSON 6 (p. 181-185). Forms with- out "cross product" terms are listed separately. With each form is given the number of automorphs. This table has been extended to d<200 by JONES 1. JONES and PALL 1 list all 102 so-called regular forms f=ax*+by*+cz*. These are reproduced in DICKSON 9 (p. 112-113) where also are given in each case the numbers not represented by/. A special table giving certain arithmetic progressions and generic char- acters of reduced positive ternary forms whose Hessian does not exceed 25 appears in HADLOCK 1. Only three tables of indefinite ternary forms have been published. The first is due to EISENSTEIN 3 and lists non-equivalent indefinite forms whose de- terminants have no square factors and are less than 20. MARKOV 1 tabulated reduced indefinite ternary forms, not representing zero, of determinant ^ 50. This table was recomputed and extended to determi- [71]

n-o DESCRIPTIVE SURVEY nants g83 by Ross and appears in DICKSON 6 (p. 150-151). A similar table for determinants 4«g 124 occurs in Ross 1. CHARVE 1 lists all positive quaternary quadratic forms reduced in the sense of Selling of determinants ^ 20. A similar table of such forms reduced in the sense of Eisenstein for determinants ^25 is given in TOWNES 1. There are a few tables of binary cubic forms, all with negative discrimi- nants. Two of these by DELONE 1, 2 have been described under 1. ARNDT 3 gave all reduced binary cubics of negative discriminant — D, their classes and characteristic binary quadratic forms for all possible D<2000. CAYLEY 3 reproduced part of this table in revised form. His table gives the reduced forms with their order, characteristic and composition for the follow- ing values of the discriminant D: 0 > D = 4* > - 400 and 0 > D = 4k + IS - 99 and D=-4k, fc = 243, 307, 339, 459, and 675. MATHEWS 2 contains a table due to Berwick of all non-composite reduced binary cubics with discriminant — D, D<1000. o. TABLES RELATED TO CYCLOTOMY The problem of dividing the circle into an equal number of parts, or what is the same thing, the study of the roots of the binomial equation xn= 1 would seem at first sight to have little connection with tables in the theory of num- bers. Gauss was the first to recognize, however, the intimate connection be- tween cyclotomy and various branches of number theory, when he showed that the construction of regular polygons by Euclidean methods depends ulti- mately on the factorization of Fermat's numbers 22"+l. A list of the 32 regular polygons with an odd number of sides known to be constructible with ruler and compasses is given in KRAITCHIK 4 (p. 270). The theory of cyclotomy is of much wider application to number theory, however, and tables described un- der bi, b,, d, 62, ft, ji, jz, n, p and qi either depend upon cyclotomy or are of use in its applications. We have in fact already introduced in various connections the cyclotomic polynomial Urn where n is Mobius' function and S ranges over the divisors of n, which has for roots all the primitive «th roots of unity. This polynomial is often loosely spoken of as "the" irreducible factor of x"—l, and is often written as Xn and Fn(x). Tables of coefficients of Qn(x) are scarce. REUSCHLE 3 gives Qn(x) for « = 3-100, 105, 120 and 128 with the exception of « = 4£+2 for which Q*k+t(x) = Qu!+i( — x). SYLVESTER 1 gives Qn(x) for all «^36. KRAITCHIK 7 gives, for all products « of two or more primes not exceeding 105 (except 77), [72]

DESCRIPTIVE SURVEY o the coefficients of Qn(x) or of (?„( — x) = Qtn(x) according as « = 4£+l or 4£+3, and for n=2pq^ 102, those of &„(*). The need for tables of (?„(*) is not acute since for any particular «, Qn(x) may be readily found from the application of one or more of the following formulas: Q,(x) = x"-i + x>~* + • • • + x + 1 e.(«) = e-.(«") Q».(*) = Q.(- *), (« odd) where w = «0»« and «O is the product of the distinct prime factors of n, and where « is not divisible by the prime p. Several tables give data on the "/-normal periods" of the primitive «th roots of unity where 0(«) = e-/. The most elaborate such table is REUSCHLE 3, which gives for every divisor/ of #(«) the set of fundamental relations between the /-normal periods which express the product of any two of them as a linear combination of the periods for n= 1-100, 105, 120, 128, except « = 4A+2. In most cases the irreducible equation of degree e satisfied by the periods is given also, though when n is composite and e is large this equation is not given. SYLVESTER 1 gives the polynomials whose roots are the binomial periods i> = a+«~i, where a are the primitive «th roots of unity, for all «^36, and 12 other polynomials whose roots are the/-nomial periods,/>2, for n= 15, 21, 25, 26, 28 and 33. D. H. LEHMER 3 contains a table of all irreducible polynomials of degree ^ 10, whose roots are of the form «+«~i+2, where a are the primitive «th roots of unity, «?^4£+2. CAREY 1 contains tables of the coefficients in the linear expressions for the squares and products of two /-normal periods of imaginary />th roots of unity for all primes p <500 and for e= (p- 1)//=3, 4, and 5. TANNER 1 gives for each />=10«+l<1000 the quintic equation for the five (p— l)/5-nomial periods. Many tables give the representation of Qn(x) as a quadratic form. The first of these is due to Gauss, who discovered the polynomials Y"(x) and Z"(x) of degrees (p — 1)/2 and (p — 3)/2 respectively such that (2) 4<*» - !)/(* - 1) = F*(*) - (- 1)«-»'^Z'(*). These are tabulated in GAUSS 1 for p^23. Dirichlet and Cauchy later pointed out that (2) can be generalized to the case of p, replaced by a composite num- ber n, as follows: (3) 4Qn(x) = F.(*) - (- l)< where « is a product of distinct odd primes. (A quadratic form exists in the [73]

o DESCRIPTIVE SURVEY case of a perfectly general «, as may be seen at once from (1) by replacing x in (3) by ±*m). Tables giving Yn(x) and Zn(x) may be given the following tabular descrip- tion, where by "general" we mean prime or the product of distinct odd primes (the trivial case of p = 3 is usually not given). reference character of n range of « GAUSS 1 prime MATHEWS 1 prime KRAITCHIK 2 (p. 3) prime KRAITCHIK 4 (p. 126) prime HOLDEN 1, 2 general «^57 (with gaps) POCKLINGTON 1 prime 41^/>^61 LUCAS 2 general « = 5-41, 61 GOUWENS 1 prime 67^/>^97 TEEGE 1 general «^101 KRAITCHIK 7 (p. 2-4) general «J£101 GRAVE! prime GRAVE 2 prime GOUWENS 2 prime For some reason Gauss and his followers failed to discover another quad- ratic form representing Qn(x) which is, for some applications, more important than (2) or (3). The existence of polynomials Tn(x) and Un(x) such that was discovered 70 years after Gauss' discovery of (2) by Aurifeuille. Tables of the coefficients of Tn and Un were first published by LUCAS 2 for odd «^41 not divisible by a square, as well as for « = 57, 69 and 105. LUCAS 3 gives in effect the coefficients of the polynomials Vn(x) and Wn(x) such that - { ( (?„(*) if « = 4* + 1 Qtn(x) if « = 4* + 2, or 3 for all« g 34, having no square factor. This table was reproduced by CUNNING- HAM 23 with the additional entries for 34<«=£42, and w = 46, and also by KRAITCHIK 2 (p. 6), and KRAITCHIK 4 (p. 88), where in both tables the addi- tional entries « = 35, 39, 42 and 51 are given. LUCAS 2 gives in reality the coefficients of the polynomials Rn(x) and Sn(x) in the identity Q^(x) = Rn(x) - 2nxSl(x) for odd «^35, as well as « = 39, 51 and 57. The importance of Aurifeuille's formula lies in the fact that for suitably chosen x, Qn(x) becomes the difference of two squares, and hence decomposable into rational factors. [74]

DESCRIPTIVE SURVEY p p. TABLES RELATING TO ALGEBRAIC NUMBER THEORY Algebraic number theory, like the theory of forms, is a rather technical subject. The more extended parts of the theory are so ramified that tables are apt to be little more than mere illustrations of theorems. In fact, many ar- ticles on the subject contain numerical illustrations too numerous, too special and too diverse to permit description here. Although these numerical illustra- tions serve to make more real the abstract subject matter being considered, they cannot fairly claim to be described as useful tables. Tables described under other sections of this report are of use in parts of algebraic number theory. In fact, the theory of binary quadratic forms is prac- tically identical with quadratic field theory, and many tables relating to the former subject (described under n) are applicable in the latter, and conversely. Other sections containing tables useful in various parts of algebraic number theory are b2, b4, d, C2, f2, i2, j, 1, m and 0. Other useful tables, more algebraic than number theoretic, such as tables of irreducible polynomials (mod p), modular systems, Galois field tables, class invariants, singular moduli, etc. will be described in another report of this committee under G. Higher Algebra. Tables relating to algebraic numbers may be classified according to the degree of the numbers considered. Many tables pertain to quadratic number fields. The tables of SOMMER 1 contain tables of both real and imaginary quadratic fields K(\/J)) for | D\ < 100, and not a square, giving in fact for each such D a basis, discriminant, principal ideal, the classes of ideals, genera and char- acters. The fundamental unit is given when D>0. A more comprehensive account of real quadratic fields is given by the table of INCE 1. This table gives data on the fields K(Vm) for all m<2025 having no square factor. Ideals (a, b-\-(a), where u = \/m for m = 2, 3 (mod 4) and a) =(1 +•%/#») /2, when m=l (mod 4), are written simply a, b. Reduced ideals fall into classes of equivalent ideals, and the ideals in any one class form a periodic cycle which is palindromic. The table lists the first half of these cycles. In addition the table gives the number of genera in the field, and the number of classes in each genus, their generic characters and finally the fundamental unit t = x-\-y\fm or (x-\-y\/rn)/2, also written in the form («+««>)2/«, when- ever possible. The table of SCHAFFSTEIN 1 gives the class number of real quadratic fields whose discriminant is a prime p( = 4k+l) for p< l2 000, 106</>< 10'+103, and A number of tables refer to the Gaussian numbers a+&V'— 1, and their powers. The first such table occurs in GAUSS 2 and gives for each of 19 complex primes p = a+ib with norm a2+62^ 157 those complex numbers (mod p) which have each of the 4 different biquadratic characters (mod />). GAUSS 9 has a table of indices for 45 complex primes p — a+ib. This table [75]

p DESCRIPTIVE SURVEY was extended to all prime and composite moduli in K(^ — 1), whose norms do not exceed 100, by G. T. BENNETT 1. BELLAVITIS 1 contains a table of powers (o+ ib)k (mod/>,r!+ 1) of a primitive root a+ib for / > = 4m+3^67, for k = r(p+l), s(/>—1) and *(/>-!) + 1, where r= 1,2, • • • (/>-l)/2, *=1, 2, • • - (f+l)/4. The table of VORONO" 1 gives for each prime p < 200, a pair of companion tables, one of which gives the powers (mod p) of a primitive root E=a-\-ib, where i* = N (mod p), W being the least positive quadratic non-residue of p. The other table gives the index of that power of E whose real part is specified and whose imaginary part is positive. GLAISHER 17 has tabulated three functions which depend on "primary" Gaussian numbers, that is, numbers of the form (- l)<-+»-i>/»(o + ib) where a>0 is odd and b is even. Let Sk(n) denote the sum of the kth powers of the primary Gaussian num- bers whose norm is n. Glaisher denotes the functions Si(«) and Ss(n) by x(«) and X(«) respectively. In fact x(«) is tabulated for odd «<1000, and for all primes and powers of primes < 13 000, while X(«) is tabulated for n< 100. The function 5o(«) is designated by E(n), several tables of which are described under b2. Tables relating to cubic fields are much less numerous than those for quad- ratic fields. The tables of REID 1, 2 are in two parts. Part 1 gives for each reduced cubic equation x* + px + q = 0, | p \ g 9, 1 g q g 9 the discriminant of the field thus defined, the class number, a basis and a sys- tem of units as well as the factorization of certain small rational primes in the field. Part II gives the same information for 19 other cubics of the general form as3 + bx* + cx+ d (b T± 0). The tables of DAUS 2, 3 (described under m) give the units in the cubic fields under consideration. DELONE 1, 2 give information about units of cubic fields of negative dis- criminant. In particular DELONE 2 lists all fields with discriminant —D with Z><172. Extensive tables of relative cubic fields are given in ZAPOLSKAIA 1. Quartic field tables are all of special type. DELONE, SOMINSKI! and BILEVICH 1 give a list of all totally real quartic fields with discriminant not exceeding 8112. With each such field is given a basis. [76]

DESCRIPTIVE SURVEY p-qi The tables of TANNER 1, 2 refer to the quartic field defined by to, a primi- tive 5th root of unity. These give the "coordinates" qt of the "simplest" com- plex factor of a prime p=l0n+l as well as the coordinates of the "simplest primary" factor and the "reciprocal" factor^(o>), the latter being such that^(coV(w~i) = p. In TANNER 1, /><1000 while in TANNER 2 the information is given for /><10 000 except that the reciprocal factor is tabulated only for 1000 <p <10 000. A similar table for the quartic field defined by a primitive 8th root of unity is given in BICKMORE and WESTERN 1. This gives the coordinates of a canoni- cal complex prime factor of every prime p = &n+l<25 000. These tables really belong under cyclotomic fields, concerning which ex- tensive tables were published by Reuschle, and are in fact extensions of similar tables occurring in REUSCHLE 2, 3. REUSCHLE 2 gives the complex factors of rational primes p in the cyclotomic field /C(exp 2iri/n) and the subfields gener- ated by the periods for p = kn-\-l< 1000 and for all primes n from 7 to 29 as well as for « = 5 and />= 106+ 1< 2500. These tables are superseded by REUSCHLE 3 where n = 3-100, 105, 120, 128 («j^4£+2). For « a prime <20 two factors of p< 1000 are given, one "simple" and one "primary" after Kum- mer. For other values of » only "simple" factors of p are given. In many cases complex factors of p" are given where a> 1 is the index of ideality. In all cases p< 1000. For n large and composite many of the tables pertaining to the sub- fields are wanting. q. TABLES RELATING TO ADDITIVE NUMBER THEORY Of the many and varied problems of additive number theory, three have been the source of tables. These are the problem of partitions or the represen- tation of numbers as sums of positive integers of no special type, the problem of Goldbach, or the representation of numbers as sums of primes, and the problem of Waring, or the representation of numbers as sums of powers. Qi. Theory of partitions Tables relating to partitions are of two types according as the parts con- templated are or are not restricted in some way as to size or number. We take up the unrestricted partitions first. The actual partitions of a number « into the parts 1, 2, • • • , n, giving for «=5, for example, the 7 entries (11111), (1112), (113), (122), (14), (23), (5) occur as arguments of tables of symmetric functions and other algebraic tables to be considered in another report of the Committee under G. Higher Algebra. We may cite here, however, a table of all partitions of « for «^ 18 due to [77]

qi DESCRIPTIVE SURVEY CAYLEY 4. The parts 1, 2, 3, • • • are represented by the letters a, b, c, • • • and the 7 entries under n=5 thus appear as a6, a'6, a2c, a62, ad, be, e. The theory of partitions is concerned more with the mere number p(n) of partitions rather than the actual partitions themselves. The function p(n) increases so rapidly that Cayley's table could not be carried much farther. For « = 30, for example, it would have 5604 entries. The first real table of p(n) occurs as a by-product of the table of EULER 3 and is there denoted by «(CO) and tabulated for n^59. This table was not ex- tended until 191 7 when the analytic researches of Hardy and Ramanujan made it desirable to examine the magnitude of p(n) for large n. MacMahon accord- ingly computed p(n) for «^200, his table being published by HARDY and RAMANUJAN 1. GUPTA 1 has given p(n) for «^300 and for 301 ^«^ 600. The complete table for n ^ 600 is reproduced in GUPTA 7. Two tables give values of p(n) (mod />). GUPTA 3 gives />(«) (mod 13) and (mod 19) for «^ 721. MACMAHON 1 lists those values of «^l000 for which p(n) is even. Thanks to recent investigations the asymptotic series of Hardy and Ramanujan now offers an effective and reliable method of obtaining isolated values of p(n). This series contains certain coefficients Ak(n), tables of which, as functions of «, are given in HARDY and RAMANUJAN 1 for £JS18. D. H. LEHMER 5 contains a table of actual values of Ak(n) for k^20, and for all «, (since Ak(n-\-k) = Ak(n)}, the number of decimal places being sufficient for computing />(«) for n up to three or four thousand. This table is reproduced in GUPTA 7. In investigating an approximate formula for p(n), HARDY and RAMANUJAN 1 have given the value of .9 Logi0 />(«) — V10 + n for «=10* and 3-10* (* = 0, 1, • • • , 7). The generating function for p(n) is the modular function n— i The coefficients of the related function have been studied to some extent and are given for «=S30 in RAMANUJAN 2. Turning now to tables of the number of partitions in which the parts are restricted in some way we find two tables of the function q(n) which may be regarded either as the number of partitions of n into distinct parts or as the [78]

DESCRIPTIVE SURVEY <li-<l2 number of partitions of « into odd parts, so that j(5)=3. The first table is due to Darling and is published in HARDY and RAMANUJAN 1 (Table V), and gives q(n) for «^100. WATSON 1 extends this table to «±£400, and gives for the same values of « the function qa(n), which denotes the number of par- titions of n into distinct odd parts. UMEDA 1 gives for n^ 100 the values of the function 1 " where pm(n) denotes the number of partitions of n into exactly m parts. A small table of CAYLEY 5 gives for n^ 100 the number of partitions of n into the parts 2, 3, 4, 5, and 6. Other tables of restricted partitions are double entry tables. The first of these is EULER 3, which gives the number «(m) of partitions of n into parts g m, or what is the same thing, the number of partitions of n into not more than m parts for «^59, w^20. The differences «<m> — «<m-» are also tabulated. The table of GUPTA 7 gives the number (n, m) of partitions of n in which the smallest part is precisely m, so that p(n) = («+1, 1). Table II (p. 21-79) gives (n, m) for «5S300 and 2^m^ [n/S]. On p. 81 is a table giving the num- ber of partitions of n into parts exceeding [«/4] for n^ 300. A small table of TAIT 1 gives the number of partitions of n into parts ^ 2 and ^rfor«^32andrg!7. GIGLI 1 gives the number Nn(r) of partitions of n into precisely r distinct parts not exceeding 10 for r^ 10 and all possible values of n. The subject of partitions is of course not to be confused with the so-called quadratic partitions discussed under J2, giving the actual partitions of numbers into several squares, all but one being equal. In this connection we may cite a table of GAUSS 3 having to do with the number R(n) of representations of n as a sum of two squares. Gauss tabulates the sum A X R(n) for A = *-10", k g 10, m = 2, 3, and 4. n-i This is also the number of lattice points inside a circle of radius \/A. q2. Goldbach's problem Goldbach's, as yet unproved, conjecture is that every even number >2 is the sum of two odd primesi > 1. Tables have been constructed to test the validity of this conjecture as well as to obtain some information as to the order of magnitude of the number G(x) of representations of 2x as a sum of two primes. CANTOR 1 gives all decompositions of 2n into a sum of two primes by listing i Some writers admit 1 as a prime, however. [79]

q2 DESCRIPTIVE SURVEY the lesser of the two primes in each case for 2n^ 1000. The number of such decompositions is also given. HAUSSNER 1 gives the same information as CANTOR 1, but for 2«^3000, and in addition gives the number of decompositions of 2n = pi-\-pt (pi<p*) for 2«^5000. As an auxiliary table the values of P(n)-2P(n-2)+P(n — 3) and of P(n), the number of odd primes ^«, are given for each odd «^5000. PIPPING 1 lists for each even number 2«:£5000 the smallest and largest primes <n which enter into the representation of 2n as a sum of two primes, together with the value of G(2n), the number of pairs of primes (pi, p*) such that pi+p*=2n, the pairs (pi, pt) and (/>2, pi) being reckoned as distinct if PIPPING 2 gives G(2n) for 2262 ^2n^ 2360, 4902 ^2n^ 5000 and 29 982 ^2«5=30 080 together with the corresponding values of two approximating functions. PIPPING 3 gives G'(2n), the number of decompositions of 2n as a sum of two primes in Haussner's sense in which 2«=/>i+/>2=/>2+/>i are reck- oned as one decomposition, for the same values of In as occur in PIPPING 2, and also the values of G(2«) for 120 072 ^2«^ 120 170. HAUSSNER 4 has a table of the number of representations of 2» as a sum of two numbers divisible by no prime ^pr, where p2r<2n<p*+i for 2«^ 500, and eleven other values of 2n between 4000 and 4166. STACKEL 1 has a similar table due to Weinreich for n = 6k^ 16 800. PIPPING 4 has a table of those even numbers 2« which exceed the largest prime less than 2n — 2 by a composite number for 5000^ 2«^ 60 000. With each such number 2n is given the least prime p such that 2n — p is also a prime. GRAVE 3 gives G'(2n) for 2«^ 1500. Two tables give verifications of Goldbach's conjecture at isolated points up to high limits. CUNNINGHAM 10 has tested the conjecture for even numbers 2« of the form*-2m, *=1,3, 5, 7, 9, 11, 12", 20", 2-10m, 6m, 10", 14", 18", 22m, 2m(2m ± 1) and also 2-k", k = 3, 5, 7, 11 and 2(2" ±r), r^ 11 and odd, up to, in some cases, 2«g200 000 000. SHAH and WILSON 1 give the number of decompositions of 2n into the sum of two primes, and also into the sum of two powers of primes for 35 values of 2n from 30 to 170 172. A curious table of SCHERK 1 expresses the «th prime pn in terms of all previous primes as a sum of the form «-i Pn = 1 + Z tkpk k-i where «» = 1 for k < n — 1 , while «n-i = 1 or 2. [80]

DESCRIPTIVE SURVEY q8 qs. Waring's problem The eighteenth century conjecture of Waring that every number is the sum of at most 9 positive cubes, at most 19 fourth powers and so on, has given rise to a large number of tables. The Waring problem has been generalized in many ways, but almost all tables refer to the problem of representing numbers as sums of positive fcth powers. These tables are of two sorts: basic tables dealing with the representation of numbers from 1 to N as sums of some limited number of kth powers, and special tables giving such information for miscellaneous ranges of numbers be- tween certain high limits. Tables of this latter type are more recent and owe their existence to attempts to connect with results obtained analytically prov- ing a "Waring theorem" for all large numbers, say n>N, and thus to prove the Waring theorem completely. The practical importance of many of these tables has been greatly reduced due to refinements in the analytical methods and a consequent lessening of the number N, a process which is likely to continue in the future. Tables relating to Waring's problem for kth powers naturally classify themselves according to the value of k, and begin with £ = 3. Tables of this sort for cubes date from 1835, when ZORNOW 1 gave the least number of cubes required to represent each « Si 3000, together with the number of numbers between r3 and (r+1)3 which are sums of no fewer than a specified number of cubes, for 1 ^r^ 13. This table was recomputed and extended by Dase to «g 12 000, and pub- lished in JACOBI 4. Besides the corresponding distribution tables there is also the list of those numbers ^12 000, which are sums of 2 cubes and sums of not less than 3 cubes. The table of STERNECK 3 gives the minimum number of cubes required to represent every number ^40 000 as a sum of cubes. There also appears a table of the number of numbers in each chiliad which require a specified num- ber of cubes from 1 to 9. A. E. Western has made a special study of the numbers represented as a sum of 4 or 5 cubes. In particular, he has determined for each « = 9£+4 <810 000, whether the number of representations by 5 cubes is 0, 1 or >1. These results, and others for selected ranges between 4-10* and 4-10° are sum- marized in WESTERN 2, where the densities of the various numbers in various ranges are given and compared with empirical formulas. DICKSON 12 is a manuscript table extending STERNECK 3 from 40 000 to 270 000. DICKSON 13 is a manuscript table of the sum of 4 cubes from 270 000 to 560 000. From 300 000 on the minimum number of summands required to represent such numbers is indicated. A small table of Ko 1 gives the representation of every «^ 100, except 76 and 99, in the form 3?+y*+2&, where x, y, and z are integers, positive, nega- [81]

qt DESCRIPTIVE SURVEY tive or zero. The cases n=6k are omitted from the table, since in this case we have (x,y,z) = (*+1,4-1, -*). Three tables on fourth powers may be mentioned. BRETSCHNEIDER 2 gives "minimum decompositions" for numbers «^84 = 4096. If s is the least number of biquadrates whose sum is n then all decompositions involving s biquadrates are given. Those numbers n whose minimum decompositions are derived merely by adding I4 to those of the preceding number are omitted from the table. A second table lists all numbers representable by s, but no fewer than s biquadrates for s= 2, 3, 4, • • • , 19. A more elaborate table for the same range is D. H. and E. T. LEHMER 1. This gives all decompositions of each number ^4096 into a sum of not more than 19 biquadrates. A table sufficient for find- ing one minimum decomposition into fourth powers for 4096 <«^ 28 561 to- gether with a summarizing table appears in CHANDLER 1. A special table of SPARKS 1 is used to prove that every number ^4184 is represented by the form x*+x^+x^+xi+2xl+2xf+^+7xl. Three tables of fifth powers may be cited. WIEFERICH 1 shows the least number of 5th powers required to represent each number «^3011. DICKSON 7 gives a minimum decomposition into 5th powers for all n^ 150 000, and the minimum number of such decompositions for «^300 000. DICKSON 11 gives a minimum decomposition into sums of fifth powers for the ranges 839 000 to 929 000, and 1 466 800 to 1 600 000. This information for the range 3 470 000 to 3 500 000 is given in DICKSON 8 (p. 84-154). On p. 154-257 are given the minimum numbers of fifth powers required to repre- sent all numbers .between 3 500 000 and 3 600 000. Tables relating to Waring's problem for higher powers are all very special and may be cited as follows: For sixth powers—SHOOK 1; seventh powers—YANG 1, MAUCH 1 and DICKSON 8 (p. 25-81); eighth powers—SUGAR 1; tenth powers—DICKSON 8 (p. 1-7); thirteenth powers—ZUCKERMAN 1; fifteenth and seventeenth powers —DICKSON 8 (p. 8-24). HARDY and LITTLEWOOD 2 give values or lower bounds for the number T(k) which is the least number s such that every arithmetic progression contains an infinity of numbers which are sums of at most s positive *th powers, for k ^ 200. Finally, there is the table of PILLAI 1, which gives for each «^100, the values of 2", /„ and rn in the equation 3" = U» + rn, quantities which are important in Waring's problem for «th powers. Gupta has published 4 tables dealing with the representation of numbers by sums of like powers of primes. In this case 1 is counted as a prime. GUPTA 2 has a table showing that every number ^ 100 000 is a sum of not more than 8 squares of primes. GUPTA 6 has a special table for this problem of [82]

DESCRIPTIVE SURVEY qi all integers ^2000 of the form A = (/>*-1)/120, 5=(/>2-49)/120, C = A+B, where p is a prime. GUPTA 4 gives the least number of cubes of primes required to represent each number ^ 113= 1331, and a list of 150 numbers between 11s and 20 828 which require 6 or fewer cubes of primes. GUPTA 5 gives tables showing that every number ^ 20 875 (except 1301) is a sum of not more than 12 cubes of primes. Waring's problem with polynomial summands is responsible for a number of special tables due to Dickson and his pupils. The summands in question are polygonal numbers and certain cubic functions. For polygonal numbers we may cite DICKSON 5, ANDERSON 1, GARBE 1, and for cubics, BAKER 1, and HABERZETLE 1. [83]