prime numbers in arithmetic progression

SearchAdvancedHelp

(0.003 seconds)

11—20 of 945 matching pages

11: 27.3 Multiplicative Properties

§27.3 Multiplicative Properties

►Except for $\nu \left(n\right)$, $\mathrm{\Lambda }\left(n\right)$, $p_n$, and $\pi \left(x\right)$, the functions in §27.2 are multiplicative, which means $f(1)=1$ and … ►If $f$ is multiplicative, then the values $f(n)$ for $n>1$ are determined by the values at the prime powers. Specifically, if $n$ is factored as in (27.2.1), then …In particular, …

12: 1.2 Elementary Algebra

… ►

Arithmetic Progression

… ►

Geometric Progression

… ►The arithmetic mean of $n$ numbers $a_1,a_2,\mathrm{\dots },a_n$ is … ►If $r$ is a nonzero real number, then the weighted mean $M(r)$ of $n$ nonnegative numbers $a_1,a_2,\mathrm{\dots },a_n$, and $n$ positive numbers $p_1,p_2,\mathrm{\dots },p_n$ with … ►Multiplication of an $m\times n$ matrix $𝐀$ and an $m^{\prime }\times n^{\prime }$ matrix $𝐁$, giving the $m\times n^{\prime }$ matrix $𝐂=𝐀𝐁$ is defined iff $n=m^{\prime }$. …

13: 27.16 Cryptography

§27.16 Cryptography

►Applications to cryptography rely on the disparity in computer time required to find large primes and to factor large integers. ►For example, a code maker chooses two large primes $p$ and $q$ of about 400 decimal digits each. Procedures for finding such primes require very little computer time. The primes are kept secret but their product $n=pq$, an 800-digit number, is made public. …

14: 24.15 Related Sequences of Numbers

… ►

§24.15(i) Genocchi Numbers

… ►

§24.15(ii) Tangent Numbers

… ►

§24.15(iii) Stirling Numbers

… ►In (24.15.9) and (24.15.10) $p$ denotes a prime. … ►

§24.15(iv) Fibonacci and Lucas Numbers

…

15: 27.21 Tables

§27.21 Tables

►Lehmer (1914) lists all primes up to 100 06721. Bressoud and Wagon (2000, pp. 103–104) supplies tables and graphs that compare $\pi \left(x\right),x/\ln x$, and $\mathrm{li}\left(x\right)$. …9 lists all primes that are less than 1 00000. … ►

16: 27.19 Methods of Computation: Factorization

… ►Techniques for factorization of integers fall into three general classes: Deterministic algorithms, Type I probabilistic algorithms whose expected running time depends on the size of the smallest prime factor, and Type II probabilistic algorithms whose expected running time depends on the size of the number to be factored. … ►As of January 2009 the largest prime factors found by these methods are a 19-digit prime for Brent–Pollard rho, a 58-digit prime for Pollard $p-1$, and a 67-digit prime for ecm. … ►These algorithms include the Continued Fraction Algorithm (cfrac), the Multiple Polynomial Quadratic Sieve (mpqs), the General Number Field Sieve (gnfs), and the Special Number Field Sieve (snfs). …The snfs can be applied only to numbers that are very close to a power of a very small base. The largest composite numbers that have been factored by other Type II probabilistic algorithms are a 63-digit integer by cfrac, a 135-digit integer by mpqs, and a 182-digit integer by gnfs. …

17: 24.19 Methods of Computation

… ►

§24.19(i) Bernoulli and Euler Numbers and Polynomials

… ►For number-theoretic applications it is important to compute $B_{2n}(modp)$ for $2n\le p-3$; in particular to find the irregular pairs $(2n,p)$ for which $B_{2n}\equiv 0(modp)$. We list here three methods, arranged in increasing order of efficiency. ►

Tanner and Wagstaff (1987) derives a congruence $(modp)$ for Bernoulli numbers in terms of sums of powers. See also §24.10(iii).

►

Buhler et al. (1992) uses the expansion

24.19.3 $$\frac{t^2}{\cosh t-1}=-2\sum _{n=0}^{\mathrm{\infty }}(2n-1)B_{2n}\frac{t^{2n}}{(2n)!},$$

ⓘ

Symbols:

$B_n$: Bernoulli numbers, $!$: factorial (as in $n!$), $\cosh z$: hyperbolic cosine function, $n$: integer and $t$: real or complex

Referenced by:

§24.19(ii)

Permalink:

http://dlmf.nist.gov/24.19.E3

Encodings:

pMML, png, TeX

See also:

Annotations for §24.19(ii), §24.19 and Ch.24

and computes inverses modulo $p$ of the left-hand side. Multisectioning techniques are applied in implementations. See also Crandall (1996, pp. 116–120).

…

18: 22.20 Methods of Computation

… ►For $x$ real and $k\in (0,1)$, use (22.20.1) with $a_0=1$, $b_0=k^{\prime }\in (0,1)$, $c_0=k$, and continue until $c_N$ is zero to the required accuracy. … ►By application of the transformations given in §§22.7(i) and 22.7(ii), $k$ or $k^{\prime }$ can always be made sufficently small to enable the approximations given in §22.10(ii) to be applied. … ►To compute $\mathrm{dn}(x,k)$ to 6D for $x=0.2$, $k^2=0.19$, $k^{\prime }=0.9$. … ►If either $\tau$ or $q={\mathrm{e}}^{\mathrm{i}\pi \tau }$ is given, then we use $k={\theta }_2^2(0,q)/{\theta }_3^2(0,q)$, $k^{\prime }={\theta }_4^2(0,q)/{\theta }_3^2(0,q)$, $K=\frac{1}{2}\pi {\theta }_3^2(0,q)$, and $K^{\prime }=-\mathrm{i}\tau K$, obtaining the values of the theta functions as in §20.14. … ►If $k=k^{\prime }=1/\sqrt{2}$, then three iterations of (22.20.1) give $M=\mathrm{0.84721\hspace{0.33em}30848}$, and from (22.20.6) $K=\pi /(2M)=\mathrm{1.85407\hspace{0.33em}46773}$ — in agreement with the value of ${\left(\mathrm{\Gamma }\left(\frac{1}{4}\right)\right)}^2/\left(4\sqrt{\pi }\right)$; compare (23.17.3) and (23.22.2). …

19: 27.13 Functions

… ►Whereas multiplicative number theory is concerned with functions arising from prime factorization, additive number theory treats functions related to addition of integers. … ►Every even integer $n>4$ is the sum of two odd primes. In this case, $S(n)$ is the number of solutions of the equation $n=p+q$, where $p$ and $q$ are odd primes. Goldbach’s assertion is that $S(n)\ge 1$ for all even $n>4$. This conjecture dates back to 1742 and was undecided in 2009, although it has been confirmed numerically up to very large numbers. Vinogradov (1937) proves that every sufficiently large odd integer is the sum of three odd primes, and Chen (1966) shows that every sufficiently large even integer is the sum of a prime and a number with no more than two prime factors. …

20: 27.4 Euler Products and Dirichlet Series

… ►The fundamental theorem of arithmetic is linked to analysis through the concept of the Euler product. …In this case the infinite product on the right (extended over all primes $p$) is also absolutely convergent and is called the Euler product of the series. If $f(n)$ is completely multiplicative, then each factor in the product is a geometric series and the Euler product becomes … ►Euler products are used to find series that generate many functions of multiplicative number theory. … ►In (27.4.12) and (27.4.13) ${\zeta }^{\prime }\left(s\right)$ is the derivative of $\zeta \left(s\right)$.