User:MathPerson/sandbox

Sandbox.

John W. Pilley
Born	(1928-07-01)July 1, 1928 Memphis, Tennessee
Died	June 17, 2018(2018-06-17) (aged 89) Spartanburg, South Carolina
Nationality	American
Occupation(s)	professor, ethologist
Years active	1969-2018
Known for	Owner and trainer of Chaser the border collie
Spouse	Sally Pilley (married 1955)
Academic background
Education	PhD psychology (1969)
Alma mater	Abilene Christian University, Princeton Theological Seminary, Stetson University, Memphis State
Academic work
Institutions	Wofford College

Generalizations

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. All five Platonic solids: the cube, the regular tetrahedron, regular octahedron, regular dodecahedron, and regular icosahedron, have the Rupert property. It has been conjectured that all 3-dimensional convex polyhedra have this property. For n greater than 2, the n-dimensional hypercube also has the Rupert property.

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. and truncated tetrahedron

Coin

Sci-Hub

Reuleaux polygon with 11 sides.

Quote 1. Quote 2. Quote 3.

Claude Lightfoot's case in the Supreme Court.

Hinton's case.

Miller v Alabama

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

Inuit had games using string figures.

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

Irwin's generalizations of Kempner's results

In 1916, Irwin 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 showed that the sum of this last series is about 23.04428708074784831968.

Misc stuff

Rules for Sheepdog Herding Competitions

Info about Chaser. Was "". Used citation bot to change it to this.

Birthday problem.

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), (Montgomery & Vaughan 2007). It is already known that 1/2 ≤ β ≤ 1 (Ingham 1932).

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

Here is a book.

This refers to chapter 11 of the book.

This refers to a section of the book.

Citation to something on the wayback machine.

This is from a discussion about precession. 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 $f(x)$ is a square-integrable function over $[-\pi ,\pi ]$ (i.e., $f(x)$ and $f^{2}(x)$ are integrable on that interval), with the Fourier series

$f(x)\simeq {\frac {a_{0}}{2}}+\sum _{n=1}^{\infty }(a_{n}\cos(nx)+b_{n}\sin(nx))$.

Then

${\frac {1}{\pi }}\int _{-\pi }^{\pi }f^{2}(x)dx={\frac {a_{0}^{2}}{2}}+\sum _{n=1}^{\infty }(a_{n}^{2}+b_{n}^{2})$.

For $n\geq 2$, the $n$th non-Fibonacci number (i.e., 4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, ...) is $\left\lfloor n+\log _{\varphi }\left({\sqrt {5}}\left(n+\log _{\varphi }\left(n{\sqrt {5}}\right)\right)-5+{\frac {3}{n}}\right)-2\right\rfloor$

($\log _{\varphi }(x)$ can be computed using logarithms to other, standard bases. For example, $\log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )$.)

Chris Caldwell's Prime Pages

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

Factorization.

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

Try this below and see if it works.

Here is the LPSP paper.

Here is the BLS paper.

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

$\left|\zeta (s+it)-f(s)\right|<\varepsilon$ (1)

for all $s\in U$.

Definition (of Fermat pseudoprime)

Fermat's little theorem states that if n is prime and a is coprime to n, then a^n-1 - 1 is divisible by n. In other words,

$a^{n-1}\equiv 1{\pmod {n}}$,

(where mod refers to the modulo operation).

The converse is usually not true. That is, if n is not prime, then $a^{n-1}$ is usually not $\equiv 1{\pmod {n}}$. This is the basis for the Fermat primality test.

If $a^{n-1}\equiv 1{\pmod {n}}$, then n is called a probable prime to base a.

If $a^{n-1}\equiv 1{\pmod {n}}$ and n is composite, then n is called a Fermat pseudoprime to base a.

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.

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: 2³⁴⁰ = 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.

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.

Formal definition

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

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

$a^{d}\equiv 1{\pmod {n}}$

or

$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad {\mbox{ for some }}0\leq r<s.$

(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)

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

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

$a^{d}\equiv 1{\pmod {n}}$

or

$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad {\mbox{ for some }}0\leq r<s.$

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

CNT

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

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

Multiplication

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.

Primality test

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

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

These references are needed below, so put them here temporarily.

Privatization

The privatization of the road, the toll rate increases, and the 99-year lease period have been widely criticized.

• 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.

• 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.

• 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. By 2019, the estimated value had risen to C$30 billion.

• 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. 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.

Baillie-PSW primality test

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. It has been shown that there are no counterexamples for n $<2^{64}$.

Fibonacci pseudoprimes

$U_{\delta (n)}\equiv 0{\pmod {n}}.$ (1)

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

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, page 142 of, or page 127 of ) 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 (, pages 272–273) and Crandall and Pomerance (, 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 10¹¹ also being base-2 Fermat pseudoprimes.

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

${\text{ }}(5){\text{ }}V_{n}\equiv P{\pmod {n}}.$

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. Using this definition, the first ten Fibonacci pseudoprimes are 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, and 15251 ( page 129) (sequence A005845 in the OEIS). This sequence appears to have been first studied by Singmaster.

It has been shown that there are no even Fibonacci pseudoprimes with the second definition using equation (5). 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 ) we also have

${\text{ }}(5){\text{ }}V_{n}\equiv P{\pmod {n}}.$

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. Using this definition, the first ten Fibonacci pseudoprimes are 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, and 15251 ( 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. Singmaster computed these pseudoprimes up to 100000. Jacobsen lists all 111443 of these pseudoprimes less than 10¹³.

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

Using the bits

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: 1₂ = 1, 10₂ = 2, 100₂ = 4, 101₂ = 5, 1010₂ = 10, 1011₂ = 11, 10110₂ = 22, 101100₂ = 44. Therefore, we compute U₁, U₂, U₄, U₅, U₁₀, U₁₁, U₂₂, and U₄₄. We also compute the same-numbered terms in the V sequence, along with Q¹, Q², Q⁴, Q⁵, Q¹⁰, Q¹¹, Q²², and Q⁴⁴.

Better results

In 1899, de la Vallée Poussin proved that

$\pi (x)=\operatorname {li} (x)+O\left(xe^{-a{\sqrt {\ln x}}}\right)\quad {\text{as }}x\to \infty$

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

More precise estimates of $\pi (x)\!$ are now known. For example, in 2002, Kevin Ford proved that

$\pi (x)=\operatorname {li} (x)+O\left(x\exp \left(-0.2098(\ln x)^{\frac {3}{5}}(\ln \ln x)^{-{\frac {1}{5}}}\right)\right)$.

In 2016, Tim Trudgian proved an explicit upper bound for the difference between $\pi (x)$ and $\operatorname {li} (x)$:

${\big |}\pi (x)-\operatorname {li} (x){\big |}\leq 0.2795{\frac {x}{(\ln x)^{3/4}}}\exp \left(-{\sqrt {\frac {\ln x}{6.455}}}\right)$

for $x\geq 229$.

For most values of $x$ we are interested in (i.e., when $x$ is not unreasonably large) $\operatorname {li} (x)\!$ is greater than $\pi (x)\!$. However, $\pi (x)-\operatorname {li} (x)$ is known to change sign infinitely many times. For a discussion of this, see Skewes' number.

Inequalities

Dusart 2010 is this.

In , Dusart proved (Proposition 6.6) that, for $n\geq 688383$,

$p_{n}\leq n\left(\ln n+\ln \ln n-1+{\frac {\ln \ln n-2}{\ln n}}\right)$ ,

and (Proposition 6.7) that, for $n\geq 3$,

$p_{n}\geq n\left(\ln n+\ln \ln n-1+{\frac {\ln \ln n-2.1}{\ln n}}\right)$ .

More recently, Dusart has proved (Theorem 5.1) that, for $x>1$,

$\pi (x)\leq {\frac {x}{\ln x}}\left(1+{\frac {1}{\ln x}}+{\frac {2}{\ln ^{2}x}}+{\frac {7.59}{\ln ^{3}x}}\right)$ ,

and that, for $x\geq 88789$,

$\pi (x)>{\frac {x}{\ln x}}\left(1+{\frac {1}{\ln x}}+{\frac {2}{\ln ^{2}x}}\right)$ .

A function that represents all primes

Given the constant $f_{1}=2.920050977316...$, for $n\geq 2$, define the sequence

$f_{n}=\left\lfloor f_{n-1}\right\rfloor (f_{n-1}-\left\lfloor f_{n-1}\right\rfloor +1)$ (1)

where $\left\lfloor \cdot \right\rfloor$ is the floor function. Then for $n\geq 1$, $\left\lfloor f_{n}\right\rfloor$ equals the $n^{th}$ prime: $\left\lfloor f_{1}\right\rfloor =2$, $\left\lfloor f_{2}\right\rfloor =3$, $\left\lfloor f_{3}\right\rfloor =5$, etc. The initial constant $f_{1}=2.920050977316$ given in the article is precise enough for equation (1) to generate the primes through 37, the $12^{th}$ prime.

The exact value of $f_{1}$ that generates all primes is given by the rapidly-converging series

$f_{1}=\sum _{n=1}^{\infty }{\frac {p_{n}-1}{P_{n}}}={\frac {2-1}{1}}+{\frac {3-1}{2}}+{\frac {5-1}{2\cdot 3}}+{\frac {7-1}{2\cdot 3\cdot 5}}\cdots$,

where $p_{n}$ is the $n^{th}$ prime, and $P_{n}$ is the product of all primes less than $p_{n}$. The more digits of $f_{1}$ 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: $f_{1}\simeq 2.920050977316134712092562917112019$. 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, $f_{1}$.

Demographics

Historical population

Year	Pop.	±%
1841	0	—
1851	0	0.00%
1881	3	—

Ducci

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, this 4-tuple converges to (0, 0, 0, 0) in four iterations: $(e,\pi ,{\sqrt {2}},1)\rightarrow (\pi -e,\pi -{\sqrt {2}},{\sqrt {2}}-1,e-1)\rightarrow (e-{\sqrt {2}},\pi -2{\sqrt {2}}+1,e-{\sqrt {2}},2e-\pi -1)\rightarrow$ $(\pi -e-{\sqrt {2}}+1,\pi -e-{\sqrt {2}}+1,\pi -e-{\sqrt {2}}+1,\pi -e-{\sqrt {2}}+1)\rightarrow (0,0,0,0)$

The properties presented here do not always hold for these generalisations. For example, a Ducci sequence starting with the n-tuple (1, q, q², q³) where q is the (irrational) positive root of the cubic $x^{3}-x^{2}-x-1=0$ does not reach (0,0,0,0) in a finite number of steps, although in the limit it converges to (0,0,0,0).

Universality April 2017 version

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. More recent work has included effective versions of Voronin's theorem and extending it to Dirichlet L-functions

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

Universality ORIGINAL May 2017 version

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. More recent work has included effective versions of Voronin's theorem and extending it to Dirichlet L-functions and Selberg zeta functions

Universality of other zeta functions

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

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.

A similar universality property has been shown for the Lerch zeta function $L(\lambda ,\alpha ,s)$, at least when the parameter α is a transcendental number. Sections of the Lerch zeta-function have also been shown to have a form of joint universality.

Universality NEW May 12 2017 version

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. More recent work has included effective versions of Voronin's theorem and extending it to Dirichlet L-functions.

Current latitude of arctic circle

Macro from the article about the arctic circle: The position of the Arctic Circle is not fixed; as of 7 November 2024, it runs 66°33′50.2″ north of the Equator.

Implementing a Fermat probable prime test

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: a¹, 'a², a³, a⁶, a¹², a¹³, a²⁶, and a⁵². Note that we can go from a²⁶ to a⁵² in just one step by squaring a²⁶. 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

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: a¹, 'a², a³, a⁶, a¹², a¹³, a²⁶, and a⁵². Note that we can go from a²⁶ to a⁵² in just one step by squaring a²⁶. 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

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 $\left({\tfrac {D}{n}}\right)=-1$, 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 $\left({\tfrac {D}{n}}\right)$ is −1. (If D and n have a prime factor in common, then $\left({\tfrac {D}{n}}\right)=0$). 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 , p. 1416. Once we have D, we set P = 1 and $Q=(1-D)/4$. 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 $U_{n+1}$ and $V_{n+1}$ without having to compute all the intermediate terms; see Lucas sequence-Other relations. First, we can double the subscript from $k$ to $2k$ in one step using the recurrence relations

$U_{2k}=U_{k}\cdot V_{k}$

$V_{2k}=V_{k}^{2}-2Q^{k}$.

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

$U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2$

$V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2$.

(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 U₁, U₂, U₄, U₅, U₁₀, U₁₁, U₂₂, and U₄₄. We also compute the same-numbered terms in the V sequence, along with Q¹, Q², Q⁴, Q⁵, Q¹⁰, Q¹¹, Q²², and Q⁴⁴.

By the end of the calculation, we will have computed U_n+1, V_n+1, and Qⁿ⁺¹. We then check congruence (2) using our known value of U_n+1.

When D, P, and Q are chosen as described above, the first 10 Lucas pseudoprimes are (see page 1401 of ): 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 $D=P^{2}-4Q$ is found so that the Jacobi symbol $\left({\tfrac {D}{n}}\right)=-1$. 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

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 $\left({\tfrac {D}{n}}\right)=-1$, then we have the following (see equation 2 on page 1392 of ):

${\text{ }}(3){\text{ }}V_{n+1}\equiv 2Q{\pmod {n}}.$

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 V_n+1 was computed in the process of computing U_n+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 $\left({\tfrac {D}{n}}\right)$ 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 10⁸ for which congruence (3) is true (see page 1409 and Table 6 of;).

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

Recall that $Q^{n+1}$ is computed during the calculation of $U_{n+1}$. It would be easy to save the previously-computed power of $Q$, namely, $Q^{(n+1)/2}$.

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

$Q^{(n-1)/2}\equiv \left({\tfrac {Q}{n}}\right){\pmod {n}}$ .

(Here, $\left({\tfrac {Q}{n}}\right)$ is the Legendre symbol; if n is prime, this is the same as the Jacobi symbol). Therefore, if n is prime, we must have

${\text{ }}(4){\text{ }}Q^{(n+1)/2}\equiv Q\cdot Q^{(n-1)/2}\equiv Q\cdot \left({\tfrac {Q}{n}}\right){\pmod {n}}$ .

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. If any of these conditions fails to hold, then we have proved that n is not prime.

Effective universality

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 $f(s)$ is analytic in $|s|\leq .05$ with $\max _{\left|s\right|\leq .05}\left|f(s)\right|\leq 1$, then for any ε in $0<\epsilon <1/2$, there exists a number $t$ in $0\leq t\leq \exp({\exp({10/\epsilon ^{13}})})$ such that

$\max _{\left|s\right|\leq .0001}\left|\log \zeta (s+{\frac {3}{4}}+it)-f(s)\right|<\epsilon$.

For example, if $\epsilon =1/10$, then the bound for t is $t\leq \exp({\exp({10/\epsilon ^{13}})})=\exp({\exp({10^{14}})})$.

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

$\liminf _{T\to \infty }{\frac {1}{T}}\,\lambda \!\left(\left\{t\in [0,T]:\max _{\left|s\right|\leq .0001}\left|\log \zeta (s+{\frac {3}{4}}+it)-f(s)\right|<\epsilon \right\}\right)\geq {\frac {1}{\exp({\epsilon ^{-13}})}}$.

For example, if $\epsilon =1/10$, then the right-hand side is $1/\exp({10^{13}})$. See .

Universality of other zeta functions

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.

A similar universality property has been shown for the Lerch zeta function $L(\lambda ,\alpha ,s)$, at least when the parameter α is a transcendental number. Sections of the Lerch zeta-function have also been shown to have a form of joint universality.

For probable prime

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

Test whether $n=209$ is a probable prime. We will use base 2, but many other choices for the base would work just as well. We will compute $2^{n-1}{\pmod {n}}$.

• Step 1: To make the exponentiation easier, factor $n-1=2^{4}\cdot 13$.
• Step 2: $2^{13}=2\cdot (2^{6})^{2}=2\cdot 64^{2}=8192\equiv 41{\pmod {209}}$
• Step 3: $2^{2\cdot 13}=(2^{13})^{2}\equiv 41^{2}\equiv 9{\pmod {209}}$
• Step 4: $2^{4\cdot 13}=(2^{2\cdot 13})^{2}\equiv 9^{2}\equiv 81{\pmod {209}}$
• Step 5: $2^{8\cdot 13}=(2^{4\cdot 13})^{2}\equiv 81^{2}\equiv 82{\pmod {209}}$
• Step 6: $2^{n-1}=2^{16\cdot 13}=(2^{8\cdot 13})^{2}\equiv 82^{2}\equiv 36{\pmod {209}}$.

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

Variations

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 $({\tfrac {a}{p}})$ modulo p, where $({\tfrac {a}{p}})$ 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 ). There are 11347 Euler pseudoprimes base 2 that are less than 25·10⁹ (see p. 1005 of ).

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 · 2^s, where d is odd. The number n is a strong probable prime (SPRP) to base a if one of the following conditions holds:

$a^{d}\equiv 1{\pmod {n}},\;$

$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ for some }}0\leq r\leq s-1.\,$

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 ). There are 4842 strong pseudoprimes base 2 that are less than 25·10⁹ (see p. 1005 of ).

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

Test whether 97 is probably prime:

• Step 1: Find $d$ and $s$ for which $97-1=96=d\cdot 2^{s}$, where $d$ is odd
  • Dividing by 2 (5 times) until we get a quotient that is odd, we see that $96=3\cdot 2^{5}$, so $d=3$ and $s=5$
• Step 2: Choose $a$, $1<a<97-1$. We will choose $2$
• Step 3: Calculate $a^{d}{\pmod {97}}$ , i.e. $2^{3}{\pmod {97}}$. This isn't congruent to $1{\pmod {97}}$, so we continue and test the next condition
• Step 4: Calculate $2^{3\cdot 2^{r}}{\pmod {97}}$ for $0\leq r<s$ . If one of these is congruent to $-1\equiv 96{\pmod {97}}$ , then $97$ is probably prime. Otherwise, $97$ is definitely composite
  • $r=0:2^{3}\equiv 8{\pmod {97}}$
  • $r=1:2^{6}\equiv (2^{3})^{2}\equiv 8^{2}\equiv 64{\pmod {97}}$
  • $r=2:2^{12}\equiv (2^{6})^{2}\equiv 64^{2}\equiv 22{\pmod {97}}$
  • $r=3:2^{24}\equiv (2^{12})^{2}\equiv 22^{2}\equiv 96\equiv -1{\pmod {97}}$; this is -1 so we can stop here
• Therefore, $97$ 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 $d$ and $s$ for which $321-1=320=d\cdot 2^{s}$, where $d$ is odd
  • Dividing by 2 (6 times) until we get a quotient that is odd, we see that $320=5\cdot 2^{6}$, so $d=5$ and $s=6$
• Step 2: Choose $a$ from 2 through 320. We will choose $2$
• Step 3: Calculate $a^{d}{\pmod {321}}$ , i.e. $2^{5}\equiv 32{\pmod {321}}$. This isn't congruent to $1{\pmod {321}}$, so we continue and test the next condition
• Step 4: Calculate $2^{5\cdot 2^{r}}{\pmod {321}}$ for $0\leq r<s$ . If one of these is congruent to $-1\equiv 320{\pmod {321}}$ , then $321$ is probably prime. Otherwise, $321$ is definitely composite
  • $r=0:2^{5}\equiv 32{\pmod {321}}$
  • $r=1:2^{10}\equiv (2^{5})^{2}\equiv 32^{2}\equiv 61{\pmod {321}}$
  • $r=2:2^{20}\equiv (2^{10})^{2}\equiv 61^{2}\equiv 190{\pmod {321}}$
  • $r=3:2^{40}\equiv (2^{20})^{2}\equiv 190^{2}\equiv 148{\pmod {321}}$
  • $r=4:2^{80}\equiv (2^{40})^{2}\equiv 148^{2}\equiv 76{\pmod {321}}$
  • $r=5:2^{160}\equiv (2^{80})^{2}\equiv 76^{2}\equiv 319\equiv -2{\pmod {321}}$
• This not -1, so $321$ is definitely composite.

Right-to-left binary method

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 $R$ to 1 and preserve the value of b in the variable x:

$R\leftarrow 1\,(=b^{0}){\text{ and }}x\leftarrow b$.

Step 1) bit 1 is 1, so set $R\leftarrow R\cdot x{\text{ }}(=b^{1})$;

set $x\leftarrow x^{2}{\text{ }}(=b^{2})$.

Step 2) bit 2 is 0, so do not reset R;

set $x\leftarrow x^{2}{\text{ }}(=b^{4})$.

Step 3) bit 3 is 1, so set $R\leftarrow R\cdot x{\text{ }}(=b^{5})$;

set $x\leftarrow x^{2}{\text{ }}(=b^{8})$.

Step 4) bit 4 is 1, so set $R\leftarrow R\cdot x{\text{ }}(=b^{13})$;

This is the last step so we don't need to square x.

We are done: R is now $b^{13}$.

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

Initialize:

$R\leftarrow 1\,(=b^{0})$ and $x\leftarrow b=4$.

Step 1) bit 1 is 1, so set $R\leftarrow R\cdot 4{\pmod {497}}\equiv 4{\pmod {497}}$;

set $x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}$.

Step 2) bit 2 is 0, so do not reset R;

set $x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}{\pmod {497}}\equiv 256{\pmod {497}}$.

Step 3) bit 3 is 1, so set $R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256{\pmod {497}}\equiv 30{\pmod {497}}$;

set $x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}{\pmod {497}}\equiv 429{\pmod {497}}$.

Step 4) bit 4 is 1, so set $R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429{\pmod {497}}\equiv 445{\pmod {497}}$;

We are done: R is now $4^{13}{\pmod {497}}\equiv 445{\pmod {497}}$, 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 2²⁰ = 1048576, this algorithm would have 20 steps instead of 1048576 steps.

Left-to-right binary exponentiation

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 $b^{13}$ 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: $r\leftarrow 1\,(=b^{0})$.

Step 1) $r\leftarrow r^{2}\,(=b^{0})$; bit 1 = 1, so compute $r\leftarrow r\cdot b\,(=b^{1})$;

Step 2) $r\leftarrow r^{2}\,(=b^{2})$; bit 2 = 1, so compute $r\leftarrow r\cdot b\,(=b^{3})$;

Step 3) $r\leftarrow r^{2}\,(=b^{6})$; bit 3 = 0, so we are done with this step;

Step 4) $r\leftarrow r^{2}\,(=b^{12})$; bit 4 = 1, so compute $r\leftarrow r\cdot b\,(=b^{13})$.

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

Basic method

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

$x^{n}={\begin{cases}x\,(x^{2})^{\frac {n-1}{2}},&{\mbox{if }}n{\mbox{ is odd}}\\(x^{2})^{\frac {n}{2}},&{\mbox{if }}n{\mbox{ is even}}.\end{cases}}$

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

This example shows how to compute $x^{13}$ 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: $r\leftarrow 1\,(=x^{0})$.

Step 1) $r\leftarrow r^{2}\,(=x^{0})$; bit 1 = 1, so compute $r\leftarrow r\cdot x\,(=x^{1})$;

Step 2) $r\leftarrow r^{2}\,(=x^{2})$; bit 2 = 1, so compute $r\leftarrow r\cdot x\,(=x^{3})$;

Step 3) $r\leftarrow r^{2}\,(=x^{6})$; bit 3 = 0, so we are done with this step;

Step 4) $r\leftarrow r^{2}\,(=x^{12})$; bit 4 = 1, so compute $r\leftarrow r\cdot x\,(=x^{13})$.

This may be implemented as the following recursive algorithm:

References

• 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

Further reading

• 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.

External links

• How to resolve Simpson's paradox? question on statistics Q&A site CrossValidated
• At the Plate, a Statistical Puzzler: Understanding Simpson's Paradox by Arthur Smith, August 20, 2010