Sandbox.

John W. Pilley
Born(1928-07-01)July 1, 1928
DiedJune 17, 2018(2018-06-17) (aged 89)
NationalityAmerican
Occupation(s)professor, ethologist
Years active1969-2018
Known forOwner and trainer of Chaser the border collie
SpouseSally Pilley (married 1955)
Academic background
EducationPhD psychology (1969)
Alma materAbilene Christian University, Princeton Theological Seminary, Stetson University, Memphis State
Academic work
InstitutionsWofford College

Generalizations

edit

A polyhedron P is said to have the Rupert property if a polyhedron of the same or larger size and the same shape as P can pass through a hole in P.[1] All five Platonic solids: the cube, the regular tetrahedron, regular octahedron,[2] regular dodecahedron, and regular icosahedron, have the Rupert property.[1] It has been conjectured[1] that all 3-dimensional convex polyhedra have this property. For n greater than 2, the n-dimensional hypercube also has the Rupert property.[3]

Of the 13 Archimedean solids, it is known that these nine have the Rupert property: the cuboctahedron, truncated octahedron, truncated cube, rhombicuboctahedron, icosidodecahedron, truncated cuboctahedron, truncated icosahedron, truncated dodecahedron.[4] and truncated tetrahedron[5]

Coin

edit

Palace [6]

Sci-Hub [7]

Reuleaux polygon with 11 sides.[8]

Quote 1.[9]: 51–52  Quote 2.[9]: 56  Quote 3.[9]: 3 

Claude Lightfoot's case in the Supreme Court. [10]

Hinton's case. [11]

Miller v Alabama [12]

Miller v. Alabama TWO, 567 U.S. 460 (2012) This only goes to volume 567, not to page 460. [13]

Inuit had games using string figures. [14]: page 161 

In 1916, Irwin[15] showed that the value of the Kempner series is between 22.4 and 23.3.

Irwin's generalizations of Kempner's results

edit

In 1916, Irwin [15] also generalized Kempner's results. Let k be a nonnegative integer. Irwin proved that the sum of 1/n where n has at most k occurrences of any digit d is a convergent series.

For example, the sum of 1/n where n has at most one 9, is a convergent series. But the sum of 1/n where n has no 9 is convergent. Therefore, the sum of 1/n where n has exactly one 9, is also convergent. Baillie[16] showed that the sum of this last series is about 23.04428708074784831968.

Misc stuff

edit

Rules for Sheepdog Herding Competitions [17]

Info about Chaser. Was "[18]". Used citation bot to change it to this.[19]

Birthday problem. [20][21]

 
Gravity well with planetary orbit

The sum of 1/n where n has no 9's is about 22.92067661926415034816. This uses gaps in double braces, but when you copy it, the spaces don't get copied.

Here is a Harvard citation to two books with one, and two, authors: If β is the upper bound of the real parts of the zeros, then the difference π(x) - li(x) has the error bound O(xβ log(x)) (Ingham 1932): Theorem 30 , (Montgomery & Vaughan 2007): p. 430 . It is already known that 1/2 ≤ β ≤ 1 (Ingham 1932).: p. 82 

The brontosaurus is thin at one end.[22]: page 5  Then it becomes much thicker in the middle.[22]: 6  Also try this. [22]: Theorem 7  The 'r' combines 'ref' and 'rp'. See Help:References and page numbers and Template:R.

Here is a book. [23]

This refers to chapter 11 of the book.[23]

This refers to a section of the book. [23]: §11.3.6.3 

Citation to something on the wayback machine.[24]

This is from a discussion about precession.[25] Note that this cites books, but not with the usual cite book template.

For a way to list a bunch of books in one reference, see Introduction to general relativity, the reference that begins "This development is traced...". That uses Template:Harvard citation no brackets.

Parseval's theorem can also be expressed as follows: Suppose   is a square-integrable function over   (i.e.,   and   are integrable on that interval), with the Fourier series

 .

Then[26] [27] [28]

 .

For  , the  th non-Fibonacci number (i.e., 4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, ...) is   [29]

(  can be computed using logarithms to other, standard bases. For example,  .)

Chris Caldwell's Prime Pages [30]

Pinch article. [31] [32] Could also use this url. http://tucs.fi/publications/view/?pub_id=pErJuKaLe07a.

Factorization. [33]

Here is the PSW paper. (wikilinks converted to author-links) [34]

Try this below and see if it works.

Here is the LPSP paper. [35]

Here is the BLS paper. [36]

Then for any ε > 0 there exists a t ≥ 0 such that

  (1)

for all  .

Definition (of Fermat pseudoprime)

edit

Fermat's little theorem states [37]: Theorem 2.23  that if n is prime and a is coprime to n, then an-1 - 1 is divisible by n. In other words,

 ,

(where mod refers to the modulo operation).

The converse is usually not true. That is, if n is not prime, then   is usually not  . This is the basis for the Fermat primality test. [38]

If  , then n is called a probable prime to base a.

If   and n is composite, then n is called a Fermat pseudoprime to base a.[37]: Def. 3.32 

A Fermat pseudoprime is often called a pseudoprime, with the modifier Fermat being understood.

In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a.[38]

The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2340 = 1 (mod 341) and thus passes the Fermat primality test for the base 2.

For any base a greater than 1, there are an infinite number of pseudoprimes to base a.[39]: Thm. 3.4.4 

Pseudoprimes to base 2 are sometimes called Poulet numbers, after the Belgian mathematician Paul Poulet, Sarrus numbers, or Fermatians (sequence A001567 in the OEIS).

An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.[37]: Def. 3.34 

Formal definition

edit

This is from the Strong pseudoprime page. This is the original, longer definition:

An odd composite number n = d · 2s + 1 where d is odd is called a strong (Fermat) pseudoprime to base a if:

 

or

 

(If a number n satisfies one of the above conditions and we don't yet know whether it is prime, it is more precise to refer to it as a strong probable prime to base a. But if we know that n is not prime, then one may use the term strong pseudoprime.)


Formal definition (new)

edit

This is for the Strong pseudoprime page. This is a more concise definition.

An odd number n = d · 2s + 1 where d is odd, is called a strong (Fermat) probable prime to base a if:

 

or

 

If we know that such an n is not prime, then n is called a strong pseudoprime.

In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations, such as high-speed multiplication, primality testing, and integer factorization.

Algorithms

edit

There are many algorithms in computational number theory. The following are some of the algorithms and their complexities:

Multiplication

edit

The lower bound for the computational complexity of multiplication has been a focus since the first computer appeared. The standard multiplication algorithm has complexity O(n²), but the time complexity has been long conjectured to be O(n log(n)). This was proved in 2019.[40]

Primality test

edit

An important problem in computational number theory is to determine whether an integer is prime.

The are several possible approaches. If the number is sufficiently small, one can use trial division to test whether any small prime factors are divisors of the number in question.

For larger numbers for which trial division would take too long, one can apply a probable prime test. This test reports one of two results: either the number is definitely composite, or the number is very likely to be prime (that is, the number is a probable prime).

If a number is believed to be prime and a proof of primality is required, then there are several algorithms that can produce such a proof. These include the AKS primality test and the elliptic curve algorithm.

Factorization

edit

If a number has been found to be composite, it is sometimes necessary to find its factors. Integer factorization is another important problem in computational number theory.

Highway 407

edit

These references are needed below, so put them here temporarily.[41][42] [43]

Privatization

edit

The privatization of the road, the toll rate increases, and the 99-year lease period have been widely criticized.[44]: Chapter 2 

  • The original plan was for the tolls to end after the construction cost was paid off, probably after about 35 years; there is no indication that the private owners will eliminate the tolls.[45]
  • Although Premier Mike Harris promised that tolls would not rise by more than 30 percent, they have risen by over 200 percent by 2015, from about 10 cents to over 30 cents per kilometre.[41]
  • There have been criticisms and lawsuits arising from plate denial issues.
  • Another criticism is that taxpayers did not receive a fair price for their highway: In 2002, just three years after the original sale for C$3.1 billion, Macquarie Infrastructure Group, an Australian investment firm, estimated that the highway was worth four times the original price.[46] By 2019, the estimated value had risen to C$30 billion.[42][43]
  • Both the length of the lease, and the fact that the road is controlled by private corporations, mean that decisions about the road and the tolls are less accountable to the public.[44]: Chapter 2  The Harris government failed to put any restrictions on toll increases (as long as the road attracted a certain volume of cars). As a result, commuters in the densely-populated Toronto area will have no protection against ever-rising tolls on this key highway during the entire 99-year span of the lease.[44]: pp. 53-57 

Baillie-PSW primality test

edit

This is for the Primality test page. Add a new section with this name.

The Baillie–PSW primality test is a probabilistic primality test that combines a Miller–Rabin type test with a Lucas pseudoprime test to get a primality test that has no known counterexamples. That is, there are no known composite n for which this test reports that n is probably prime.[35] It has been shown that there are no counterexamples for n  .

Fibonacci pseudoprimes

edit
  (1)

Some good references are chapter 8 of the book by Bressoud and Wagon (with Mathematica code),[47] pages 142–152 of the book by Crandall and Pomerance,[39] and pages 53–74 of the book by Ribenboim.[48]

Original version of Fibonacci pseudoprimes:

As noted above, when P = 1 and Q = −1, the numbers in the U sequence are the Fibonacci numbers.

A Fibonacci pseudoprime is often (page 264 of,[47] page 142 of,[39] or page 127 of [48]) defined as a composite number n for which equation (1) above is true with P = 1 and Q = −1 (but n is not divisible by 5). By this definition, the first ten Fibonacci pseudoprimes are 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, and 10877 (sequence A081264 in the OEIS). The references of Anderson and Jacobsen below use this definition.

If n is congruent to 2 or 3 (mod 5), then Bressoud (,[47] pages 272–273) and Crandall and Pomerance (,[39] page 143 and exercise 3.41 on page 168) point out that it is rare for a Fibonacci pseudoprime to also be a Fermat pseudoprime base 2. However, when n is congruent to 1 or 4 (mod 5), the opposite is true, with over 12% of Fibonacci pseudoprimes under 1011 also being base-2 Fermat pseudoprimes.

If n is prime and GCD(n, Q) = 1, then (see equation 4 on page 1392 of [35]) we also have

 

This leads to an alternate definition of Fibonacci pseudoprime.[49] By this definition, a Fibonacci pseudoprime is a composite number n for which equation (5) is true with P = 1 and Q = −1. Using this definition, the first ten Fibonacci pseudoprimes are 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, and 15251 ([48] page 129) (sequence A005845 in the OEIS). This sequence appears to have been first studied by Singmaster.[50]

It has been shown that there are no even Fibonacci pseudoprimes with the second definition using equation (5).[51] Using the more common first definition with equation (1), they do exist (sequence A141137 in the OEIS).

A strong Fibonacci pseudoprime may ... blah blah blah

New version of 2nd paragraph:

If n is prime and GCD(n, Q) = 1, then (see equation 4 on page 1392 of [35]) we also have

 

This leads to an alternate definition of Fibonacci pseudoprime. By this definition, a Fibonacci pseudoprime is a composite number n for which equation (5) is true with P = 1 and Q = −1.[52] [53] Using this definition, the first ten Fibonacci pseudoprimes are 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, and 15251 ([48] page 129) (sequence A005845 in the OEIS); the latter refers to these as Bruckman-Lucas pseudoprimes. Hoggatt and Bicknell studied properties of these pseudoprimes in 1974.[54] Singmaster computed these pseudoprimes up to 100000.[55] Jacobsen lists all 111443 of these pseudoprimes less than 1013.[56]

It has been shown that there are no even Fibonacci pseudoprimes as defined by equation (5).[57][58] Using the more common first definition with equation (1), they do exist (sequence A141137 in the OEIS).

Using the bits

edit

We use the bits of the binary expansion of n to determine which terms in the U sequence to compute. For example, if n+1 = 44 (= 101100 in binary), then, taking the bits one at a time from left to right, we obtain the sequence of indices to compute: 12 = 1, 102 = 2, 1002 = 4, 1012 = 5, 10102 = 10, 10112 = 11, 101102 = 22, 1011002 = 44. Therefore, we compute U1, U2, U4, U5, U10, U11, U22, and U44. We also compute the same-numbered terms in the V sequence, along with Q1, Q2, Q4, Q5, Q10, Q11, Q22, and Q44.

Better results

edit

In 1899, de la Vallée Poussin proved that

 

for some positive constant a. Here, O(...) is the big O notation.

More precise estimates of   are now known. For example, in 2002, Kevin Ford proved that[59]

 .

In 2016, Tim Trudgian proved an explicit upper bound for the difference between   and  :

 

for  .[60]

For most values of   we are interested in (i.e., when   is not unreasonably large)   is greater than  . However,   is known to change sign infinitely many times. For a discussion of this, see Skewes' number.

Inequalities

edit

Dusart 2010 is this.[61]

In [61], Dusart proved (Proposition 6.6) that, for  ,

  ,

and (Proposition 6.7) that, for  ,

  .

More recently, Dusart[62] has proved (Theorem 5.1) that, for  ,

  ,

and that, for  ,

  .

A function that represents all primes

edit

Given the constant  , for  , define the sequence

  (1)

where   is the floor function. Then for  ,   equals the   prime:  ,  ,  , etc. [63] The initial constant   given in the article is precise enough for equation (1) to generate the primes through 37, the   prime.

The exact value of   that generates all primes is given by the rapidly-converging series

 ,

where   is the   prime, and   is the product of all primes less than  . The more digits of   that we know, the more primes equation (1) will generate. For example, we can use 25 terms in the series, using the 25 primes less than 100, to calculate the following more precise approximation:  . This has enough digits for equation (1) to generate all of the primes less than 100.

As with Mills' formula and Wright's formula above, in order to generate a longer list of primes, we need to start by knowing more digits of the initial constant,  .

Demographics

edit
Historical population
YearPop.±%
18410—    
185100.00%
18813—    

Ducci

edit

An obvious generalisation of Ducci sequences is to allow the members of the n-tuples to be any real numbers rather than just integers. For example, [64] this 4-tuple converges to (0, 0, 0, 0) in four iterations:    

The properties presented here do not always hold for these generalisations. For example, a Ducci sequence starting with the n-tuple (1, q, q2, q3) where q is the (irrational) positive root of the cubic   does not reach (0,0,0,0) in a finite number of steps, although in the limit it converges to (0,0,0,0).[65]

Universality April 2017 version

edit

The critical strip of the Riemann zeta function has the remarkable property of universality. This zeta-function universality states that there exists some location on the critical strip that approximates any holomorphic function arbitrarily well. Since holomorphic functions are very general, this property is quite remarkable. The first proof of universality was provided by Sergei Mikhailovitch Voronin in 1975.[66] More recent work has included effective versions of Voronin's theorem [67] and extending it to Dirichlet L-functions [68] [69]

D. R. Heath-Brown proved that at least one of 2, 3, or 5 is a primitive root modulo infinitely many primes p. [70] [71]

Universality ORIGINAL May 2017 version

edit

The critical strip of the Riemann zeta function has the remarkable property of universality. This zeta-function universality states that there exists some location on the critical strip that approximates any holomorphic function arbitrarily well. Since holomorphic functions are very general, this property is quite remarkable. The first proof of universality was provided by Sergei Mikhailovitch Voronin in 1975.[72] More recent work has included effective versions of Voronin's theorem [73] and extending it to Dirichlet L-functions [74] [75] and Selberg zeta functions [76]

Universality of other zeta functions

edit

Work has been done showing that universality extends to Selberg zeta functions [77]

The Dirichlet L-functions show not only universality, but a certain kind of joint universality that allow any set of functions to be approximated by the same value(s) of t in different L-functions, where each function to be approximated is paired with a different L-function.[78] [79]: Section 4 

A similar universality property has been shown for the Lerch zeta function  , at least when the parameter α is a transcendental number. [79]: Section 5  Sections of the Lerch zeta-function have also been shown to have a form of joint universality. [79]: Section 6 

Universality NEW May 12 2017 version

edit

The critical strip of the Riemann zeta function has the remarkable property of universality. This zeta-function universality states that there exists some location on the critical strip that approximates any holomorphic function arbitrarily well. Since holomorphic functions are very general, this property is quite remarkable. The first proof of universality was provided by Sergei Mikhailovitch Voronin in 1975.[80] More recent work has included effective versions of Voronin's theorem [81] and extending it to Dirichlet L-functions. [82] [83]

Current latitude of arctic circle

edit

Macro from the article about the arctic circle: The position of the Arctic Circle is not fixed; as of 23 June 2024, it runs 66°33′50.0″ north of the Equator.[84]

Implementing a Fermat probable prime test

edit

This is for the Fermat pseudoprime article. However, that links to Fermat primality test. That links to the exponentiation algorithm, so this might not be necessary.

Suppose n = 53 so n−1 = 110100 in binary. We use the bits in left to right order, so only the following powers of a need to be computed: a1, 'a2, a3, a6, a12, a13, a26, and a52. Note that we can go from a26 to a52 in just one step by squaring a26. To keep the intermediate results from becoming unnecessarily large, the result is reduced (mod n) at the end of each step.

Implementing a Fermat primality test

edit

This goes into this article: https://en.wikipedia.org/wiki/Fermat_primality_test This section:

Suppose one is given a large number n for which one intends to apply the Fermat probable prime test. A typical implementation might work as follows. First, test for divisibility by small primes. If no prime divisors are found, then the Fermat test would be performed.

The base a can be any number other than 0, 1, or −1 (mod n). [If n is odd, then both a = 1 and a = n−1, raised to the power n−1 would trivially give the result 1 (mod n)]. a = 2 is a common choice for a base. We can raise the base a to the large power n−1 without having to compute every power of a between 1 and n−1 using a technique called binary exponentiation, as shown in the following example.

Suppose n = 53 so n−1 = 110100 in binary. We use the bits in left to right order, so only the following powers of a need to be computed: a1, 'a2, a3, a6, a12, a13, a26, and a52. Note that we can go from a26 to a52 in just one step by squaring a26. To keep the intermediate results from becoming unnecessarily large, the result is reduced (mod n) at the end of each step.

Implementing a Lucas probable prime test

edit

Before embarking on a probable prime test, one usually verifies that n, the number to be tested for primality, is odd, is not a perfect square, and is not divisible by any small prime less than some convenient limit. Perfect squares are easy to detect using Newton's method for square roots.

We choose a Lucas sequence where the Jacobi symbol  , so that δ(n) = n + 1.

Given n, one technique for choosing D is to use trial and error to find the first D in the sequence 5, −7, 9, −11, ... such that   is −1. (If D and n have a prime factor in common, then  ). With this sequence of D values, the average number of D values that must be tried before we encounter one whose Jacobi symbol is −1 is about 1.79; see [35], p. 1416. Once we have D, we set P = 1 and  . It is a good idea to check that n has no prime factors in common with P or Q. This method of choosing D, P, and Q was suggested by John Selfridge.

Given D, P, and Q, there are recurrence relations that enable us to quickly compute   and   without having to compute all the intermediate terms; see Lucas sequence-Other relations. First, we can double the subscript from   to   in one step using the recurrence relations

 
 .

Next, we can increase the subscript by 1 using the recurrences

 
 .

(If either of these numerators is odd, we can make it be even by increasing it by n, because all of these calculations are carried out modulo n.) Observe that, for each term that we compute in the U sequence, we compute the corresponding term in the V sequence. As we proceed, we also compute the same, corresponding powers of Q.

We use the bits of the binary expansion of n + 1, starting at the leftmost bit, to determine which terms in the U sequence need to be computed. For example, if n + 1 = 44 (= 101100 in binary), then, using these bits from left to right, we compute U1, U2, U4, U5, U10, U11, U22, and U44. We also compute the same-numbered terms in the V sequence, along with Q1, Q2, Q4, Q5, Q10, Q11, Q22, and Q44.

By the end of the calculation, we will have computed Un+1, Vn+1, and Qn+1. We then check congruence (2) using our known value of Un+1.

When D, P, and Q are chosen as described above, the first 10 Lucas pseudoprimes are (see page 1401 of [35]): 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, and 10877 (sequence A217120 in the OEIS)

The strong versions of the Lucas test can be implemented in a similar way.

When D, P, and Q are chosen as described above, the first 10 strong Lucas pseudoprimes are: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519 (sequence A217255 in the OEIS)

To calculate a list of extra strong Lucas pseudoprimes, set Q = 1. Then try P = 3, 4, 5, 6, ..., until a value of   is found so that the Jacobi symbol  . With this method for selecting D, P, and Q, the first 10 extra strong Lucas pseudoprimes are 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, and 72389 (sequence A217719 in the OEIS)

Checking additional congruence conditions

edit

If we have checked that congruence (2) is true, there are additional congruence conditions we can check that have almost no additional computational cost. If n happens to be composite, these additional conditions may help discover that fact.

If n is an odd prime and  , then we have the following (see equation 2 on page 1392 of [35]):

 

Although this congruence condition is not, by definition, part of the Lucas probable prime test, it is almost free to check this condition because, as noted above, the value of Vn+1 was computed in the process of computing Un+1.

If either congruence (2) or (3) is false, this constitutes a proof that n is not prime. If both of these congruences are true, then it is even more likely that n is prime than if we had checked only congruence (2).

If Selfridge's method (above) for choosing D, P, and Q happened to set Q = −1, then we can adjust P and Q so that D and   remain unchanged and P = Q = 5 (see Lucas sequence-Algebraic relations). If we use this enhanced method for choosing P and Q, then 913 = 11·83 is the only composite less than 108 for which congruence (3) is true (see page 1409 and Table 6 of;[35]).

Here is another congruence condition that is true for primes and that is trivial to check.

Recall that   is computed during the calculation of  . It would be easy to save the previously-computed power of  , namely,  .

Next, if n is prime, then, by Euler's criterion,

  .

(Here,   is the Legendre symbol; if n is prime, this is the same as the Jacobi symbol). Therefore, if n is prime, we must have

  .

The Jacobi symbol on the right side is easy to compute, so this congruence is easy to check. If this congruence does not hold, then n cannot be prime.

Additional congruence conditions that must be satisfied if n is prime are described in Section 6 of.[35] If any of these conditions fails to hold, then we have proved that n is not prime.

Effective universality

edit

Some recent work has focused on effective universality. Under the conditions stated at the beginning of this article, there exist values of t that satisfy inequality (1). An effective universality theorem places an upper bound on the smallest such t.

For example, in 2003, Garunkštis proved that if   is analytic in   with  , then for any ε in  , there exists a number   in   such that

 .

For example, if  , then the bound for t is  .

Bounds can also be obtained on the measure of these t values, in terms of ε:

 .

For example, if  , then the right-hand side is  . See [85]: p. 210 .

Universality of other zeta functions

edit

The Dirichlet L-functions show not only universality, but a certain kind of joint universality that allow any set of functions to be approximated by the same value(s) of t in different L-functions, where each function to be approximated is paired with a different L-function.[86] [79]: Section 4 

A similar universality property has been shown for the Lerch zeta function  , at least when the parameter α is a transcendental number. [79]: Section 5  Sections of the Lerch zeta-function have also been shown to have a form of joint universality. [79]: Section 6 

For probable prime

edit

The following is for the probable prime article.

If n is large, raising a to a large power such as n - 1 (mod n) can be done efficiently as shown in the following examples. The general technique is Exponentiation by squaring.

Example probable prime test

edit

Test whether   is a probable prime. We will use base 2, but many other choices for the base would work just as well. We will compute  .

  • Step 1: To make the exponentiation easier, factor  .
  • Step 2:  
  • Step 3:  
  • Step 4:  
  • Step 5:  
  • Step 6:  .

This last result is not 1, so 209 is not a probable prime base 2. Therefore, 209 is definitely composite.

Variations

edit

An Euler probable prime to base a is an integer that is indicated prime by the somewhat stronger Euler's criterion that for any prime p, a(p − 1)/2 equals   modulo p, where   is the Legendre symbol. An Euler probable prime which is composite is called an Euler–Jacobi pseudoprime (or an Euler pseudoprime) to base a. The smallest Euler pseudoprime to base 2 is 561 (see p. 1004 of [34]). There are 11347 Euler pseudoprimes base 2 that are less than 25·109 (see p. 1005 of [34]).

This test may be strengthened by using the fact that the only square roots of 1 modulo a prime are 1 and −1. Let n - 1 = d · 2s, where d is odd. The number n is a strong probable prime (SPRP) to base a if one of the following conditions holds:

 
 

A strong probable prime to base a that is composite is called a strong pseudoprime to base a.

For a given base a, the strong probable primes form a proper subset of the Euler probable primes; further, the Euler probable primes form a proper subset of probable primes.

The smallest strong pseudoprime base 2 is 2047 (see p. 1004 of [34]). There are 4842 strong pseudoprimes base 2 that are less than 25·109 (see p. 1005 of [34]).

There are also Lucas probable primes, which are based on Lucas sequences. A Lucas probable prime test can be used alone. The Baillie-PSW primality test combines a Lucas test with a strong probable prime test.

Example of SPRP

edit

Test whether 97 is probably prime:

  • Step 1: Find   and   for which  , where   is odd
    • Dividing by 2 (5 times) until we get a quotient that is odd, we see that  , so   and  
  • Step 2: Choose  ,  . We will choose  
  • Step 3: Calculate   , i.e.  . This isn't congruent to  , so we continue and test the next condition
  • Step 4: Calculate   for   . If one of these is congruent to   , then   is probably prime. Otherwise,   is definitely composite
    •  
    •  
    •  
    •  ; this is -1 so we can stop here
  • Therefore,   is probably prime; in fact, it is also a strong probable prime to base 2.

Another example: test whether 321 is probably prime.

  • Step 1: Find   and   for which  , where   is odd
    • Dividing by 2 (6 times) until we get a quotient that is odd, we see that  , so   and  
  • Step 2: Choose   from 2 through 320. We will choose  
  • Step 3: Calculate   , i.e.  . This isn't congruent to  , so we continue and test the next condition
  • Step 4: Calculate   for   . If one of these is congruent to   , then   is probably prime. Otherwise,   is definitely composite
    •  
    •  
    •  
    •  
    •  
    •  
  • This not -1, so   is definitely composite.

Right-to-left binary method

edit

In this example, the base b is raised to the exponent e = 13. The exponent is 1101 in binary. There are four binary digits, so the loop executes four times. The bits in right-to-left order are 1, 0, 1, 1.

First, initialize the result   to 1 and preserve the value of b in the variable x:

 .
Step 1) bit 1 is 1, so set  ;
set  .
Step 2) bit 2 is 0, so do not reset R;
set  .
Step 3) bit 3 is 1, so set  ;
set  .
Step 4) bit 4 is 1, so set  ;
This is the last step so we don't need to square x.

We are done: R is now  .

Here is the above calculation, where we compute b = 4 to the power e = 13, performed modulo 497.

Initialize:

  and  .
Step 1) bit 1 is 1, so set  ;
set  .
Step 2) bit 2 is 0, so do not reset R;
set  .
Step 3) bit 3 is 1, so set  ;
set  .
Step 4) bit 4 is 1, so set  ;

We are done: R is now  , the same result obtained in the previous algorithms.

The running time of this algorithm is O(log exponent). When working with large values of exponent, this offers a substantial speed benefit over the previous two algorithms, whose time is O(exponent). For example, if the exponent was 220 = 1048576, this algorithm would have 20 steps instead of 1048576 steps.

Left-to-right binary exponentiation

edit

there are two articles on this general subject:

Exponentiation by squaring#Basic method
and
binary exponentiation

We can also use the bits of the exponent in left to right order. In practice, we would usually want the result modulo some modulus m. In that case, we would reduce each multiplication result (mod m) before proceeding. For simplicity, the modulus calculation is omitted here. This example shows how to compute   using left to right binary exponentiation. The exponent is 1101 in binary; there are 4 bits, so there are 4 iterations.

Initialize the result to 1:  .

Step 1)  ; bit 1 = 1, so compute  ;
Step 2)  ; bit 2 = 1, so compute  ;
Step 3)  ; bit 3 = 0, so we are done with this step;
Step 4)  ; bit 4 = 1, so compute  .

put this into the 'Basic method' part of the article Exponentiation by squaring:

Basic method

edit

The method is based on the observation that, for a positive integer n, we have

 

This method uses the bits of the exponent to determine which powers are computed.

This example shows how to compute   using this method. The exponent, 13, is 1101 in binary. The bits are used in left to right order. The exponent has 4 bits, so there are 4 iterations.

First, initialize the result to 1:  .

Step 1)  ; bit 1 = 1, so compute  ;
Step 2)  ; bit 2 = 1, so compute  ;
Step 3)  ; bit 3 = 0, so we are done with this step;
Step 4)  ; bit 4 = 1, so compute  .

This may be implemented as the following recursive algorithm:


References

edit
  • Ingham, A.E. (1932), The Distribution of Prime Numbers, Cambridge Tracts in Mathematics and Mathematical Physics, vol. 30, Cambridge University Press. Reprinted 1990, ISBN 978-0-521-39789-6, MR1074573
  • Montgomery, Hugh L.; Vaughan, Robert C. (2007), Multiplicative Number Theory I. Classical Theory, Cambridge studies in advanced mathematics, vol. 97, Cambridge University Press.ISBN 978-0-521-84903-6
  1. ^ a b c Jerrard, Richard P.; Wetzel, John E.; Yuan, Liping (April 2017). "Platonic Passages". Mathematics Magazine. 90 (2). Washington, DC: Mathematical Association of America: 87–98. doi:10.4169/math.mag.90.2.87.
  2. ^ Scriba, Christoph J. (1968), "Das Problem des Prinzen Ruprecht von der Pfalz", Praxis der Mathematik (in German), 10 (9): 241–246, MR 0497615
  3. ^ Huber, Greg; Shultz, Kay Pechenick; Wetzel, John E. (June–July 2018). "The n-Cube is Rupert". American Mathematical Monthly. 125 (6). Washington, DC: Mathematical Association of America: 505–512. doi:10.1080/00029890.2018.1448197.{{cite journal}}: CS1 maint: date format (link)
  4. ^ Chai, Ying; Yuan, Liping; Zamfirescu, Tudor (June–July 2018). "Rupert Property of Archimedean Solids". American Mathematical Monthly. 125 (6). Washington, DC: Mathematical Association of America: 497–504. doi:10.1080/00029890.2018.1449505.{{cite journal}}: CS1 maint: date format (link)
  5. ^ Lavau, Gérard (December 2019). "The Truncated Tetrahedron is Rupert". American Mathematical Monthly. 126 (10). Washington, DC: Mathematical Association of America: 929–932. doi:10.1080/00029890.2019.1656958.
  6. ^ Rawal, Bipul; Joshi, Rija; Bohra, Hemendra; Tamrakar, Aswain Bir Singh. "Historic Towns in Transition-Documentation and Restoration of the Earthen Palaces in Upper Mustang" (PDF). Nepal National Reconstruction Authority. Retrieved 5 December 2023.
  7. ^ Elbakyan, Alexandra; Bohannon, John (August 16, 2021). "Data from: 'Who's downloading pirated papers? Everyone'". Dryad. Retrieved 12 February 2023.{{cite web}}: CS1 maint: url-status (link)
  8. ^ Chamberland, Marc (2015), Single Digits: In Praise of Small Numbers, Princeton University Press, pp. 104–105, ISBN 9781400865697.
  9. ^ a b c Anthony Ray Hinton; Lara Love Hardin (2018). The Sun Does Shine. New York, NY: St. Martin's Press. ISBN 978-1-250-20579-7.
  10. ^ "LIGHTFOOT v. UNITED STATES, 355 U.S. 2 (1957)". Justia Law. Retrieved 2019-11-18.
  11. ^ "Hinton v. Alabama, 571 U.S. 263 (2014)". Justia Law. Retrieved 2023-08-17.
  12. ^ "Miller v. Alabama, 567 U.S. 460 (2012)". Justia Law. Retrieved 2023-08-17.
  13. ^ "Miller v. Alabama, 567 U.S. 460 (2012)". Findlaw. Retrieved 2023-08-17.
  14. ^ Henry B. Collins (1964) [First published 1888]. introduction. The Central Eskimo. By Boas, Franz. University of Nebraska Press. ISBN 0-8032-5016-9.
  15. ^ a b Irwin, Frank (May 1916). "A Curious Convergent Series". American Mathematical Monthly. 23 (5). Washington, DC: Mathematical Association of America: 149–152. doi:10.2307/2974352. ISSN 0002-9890. JSTOR 2974352.
  16. ^ Baillie, Robert (2023). "Summing the curious series of Kempner and Irwin". arXiv:0806.4410 [math.CA].
  17. ^ "USBCHA Rules – Sheepdogs and Cattledogs" (PDF). Retrieved 30 July 2019.
  18. ^ https://www.sciencedirect.com/science/article/abs/pii/S002396901300026X
  19. ^ Pilley, John W. (2013). "Border collie comprehends sentences containing a prepositional object, verb, and direct object". Learning and Motivation. 44 (4): 229–240. doi:10.1016/j.lmot.2013.02.003.
  20. ^ Frank, P.; Goldstein, S.; Kac, M.; Prager, W.; Szegö, G.; Birkhoff, G., eds. (1964). Selected Papers of Richard von Mises. Vol. 2. Providence, Rhode Island: Amer. Math. Soc. pp. 313–334.
  21. ^ Mario Cortina Borja; John Haigh (September 2007). "The Birthday Problem". Significance. 4 (3). Royal Statistical Society: 124–127. doi:10.1111/j.1740-9713.2007.00246.x.
  22. ^ a b c Elk, Anne (November 16, 1972). Anne Elk's Theory on Brontosauruses.
  23. ^ a b c Seidelmann, P. Kenneth; Urban, Sean E., eds. (2013). Explanatory Supplement to the Astronomical Almanac (3rd ed.). University Science Books. ISBN 978-1-891389-85-6. Cite error: The named reference "ExplanatorySupplement3" was defined multiple times with different content (see the help page).
  24. ^ Here is some optional text, inside the ref, but outside the cite web."Alumni Hall of Fame Members". University of Maryland Alumni Association. The University of Maryland. 2005. Archived from the original on 2007-06-23. Retrieved 2009-06-10. This text is in a quote field inside cite web
  25. ^ Sun, Kwok. (2017). Our Place in the Universe: Understanding Fundamental Astronomy from Ancient Discoveries, second edition. Cham, Switzerland: Springer. ISBN 978-3-319-54171-6, p. 120; see also Needham, Joseph; Wang, Ling. (1995) [1959]. Science and Civilization in China: Mathematics and the Sciences of the Heavens and the Earth, vol. 3, reprint edition. Cambridge: Cambridge University Press. ISBN 0-521-05801-5, p. 220.
  26. ^ Arthur E. Danese (1965). Advanced Calculus. Vol. 1. Boston, MA: Allyn and Bacon, Inc. p. 439.
  27. ^ Wilfred Kaplan (1991). Advanced Calculus (4th ed.). Reading, MA: Addison Wesley. p. 519. ISBN 0-201-57888-3.
  28. ^ Georgi P. Tolstov (1962). Fourier Series. Translated by Silverman, Richard. Englewood Cliffs, NJ: Prentice-Hall, Inc. p. 119.
  29. ^ Farhi, Bakir (10 May 2011). "An Explicit Formula Generating the Non-Fibonacci Numbers". arXiv:1105.1127v2 [math.NT].
  30. ^ Caldwell, Chris (2006-07-07). "The Prime Database". Retrieved 2017-05-11.
  31. ^ Richard Pinch, "The Carmichael numbers up to 1021", May 2007.
  32. ^ Pinch, Richard (December 2007). Anne-Maria Ernvall-Hytönen (ed.). The Carmichael numbers up to 1021 (PDF). Proceedings of Conference on Algorithmic Number Theory. Vol. 46. Turku, Finland: Turku Centre for Computer Science. pp. 129–131. Retrieved 2017-06-26.
  33. ^ Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3.
  34. ^ a b c d e Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.
  35. ^ a b c d e f g h i Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. JSTOR 2006406. MR 0583518. Cite error: The named reference "lpsp" was defined multiple times with different content (see the help page).
  36. ^ John Brillhart; D. H. Lehmer; J. L. Selfridge (April 1975). "New Primality Criteria and Factorizations of 2m ± 1". Mathematics of Computation. 29 (130): 620–647. doi:10.2307/2005583. JSTOR 2005583.
  37. ^ a b c Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3.
  38. ^ a b Desmedt, Yvo (2010). "Encryption Schemes". In Atallah, Mikhail J.; Blanton, Marina (eds.). Algorithms and theory of computation handbook: Special topics and techniques. CRC Press. pp. 10–23. ISBN 978-1-58488-820-8.
  39. ^ a b c d Richard E. Crandall; Carl Pomerance (2005). Prime numbers: A computational perspective (2nd ed.). Springer-Verlag. ISBN 0-387-25282-7. Cite error: The named reference "CrandallPomerance" was defined multiple times with different content (see the help page).
  40. ^ David Harvey, Joris Van Der Hoeven (2019). Integer multiplication in time O(n log n)
  41. ^ a b Regg Cohn, Martin (March 30, 2015). "PC blunder over Highway 407 looms over Liberals on Hydro: Cohn". Toronto Star. Retrieved December 6, 2017. The 407 deal is now considered a financial blunder on a par with Newfoundland's lease of Churchill Falls to Quebec, and China's surrender of Hong Kong to Britain, for equally ill-fated 99-year leases.
  42. ^ a b Siekierska, Alicja (5 April 2019). "Worst deal ever? The 407 is worth $30B today – Ontario sold it for $3.1B in 1999". ca.finance.yahoo.com. Retrieved 27 June 2019.
  43. ^ a b Zochodne, Geoff (9 April 2019). "For whom the road tolls: Ontario's $32.5 billion highway highlights private asset boom". Financial Post. Retrieved 9 April 2019.
  44. ^ a b c Linda McQuaig (2019). The Sport and Prey of Capitalists: How the Rich Are Stealing Canada's Public Wealth. Toronto: Dundurn Press. ISBN 978-1-45974-366-3.
  45. ^ "Highway 407 Revisited – smart tollroad extension". Retrieved 3 October 2019.
  46. ^ Smith, Graeme (9 January 2002). "Bank values Highway 407 at four times the sale price". theglobeandmail.com. Retrieved 3 October 2019.
  47. ^ a b c David Bressoud; Stan Wagon (2000). A Course in Computational Number Theory. New York: Key College Publishing in cooperation with Springer. ISBN 978-1-930190-10-8.
  48. ^ a b c d Paulo Ribenboim (1996). The New Book of Prime Number Records. Springer-Verlag. ISBN 0-387-94457-5.
  49. ^ Di Porto, Adina; Filipponi, Piero; Montolivo, Emilio (1990). "On the generalized Fibonacci pseudoprimes". Fibonacci Quarterly. 28: 347–354. CiteSeerX 10.1.1.388.4993.
  50. ^ David Singmaster (1983). "Some Lucas Pseudoprimes". Abstracts Amer. Math. Soc. 4 (83T-10-146): 197.
  51. ^ Di Porto, Adina (1993). "Nonexistence of Even Fibonacci Pseudoprimes of the First Kind". Fibonacci Quarterly. 31: 173–177. CiteSeerX 10.1.1.376.2601.
  52. ^ Adina Di Porto; Piero Filipponi (1989). "More on the Fibonacci Pseudoprimes" (PDF). Fibonacci Quarterly. 27 (3): 232–242.
  53. ^ Di Porto, Adina; Filipponi, Piero; Montolivo, Emilio (1990). "On the generalized Fibonacci pseudoprimes". Fibonacci Quarterly. 28: 347–354. CiteSeerX 10.1.1.388.4993.
  54. ^ V. E. Hoggatt, Jr.; Marjorie Bicknell (September 1974). "Some Congruences of the Fibonacci Numbers Modulo a Prime p". Mathematics Magazine. 47 (4): 210–214. doi:10.2307/2689212. JSTOR 2689212.
  55. ^ David Singmaster (1983). "Some Lucas Pseudoprimes". Abstracts Amer. Math. Soc. 4 (83T-10-146): 197.
  56. ^ "Pseudoprime Statistics and Tables". Retrieved 5 May 2019.
  57. ^ P. S. Bruckman (1994). "Lucas Pseudoprimes are odd". Fibonacci Quarterly. 32: 155–157.
  58. ^ Di Porto, Adina (1993). "Nonexistence of Even Fibonacci Pseudoprimes of the First Kind". Fibonacci Quarterly. 31: 173–177. CiteSeerX 10.1.1.376.2601.
  59. ^ Kevin Ford (November 2002). "Vinogradov's Integral and Bounds for the Riemann Zeta Function" (PDF). Proc. London Math. Soc. 85 (3): 565–633. doi:10.1112/S0024611502013655.
  60. ^ Tim Trudgian (February 2016). "Updating the error term in the prime number theorem". Ramanujan Journal. 39 (2): 225–234. doi:10.1007/s11139-014-9656-6.
  61. ^ a b Dusart, Pierre (2 Feb 2010). "Estimates of Some Functions Over Primes without R.H.". arXiv:1002.0442v1 [math.NT].
  62. ^ Dusart, Pierre (January 2018). "Explicit estimates of some functions over primes". Ramanujan Journal. 45 (1): 225–234. doi:10.1007/s11139-016-9839-4.
  63. ^ Fridman, Dylan; Garbulsky, Juli; Glecer, Bruno; Grime, James; Tron Florentin, Massi (2019). "A Prime-Representing Constant". American Mathematical Monthly. 126 (1). Washington, DC: Mathematical Association of America: 70–73. doi:10.1080/00029890.2018.1530554.
  64. ^ Clausing, Achim (2018). "Ducci matrices". American Mathematical Monthly. 125 (10). Washington, DC: Mathematical Association of America: 901–921. doi:10.1080/00029890.2018.1523661.
  65. ^ Brockman, Greg (2007). "Asymptotic behaviour of certain Ducci sequences" (PDF). Fibonacci Quarterly.
  66. ^ Voronin, S. M. (1975). "Theorem on the Universality of the Riemann Zeta Function". Izv. Akad. Nauk SSSR, Ser. Matem. 39: 475–486. Reprinted in Math. USSR Izv. (1975) 9: 443–445.
  67. ^ Ramūnas Garunkštis; Antanas Laurinčikas; Kohji Matsumoto; Jörn Steuding; Rasa Steuding (2010). "Effective uniform approximation by the Riemann zeta-function". Publicacions Matemàtiques. 54: 209–219. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 43736941.
  68. ^ Bhaskar Bagchi (1982). "A Joint Universality Theorem for Dirichlet L-Functions". Mathematische Zeitschrift. 181: 319–334. ISSN 0025-5874.
  69. ^ Ramūnas Garunkštis (July 2011). "Self-approximation of Dirichlet L-functions". Journal of Number Theory. 131 (7): 1286–1295. arXiv:1006.1507. doi:10.1016/j.jnt.2011.01.013.
  70. ^ D. R. Heath-Brown (March 1986). "Artin's Conjecture for Primitive Roots". The Quarterly Journal of Mathematics. 37 (1): 27–38. doi:10.1093/qmath/37.1.27.
  71. ^ M. Ram Murty (1988). "Artin's Conjecture for Primitive Roots". The Mathematical Intelligencer. 10 (4): 59–67. doi:10.1007/978-1-4613-0195-0_11.
  72. ^ Voronin, S. M. (1975). "Theorem on the Universality of the Riemann Zeta Function". Izv. Akad. Nauk SSSR, Ser. Matem. 39: 475–486. Reprinted in Math. USSR Izv. (1975) 9: 443–445.
  73. ^ Ramūnas Garunkštis; Antanas Laurinčikas; Kohji Matsumoto; Jörn Steuding; Rasa Steuding (2010). "Effective uniform approximation by the Riemann zeta-function". Publicacions Matemàtiques. 54: 209–219. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 43736941.
  74. ^ Bhaskar Bagchi (1982). "A Joint Universality Theorem for Dirichlet L-Functions". Mathematische Zeitschrift. 181: 319–334. ISSN 0025-5874.
  75. ^ Steuding, Jörn (2007). Value-Distribution of L-Functions. Lecture Notes in Mathematics. Berlin: Springer. p. 19. doi:10.1007/978-3-540-44822-8. ISBN 3-540-26526-0.
  76. ^ Paulius Drungilas; Ramūnas Garunkštis; Audrius Kačėnas (2013). "Universality of the Selberg zeta-function for the modular group". Forum Mathematicum. 25 (3). doi:10.1515/form.2011.127. ISSN 1435-5337.
  77. ^ Paulius Drungilas; Ramūnas Garunkštis; Audrius Kačėnas (2013). "Universality of the Selberg zeta-function for the modular group". Forum Mathematicum. 25 (3). doi:10.1515/form.2011.127. ISSN 1435-5337.
  78. ^ B. Bagchi (1982). "A Universality theorem for Dirichlet L-functions". Mat. Z. 181 (3): 319–334. doi:10.1007/BF01161980.
  79. ^ a b c d e f Kohji Matsumoto (2013). "A survey on the theory of universality for zeta and L-functions". Plowing and Starring Through High Wave Forms. Proceedings of the 7th China–Japan Seminar. The 7th China–Japan Seminar on Number Theory. Vol. 11. Fukuoka, Japan: World Scientific. pp. 95–144. arXiv:1407.4216. ISBN 978-981-4644-92-1.
  80. ^ Voronin, S. M. (1975). "Theorem on the Universality of the Riemann Zeta Function". Izv. Akad. Nauk SSSR, Ser. Matem. 39: 475–486. Reprinted in Math. USSR Izv. (1975) 9: 443–445.
  81. ^ Ramūnas Garunkštis; Antanas Laurinčikas; Kohji Matsumoto; Jörn Steuding; Rasa Steuding (2010). "Effective uniform approximation by the Riemann zeta-function". Publicacions Matemàtiques. 54: 209–219. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 43736941.
  82. ^ Bhaskar Bagchi (1982). "A Joint Universality Theorem for Dirichlet L-Functions". Mathematische Zeitschrift. 181: 319–334. ISSN 0025-5874.
  83. ^ Steuding, Jörn (2007). Value-Distribution of L-Functions. Lecture Notes in Mathematics. Berlin: Springer. p. 19. doi:10.1007/978-3-540-44822-8. ISBN 3-540-26526-0.
  84. ^ "Obliquity of the Ecliptic (Eps Mean)". Neoprogrammics.com. Retrieved 2014-05-13.
  85. ^ Ramūnas Garunkštis; Antanas Laurinčikas; Kohji Matsumoto; Jörn Steuding; Rasa Steuding (2010). "Effective uniform approximation by the Riemann zeta-function". Publicacions Matemàtiques. 54: 209–219. JSTOR 43736941.
  86. ^ B. Bagchi (1982). "A Universality theorem for Dirichlet L-functions". Mat. Z. 181 (3): 319–334. doi:10.1007/BF01161980.

Further reading

edit
  • Karatsuba, Anatoly A.; Voronin, S. M. (2011). The Riemann Zeta-Function. de Gruyter Expositions In Mathematics. Berlin: de Gruyter. ISBN 978-3110131703.
  • Laurinčikas, Antanas (1996). Limit Theorems for the Riemann Zeta-Function. Mathematics and Its Applications. Vol. 352. Berlin: Springer. doi:10.1007/978-94-017-2091-5. ISBN 978-90-481-4647-5.
  • Steuding, Jörn (2007). Value-Distribution of L-Functions. Lecture Notes in Mathematics. Berlin: Springer. p. 19. doi:10.1007/978-3-540-44822-8. ISBN 3-540-26526-0.
  • Titchmarsh, Edward Charles; Heath-Brown, David Rodney ("Roger") (1986). The Theory of the Riemann Zeta-function (2nd ed.). Oxford: Oxford U. P. ISBN 0-19-853369-1.


edit