70 ( seventy ) is the natural number following 69 and preceding 71 .
124-453: 70 is the value n {\displaystyle n} whose factorial is closest to a googol , where 70 ! ≈ 1.1978571 … × 10 100 {\displaystyle 70!\approx 1.1978571\ldots \times 10^{100}} . 70 is the fourth discrete sphenic number , as the first of the form 2 × 5 × r {\displaystyle 2\times 5\times r} . It
248-438: A n ) n = − ∞ ∞ {\textstyle {(a_{n})}_{n=-\infty }^{\infty }} is a bi-infinite sequence , and can also be written as ( … , a − 1 , a 0 , a 1 , a 2 , … ) {\textstyle (\ldots ,a_{-1},a_{0},a_{1},a_{2},\ldots )} . In cases where
372-464: A n ) . {\textstyle (a_{n}).} Here A is the domain, or index set, of the sequence. Sequences and their limits (see below) are important concepts for studying topological spaces. An important generalization of sequences is the concept of nets . A net is a function from a (possibly uncountable ) directed set to a topological space. The notational conventions for sequences normally apply to nets as well. The length of
496-717: A double exponential function . Its growth rate is similar to n n {\displaystyle n^{n}} , but slower by an exponential factor. One way of approaching this result is by taking the natural logarithm of the factorial, which turns its product formula into a sum, and then estimating the sum by an integral: ln n ! = ∑ x = 1 n ln x ≈ ∫ 1 n ln x d x = n ln n − n + 1. {\displaystyle \ln n!=\sum _{x=1}^{n}\ln x\approx \int _{1}^{n}\ln x\,dx=n\ln n-n+1.} Exponentiating
620-442: A factor with either the first or the last member. It is also the sixth Pell number , preceding the tenth prime number 29 , in the sequence { 0 , 1 , 2 , 5 , 12 , 29 , … } {\displaystyle \{0,1,2,5,12,29,\ldots \}} . 70 is a palindromic number in bases 9 (77 9 ), 13 (55 13 ) and 34 (22 34 ). 70 is the thirteenth happy number in decimal , where 7
744-412: A set , it contains members (also called elements , or terms ). The number of elements (possibly infinite ) is called the length of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers (the positions of elements in the sequence) to
868-408: A 1685 treatise by John Wallis , a study of their approximate values for large values of n {\displaystyle n} by Abraham de Moivre in 1721, a 1729 letter from James Stirling to de Moivre stating what became known as Stirling's approximation , and work at the same time by Daniel Bernoulli and Leonhard Euler formulating the continuous extension of the factorial function to
992-467: A common example in the use of different computer programming styles and methods. The computation of n ! {\displaystyle n!} can be expressed in pseudocode using iteration as or using recursion based on its recurrence relation as Other methods suitable for its computation include memoization , dynamic programming , and functional programming . The computational complexity of these algorithms may be analyzed using
1116-545: A definition for the factorial at all complex numbers other than the negative integers. One property of the gamma function, distinguishing it from other continuous interpolations of the factorials, is given by the Bohr–Mollerup theorem , which states that the gamma function (offset by one) is the only log-convex function on the positive real numbers that interpolates the factorials and obeys the same functional equation. A related uniqueness theorem of Helmut Wielandt states that
1240-663: A distance from L {\displaystyle L} less than d {\displaystyle d} . For example, the sequence a n = n + 1 2 n 2 {\textstyle a_{n}={\frac {n+1}{2n^{2}}}} shown to the right converges to the value 0. On the other hand, the sequences b n = n 3 {\textstyle b_{n}=n^{3}} (which begins 1, 8, 27, ...) and c n = ( − 1 ) n {\displaystyle c_{n}=(-1)^{n}} (which begins −1, 1, −1, 1, ...) are both divergent. If
1364-421: A factor of two to produce one of these trailing zeros. The leading digits of the factorials are distributed according to Benford's law . Every sequence of digits, in any base, is the sequence of initial digits of some factorial number in that base. Another result on divisibility of factorials, Wilson's theorem , states that ( n − 1 ) ! + 1 {\displaystyle (n-1)!+1}
SECTION 10
#17327651994381488-599: A function of n . Nevertheless, holonomic sequences play an important role in various areas of mathematics. For example, many special functions have a Taylor series whose sequence of coefficients is holonomic. The use of the recurrence relation allows a fast computation of values of such special functions. Not all sequences can be specified by a recurrence relation. An example is the sequence of prime numbers in their natural order (2, 3, 5, 7, 11, 13, 17, ...). There are many different notions of sequences in mathematics, some of which ( e.g. , exact sequence ) are not covered by
1612-697: A function of the number of digits or bits in the result. By Stirling's formula, n ! {\displaystyle n!} has b = O ( n log n ) {\displaystyle b=O(n\log n)} bits. The Schönhage–Strassen algorithm can produce a b {\displaystyle b} -bit product in time O ( b log b log log b ) {\displaystyle O(b\log b\log \log b)} , and faster multiplication algorithms taking time O ( b log b ) {\displaystyle O(b\log b)} are known. However, computing
1736-621: A half score'. (For French, this is true only in France; other French-speaking regions such as Belgium , Switzerland , Aosta Valley and Jersey use septante .) Factorial In mathematics , the factorial of a non-negative integer n {\displaystyle n} , denoted by n ! {\displaystyle n!} , is the product of all positive integers less than or equal to n {\displaystyle n} . The factorial of n {\displaystyle n} also equals
1860-416: A limit if the elements of the sequence become closer and closer to some value L {\displaystyle L} (called the limit of the sequence), and they become and remain arbitrarily close to L {\displaystyle L} , meaning that given a real number d {\displaystyle d} greater than zero, all but a finite number of the elements of the sequence have
1984-487: A modified form of the factorial, omitting the factors in the factorial that are divisible by p . The digamma function is the logarithmic derivative of the gamma function. Just as the gamma function provides a continuous interpolation of the factorials, offset by one, the digamma function provides a continuous interpolation of the harmonic numbers , offset by the Euler–Mascheroni constant . The factorial function
2108-483: A natural number N {\displaystyle N} such that for all n ≥ N {\displaystyle n\geq N} we have If ( a n ) {\displaystyle (a_{n})} is a sequence of complex numbers rather than a sequence of real numbers, this last formula can still be used to define convergence, with the provision that | ⋅ | {\displaystyle |\cdot |} denotes
2232-404: A proof of Euclid's theorem that the number of primes is infinite. When n ! ± 1 {\displaystyle n!\pm 1} is itself prime it is called a factorial prime ; relatedly, Brocard's problem , also posed by Srinivasa Ramanujan , concerns the existence of square numbers of the form n ! + 1 {\displaystyle n!+1} . In contrast,
2356-415: A recurrence relation is Recamán's sequence , defined by the recurrence relation with initial term a 0 = 0. {\displaystyle a_{0}=0.} A linear recurrence with constant coefficients is a recurrence relation of the form where c 0 , … , c k {\displaystyle c_{0},\dots ,c_{k}} are constants . There
2480-400: A sequence are discussed after the examples. The prime numbers are the natural numbers greater than 1 that have no divisors but 1 and themselves. Taking these in their natural order gives the sequence (2, 3, 5, 7, 11, 13, 17, ...). The prime numbers are widely used in mathematics , particularly in number theory where many results related to them exist. The Fibonacci numbers comprise
2604-440: A sequence converges, then the value it converges to is unique. This value is called the limit of the sequence. The limit of a convergent sequence ( a n ) {\displaystyle (a_{n})} is normally denoted lim n → ∞ a n {\textstyle \lim _{n\to \infty }a_{n}} . If ( a n ) {\displaystyle (a_{n})}
SECTION 20
#17327651994382728-404: A sequence is defined as the number of terms in the sequence. A sequence of a finite length n is also called an n -tuple . Finite sequences include the empty sequence ( ) that has no elements. Normally, the term infinite sequence refers to a sequence that is infinite in one direction, and finite in the other—the sequence has a first element, but no final element. Such a sequence
2852-463: A sequence is to list all its elements. For example, the first four odd numbers form the sequence (1, 3, 5, 7). This notation is used for infinite sequences as well. For instance, the infinite sequence of positive odd integers is written as (1, 3, 5, 7, ...). Because notating sequences with ellipsis leads to ambiguity, listing is most useful for customary infinite sequences which can be easily recognized from their first few elements. Other ways of denoting
2976-409: A sequence of integers whose pattern can be easily inferred. In these cases, the index set may be implied by a listing of the first few abstract elements. For instance, the sequence of squares of odd numbers could be denoted in any of the following ways. Moreover, the subscripts and superscripts could have been left off in the third, fourth, and fifth notations, if the indexing set was understood to be
3100-450: A sequence of sequences: ( ( a m , n ) n ∈ N ) m ∈ N {\textstyle ((a_{m,n})_{n\in \mathbb {N} })_{m\in \mathbb {N} }} denotes a sequence whose m th term is the sequence ( a m , n ) n ∈ N {\textstyle (a_{m,n})_{n\in \mathbb {N} }} . An alternative to writing
3224-422: A sequence. Factorials appear more broadly in many formulas in combinatorics , to account for different orderings of objects. For instance the binomial coefficients ( n k ) {\displaystyle {\tbinom {n}{k}}} count the k {\displaystyle k} -element combinations (subsets of k {\displaystyle k} elements) from
3348-399: A set with n {\displaystyle n} elements, and can be computed from factorials using the formula ( n k ) = n ! k ! ( n − k ) ! . {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.} The Stirling numbers of the first kind sum to the factorials, and count
3472-418: A subset of exceptions with asymptotic density zero), it coincides with the largest prime factor of x {\displaystyle x} . The product of two factorials, m ! ⋅ n ! {\displaystyle m!\cdot n!} , always evenly divides ( m + n ) ! {\displaystyle (m+n)!} . There are infinitely many factorials that equal
3596-419: Is 1 {\displaystyle 1} , or in symbols, 0 ! = 1 {\displaystyle 0!=1} . There are several motivations for this definition: The earliest uses of the factorial function involve counting permutations : there are n ! {\displaystyle n!} different ways of arranging n {\displaystyle n} distinct objects into
3720-565: Is monotonically decreasing if each consecutive term is less than or equal to the previous one, and is strictly monotonically decreasing if each is strictly less than the previous. If a sequence is either increasing or decreasing it is called a monotone sequence. This is a special case of the more general notion of a monotonic function . The terms nondecreasing and nonincreasing are often used in place of increasing and decreasing in order to avoid any possible confusion with strictly increasing and strictly decreasing , respectively. If
3844-534: Is 1, according to the convention for an empty product . Factorials have been discovered in several ancient cultures, notably in Indian mathematics in the canonical works of Jain literature , and by Jewish mystics in the Talmudic book Sefer Yetzirah . The factorial operation is encountered in many areas of mathematics, notably in combinatorics , where its most basic use counts the possible distinct sequences –
70 (number) - Misplaced Pages Continue
3968-574: Is a common feature in scientific calculators . It is also included in scientific programming libraries such as the Python mathematical functions module and the Boost C++ library . If efficiency is not a concern, computing factorials is trivial: just successively multiply a variable initialized to 1 {\displaystyle 1} by the integers up to n {\displaystyle n} . The simplicity of this computation makes it
4092-474: Is a divergent sequence, then the expression lim n → ∞ a n {\textstyle \lim _{n\to \infty }a_{n}} is meaningless. A sequence of real numbers ( a n ) {\displaystyle (a_{n})} converges to a real number L {\displaystyle L} if, for all ε > 0 {\displaystyle \varepsilon >0} , there exists
4216-468: Is a general method for expressing the general term a n {\displaystyle a_{n}} of such a sequence as a function of n ; see Linear recurrence . In the case of the Fibonacci sequence, one has c 0 = 0 , c 1 = c 2 = 1 , {\displaystyle c_{0}=0,c_{1}=c_{2}=1,} and the resulting function of n
4340-411: Is a simple classical example, defined by the recurrence relation with initial terms a 0 = 0 {\displaystyle a_{0}=0} and a 1 = 1 {\displaystyle a_{1}=1} . From this, a simple computation shows that the first ten terms of this sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34. A complicated example of a sequence defined by
4464-550: Is a single multiplication of a number with O ( n log n ) {\displaystyle O(n\log n)} bits. Again, at each level of recursion the numbers involved have a constant fraction as many bits (because otherwise repeatedly squaring them would produce too large a final result) so again the amounts of time for these steps in the recursive calls add in a geometric series to O ( n log 2 n ) {\displaystyle O(n\log ^{2}n)} . Consequentially,
4588-401: Is a strictly increasing sequence of positive integers. Some other types of sequences that are easy to define include: An important property of a sequence is convergence . If a sequence converges, it converges to a particular value known as the limit . If a sequence converges to some limit, then it is convergent . A sequence that does not converge is divergent . Informally, a sequence has
4712-509: Is also the fifth pentatope number , as the number of 3-dimensional unit spheres which can be packed into a 4-simplex (or four-dimensional analogue of the regular tetrahedron ) of edge-length 5. The sum of the first 24 squares starting from 1 is 70 = 4900, i.e. a square pyramidal number . This is the only non trivial solution to the cannonball problem , and relates 70 to the Leech lattice in twenty-four dimensions and thus string theory . 70
4836-464: Is bi-infinite. This sequence could be denoted ( 2 n ) n = − ∞ ∞ {\textstyle {(2n)}_{n=-\infty }^{\infty }} . A sequence is said to be monotonically increasing if each term is greater than or equal to the one before it. For example, the sequence ( a n ) n = 1 ∞ {\textstyle {(a_{n})}_{n=1}^{\infty }}
4960-409: Is called a lower bound . If a sequence is both bounded from above and bounded from below, then the sequence is said to be bounded . A subsequence of a given sequence is a sequence formed from the given sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. For instance, the sequence of positive even integers (2, 4, 6, ...) is a subsequence of
5084-465: Is called a singly infinite sequence or a one-sided infinite sequence when disambiguation is necessary. In contrast, a sequence that is infinite in both directions—i.e. that has neither a first nor a final element—is called a bi-infinite sequence , two-way infinite sequence , or doubly infinite sequence . A function from the set Z of all integers into a set, such as for instance the sequence of all even integers ( ..., −4, −2, 0, 2, 4, 6, 8, ... ),
70 (number) - Misplaced Pages Continue
5208-418: Is called an index , and the set of values that it can take is called the index set . It is often useful to combine this notation with the technique of treating the elements of a sequence as individual variables. This yields expressions like ( a n ) n ∈ N {\textstyle (a_{n})_{n\in \mathbb {N} }} , which denotes a sequence whose n th element
5332-663: Is changed to keep all but the last term, it would define a product of the same form, for a smaller factorial. This leads to a recurrence relation , according to which each value of the factorial function can be obtained by multiplying the previous value by n {\displaystyle n} : n ! = n ⋅ ( n − 1 ) ! . {\displaystyle n!=n\cdot (n-1)!.} For example, 5 ! = 5 ⋅ 4 ! = 5 ⋅ 24 = 120 {\displaystyle 5!=5\cdot 4!=5\cdot 24=120} . The factorial of 0 {\displaystyle 0}
5456-563: Is divisible by n {\displaystyle n} if and only if n {\displaystyle n} is a prime number . For any given integer x {\displaystyle x} , the Kempner function of x {\displaystyle x} is given by the smallest n {\displaystyle n} for which x {\displaystyle x} divides n ! {\displaystyle n!} . For almost all numbers (all but
5580-416: Is easily discernible by inspection. Other examples are sequences of functions , whose elements are functions instead of numbers. The On-Line Encyclopedia of Integer Sequences comprises a large list of examples of integer sequences. Other notations can be useful for sequences whose pattern cannot be easily guessed or for sequences that do not have a pattern such as the digits of π . One such notation
5704-406: Is given by Binet's formula . A holonomic sequence is a sequence defined by a recurrence relation of the form where c 1 , … , c k {\displaystyle c_{1},\dots ,c_{k}} are polynomials in n . For most holonomic sequences, there is no explicit formula for expressing a n {\displaystyle a_{n}} as
5828-503: Is given by the variable a n {\displaystyle a_{n}} . For example: One can consider multiple sequences at the same time by using different variables; e.g. ( b n ) n ∈ N {\textstyle (b_{n})_{n\in \mathbb {N} }} could be a different sequence than ( a n ) n ∈ N {\textstyle (a_{n})_{n\in \mathbb {N} }} . One can even consider
5952-431: Is in contrast to the definition of sequences of elements as functions of their positions. To define a sequence by recursion, one needs a rule, called recurrence relation to construct each element in terms of the ones before it. In addition, enough initial elements must be provided so that all subsequent elements of the sequence can be computed by successive applications of the recurrence relation. The Fibonacci sequence
6076-404: Is monotonically increasing if and only if a n + 1 ≥ a n {\textstyle a_{n+1}\geq a_{n}} for all n ∈ N . {\displaystyle n\in \mathbf {N} .} If each consecutive term is strictly greater than (>) the previous term then the sequence is called strictly monotonically increasing . A sequence
6200-440: Is positive. It can be extended to the non-integer points in the rest of the complex plane by solving for Euler's reflection formula Γ ( z ) Γ ( 1 − z ) = π sin π z . {\displaystyle \Gamma (z)\Gamma (1-z)={\frac {\pi }{\sin \pi z}}.} However, this formula cannot be used at integers because, for them,
6324-500: Is replaced by the expression dist ( a n , L ) {\displaystyle \operatorname {dist} (a_{n},L)} , which denotes the distance between a n {\displaystyle a_{n}} and L {\displaystyle L} . If ( a n ) {\displaystyle (a_{n})} and ( b n ) {\displaystyle (b_{n})} are convergent sequences, then
SECTION 50
#17327651994386448-454: Is the atomic number of ytterbium , a lanthanide . In certain cases, copyrights expire after 70 (or 50) years, especially after the death of the latest author (see, Berne Convention ). Several languages, especially ones with vigesimal number systems, do not have a specific word for 70: for example, French : soixante-dix , lit. 'sixty-ten'; Danish : halvfjerds , short for halvfjerdsindstyve , 'three and
6572-439: Is the first such number greater than 1 in base ten: the sum of squares of its digits eventually reduces to 1 . For both 7 and 70, there is 97 , which reduces from the sum of squares of digits of 49, is the only prime after 7 in the successive sums of squares of digits (7, 49, 97 , 130, 10) before reducing to 1. More specifically, 97 is also the seventh happy prime in base ten. 70 = 2 × 5 × 7 simplifies to 7 × 10 , or
6696-461: Is the smallest weird number , a natural number that is abundant but not semiperfect , where it is also the second-smallest primitive abundant number , after 20 . 70 is in equivalence with the sum between the smallest number that is the sum of two abundant numbers, and the largest that is not ( 24 , 46 ). 70 is the tenth Erdős–Woods number , since it is possible to find sequences of seventy consecutive integers such that each inner member shares
6820-536: Is to perform the multiplications as a divide-and-conquer algorithm that multiplies a sequence of i {\displaystyle i} numbers by splitting it into two subsequences of i / 2 {\displaystyle i/2} numbers, multiplies each subsequence, and combines the results with one last multiplication. This approach to the factorial takes total time O ( n log 3 n ) {\displaystyle O(n\log ^{3}n)} : one logarithm comes from
6944-568: Is to write down a general formula for computing the n th term as a function of n , enclose it in parentheses, and include a subscript indicating the set of values that n can take. For example, in this notation the sequence of even numbers could be written as ( 2 n ) n ∈ N {\textstyle (2n)_{n\in \mathbb {N} }} . The sequence of squares could be written as ( n 2 ) n ∈ N {\textstyle (n^{2})_{n\in \mathbb {N} }} . The variable n
7068-967: The ∼ {\displaystyle \sim } symbol means that, as n {\displaystyle n} goes to infinity, the ratio between the left and right sides approaches one in the limit . Stirling's formula provides the first term in an asymptotic series that becomes even more accurate when taken to greater numbers of terms: n ! ∼ 2 π n ( n e ) n ( 1 + 1 12 n + 1 288 n 2 − 139 51840 n 3 − 571 2488320 n 4 + ⋯ ) . {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}-{\frac {139}{51840n^{3}}}-{\frac {571}{2488320n^{4}}}+\cdots \right).} An alternative version uses only odd exponents in
7192-416: The sin π z {\displaystyle \sin \pi z} term would produce a division by zero . The result of this extension process is an analytic function , the analytic continuation of the integral formula for the gamma function. It has a nonzero value at all complex numbers, except for the non-positive integers where it has simple poles . Correspondingly, this provides
7316-419: The abc conjecture that there are only finitely many nontrivial examples. The greatest common divisor of the values of a primitive polynomial of degree d {\displaystyle d} over the integers evenly divides d ! {\displaystyle d!} . There are infinitely many ways to extend the factorials to a continuous function . The most widely used of these uses
7440-532: The Sackur–Tetrode equation must correct the count of microstates by dividing by the factorials of the numbers of each type of indistinguishable particle to avoid the Gibbs paradox . Quantum physics provides the underlying reason for why these corrections are necessary. As a function of n {\displaystyle n} , the factorial has faster than exponential growth , but grows more slowly than
7564-471: The Wallis product , which expresses π {\displaystyle \pi } as a limiting ratio of factorials and powers of two. The result of these corrections is Stirling's approximation : n ! ∼ 2 π n ( n e ) n . {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.} Here,
SECTION 60
#17327651994387688-441: The codomain of the sequence is fixed by context, for example by requiring it to be the set R of real numbers, the set C of complex numbers, or a topological space . Although sequences are a type of function, they are usually distinguished notationally from functions in that the input is written as a subscript rather than in parentheses, that is, a n rather than a ( n ) . There are terminological differences as well:
7812-427: The convergence properties of sequences. In particular, sequences are the basis for series , which are important in differential equations and analysis . Sequences are also of interest in their own right, and can be studied as patterns or puzzles, such as in the study of prime numbers . There are a number of ways to denote a sequence, some of which are more useful for specific types of sequences. One way to specify
7936-465: The exponential generating function , which for a combinatorial class with n i {\displaystyle n_{i}} elements of size i {\displaystyle i} is defined as the power series ∑ i = 0 ∞ x i n i i ! . {\displaystyle \sum _{i=0}^{\infty }{\frac {x^{i}n_{i}}{i!}}.} In number theory ,
8060-459: The gamma function , which can be defined for positive real numbers as the integral Γ ( z ) = ∫ 0 ∞ x z − 1 e − x d x . {\displaystyle \Gamma (z)=\int _{0}^{\infty }x^{z-1}e^{-x}\,dx.} The resulting function is related to the factorial of a non-negative integer n {\displaystyle n} by
8184-583: The gamma function . Adrien-Marie Legendre included Legendre's formula , describing the exponents in the factorization of factorials into prime powers , in an 1808 text on number theory . The notation n ! {\displaystyle n!} for factorials was introduced by the French mathematician Christian Kramp in 1808. Many other notations have also been used. Another later notation | n _ {\displaystyle \vert \!{\underline {\,n}}} , in which
8308-411: The limit of a sequence of rational numbers (e.g. via its decimal expansion , also see completeness of the real numbers ). As another example, π is the limit of the sequence (3, 3.1, 3.14, 3.141, 3.1415, ...), which is increasing. A related sequence is the sequence of decimal digits of π , that is, (3, 1, 4, 1, 5, 9, ...). Unlike the preceding sequence, this sequence does not have any pattern that
8432-420: The natural numbers . In the second and third bullets, there is a well-defined sequence ( a k ) k = 1 ∞ {\textstyle {(a_{k})}_{k=1}^{\infty }} , but it is not the same as the sequence denoted by the expression. Sequences whose elements are related to the previous elements in a straightforward way are often defined using recursion . This
8556-408: The permutations – of n {\displaystyle n} distinct objects: there are n ! {\displaystyle n!} . In mathematical analysis , factorials are used in power series for the exponential function and other functions, and they also have applications in algebra , number theory , probability theory , and computer science . Much of the mathematics of
8680-406: The prime number theorem , so the time for the first step is O ( n log 2 n ) {\displaystyle O(n\log ^{2}n)} , with one logarithm coming from the divide and conquer and another coming from the multiplication algorithm. In the recursive calls to the algorithm, the prime number theorem can again be invoked to prove that the numbers of bits in
8804-453: The 7-simplex, there are a total of seventy other uniform 7-polytopes with A 7 {\displaystyle \mathrm {A_{7}} } symmetry . The 7-simplex can be constructed as the join of a point and a 6-simplex , whose order is 7!, where the 6-simplex has a total of seventy three-dimensional and two-dimensional elements (there are thirty-five 3-simplex cells, and thirty-five faces that are triangular ). 70
8928-418: The analysis of brute-force searches over permutations, factorials arise in the lower bound of log 2 n ! = n log 2 n − O ( n ) {\displaystyle \log _{2}n!=n\log _{2}n-O(n)} on the number of comparisons needed to comparison sort a set of n {\displaystyle n} items, and in
9052-403: The analysis of chained hash tables , where the distribution of keys per cell can be accurately approximated by a Poisson distribution. Moreover, factorials naturally appear in formulae from quantum and statistical physics , where one often considers all the possible permutations of a set of particles. In statistical mechanics , calculations of entropy such as Boltzmann's entropy formula or
9176-547: The argument of the factorial was half-enclosed by the left and bottom sides of a box, was popular for some time in Britain and America but fell out of use, perhaps because it is difficult to typeset. The word "factorial" (originally French: factorielle ) was first used in 1800 by Louis François Antoine Arbogast , in the first work on Faà di Bruno's formula , but referring to a more general concept of products of arithmetic progressions . The "factors" that this name refers to are
9300-432: The coefficients of other Taylor series (in particular those of the trigonometric and hyperbolic functions ), where they cancel factors of n ! {\displaystyle n!} coming from the n {\displaystyle n} th derivative of x n {\displaystyle x^{n}} . This usage of factorials in power series connects back to analytic combinatorics through
9424-400: The complex gamma function and its scalar multiples are the only holomorphic functions on the positive complex half-plane that obey the functional equation and remain bounded for complex numbers with real part between 1 and 2. Other complex functions that interpolate the factorial values include Hadamard's gamma function , which is an entire function over all the complex numbers, including
9548-441: The complex modulus, i.e. | z | = z ∗ z {\displaystyle |z|={\sqrt {z^{*}z}}} . If ( a n ) {\displaystyle (a_{n})} is a sequence of points in a metric space , then the formula can be used to define convergence, if the expression | a n − L | {\displaystyle |a_{n}-L|}
9672-721: The correction terms: n ! ∼ 2 π n ( n e ) n exp ( 1 12 n − 1 360 n 3 + 1 1260 n 5 − 1 1680 n 7 + ⋯ ) . {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({\frac {1}{12n}}-{\frac {1}{360n^{3}}}+{\frac {1}{1260n^{5}}}-{\frac {1}{1680n^{7}}}+\cdots \right).} Many other variations of these formulas have also been developed, by Srinivasa Ramanujan , Bill Gosper , and others. The binary logarithm of
9796-515: The corresponding products decrease by a constant factor at each level of recursion, so the total time for these steps at all levels of recursion adds in a geometric series to O ( n log 2 n ) {\displaystyle O(n\log ^{2}n)} . The time for the squaring in the second step and the multiplication in the third step are again O ( n log 2 n ) {\displaystyle O(n\log ^{2}n)} , because each
9920-432: The definitions and notations introduced below. In this article, a sequence is formally defined as a function whose domain is an interval of integers . This definition covers several different uses of the word "sequence", including one-sided infinite sequences, bi-infinite sequences, and finite sequences (see below for definitions of these kinds of sequences). However, many authors use a narrower definition by requiring
10044-496: The denominators of power series , most notably in the series for the exponential function , e x = 1 + x 1 + x 2 2 + x 3 6 + ⋯ = ∑ i = 0 ∞ x i i ! , {\displaystyle e^{x}=1+{\frac {x}{1}}+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}+\cdots =\sum _{i=0}^{\infty }{\frac {x^{i}}{i!}},} and in
10168-697: The domain of a sequence in the subscript is to indicate the range of values that the index can take by listing its highest and lowest legal values. For example, the notation ( k 2 ) ) k = 1 10 {\textstyle (k^{2}){\vphantom {)}}_{k=1}^{10}} denotes the ten-term sequence of squares ( 1 , 4 , 9 , … , 100 ) {\displaystyle (1,4,9,\ldots ,100)} . The limits ∞ {\displaystyle \infty } and − ∞ {\displaystyle -\infty } are allowed, but they do not represent valid values for
10292-433: The domain of a sequence to be the set of natural numbers . This narrower definition has the disadvantage that it rules out finite sequences and bi-infinite sequences, both of which are usually called sequences in standard mathematical practice. Another disadvantage is that, if one removes the first terms of a sequence, one needs reindexing the remainder terms for fitting this definition. In some contexts, to shorten exposition,
10416-477: The elements at each position. The notion of a sequence can be generalized to an indexed family , defined as a function from an arbitrary index set. For example, (M, A, R, Y) is a sequence of letters with the letter "M" first and "Y" last. This sequence differs from (A, R, M, Y). Also, the sequence (1, 1, 2, 3, 5, 8), which contains the number 1 at two different positions, is a valid sequence. Sequences can be finite , as in these examples, or infinite , such as
10540-471: The equation n ! = Γ ( n + 1 ) , {\displaystyle n!=\Gamma (n+1),} which can be used as a definition of the factorial for non-integer arguments. At all values x {\displaystyle x} for which both Γ ( x ) {\displaystyle \Gamma (x)} and Γ ( x − 1 ) {\displaystyle \Gamma (x-1)} are defined,
10664-420: The factorial function are commonly used as an example of different computer programming styles, and are included in scientific calculators and scientific computing software libraries. Although directly computing large factorials using the product formula or recurrence is not efficient, faster algorithms are known, matching to within a constant factor the time for fast multiplication algorithms for numbers with
10788-407: The factorial function was developed beginning in the late 18th and early 19th centuries. Stirling's approximation provides an accurate approximation to the factorial of large numbers, showing that it grows more quickly than exponential growth . Legendre's formula describes the exponents of the prime numbers in a prime factorization of the factorials, and can be used to count the trailing zeros of
10912-907: The factorial implies that n ! {\displaystyle n!} is divisible by all prime numbers that are at most n {\displaystyle n} , and by no larger prime numbers. More precise information about its divisibility is given by Legendre's formula , which gives the exponent of each prime p {\displaystyle p} in the prime factorization of n ! {\displaystyle n!} as ∑ i = 1 ∞ ⌊ n p i ⌋ = n − s p ( n ) p − 1 . {\displaystyle \sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ={\frac {n-s_{p}(n)}{p-1}}.} Here s p ( n ) {\displaystyle s_{p}(n)} denotes
11036-722: The factorial involves repeated products, rather than a single multiplication, so these time bounds do not apply directly. In this setting, computing n ! {\displaystyle n!} by multiplying the numbers from 1 to n {\displaystyle n} in sequence is inefficient, because it involves n {\displaystyle n} multiplications, a constant fraction of which take time O ( n log 2 n ) {\displaystyle O(n\log ^{2}n)} each, giving total time O ( n 2 log 2 n ) {\displaystyle O(n^{2}\log ^{2}n)} . A better approach
11160-620: The factorial, used to analyze comparison sorting , can be very accurately estimated using Stirling's approximation. In the formula below, the O ( 1 ) {\displaystyle O(1)} term invokes big O notation . log 2 n ! = n log 2 n − ( log 2 e ) n + 1 2 log 2 n + O ( 1 ) . {\displaystyle \log _{2}n!=n\log _{2}n-(\log _{2}e)n+{\frac {1}{2}}\log _{2}n+O(1).} The product formula for
11284-665: The factorials arise through the binomial theorem , which uses binomial coefficients to expand powers of sums. They also occur in the coefficients used to relate certain families of polynomials to each other, for instance in Newton's identities for symmetric polynomials . Their use in counting permutations can also be restated algebraically: the factorials are the orders of finite symmetric groups . In calculus , factorials occur in Faà di Bruno's formula for chaining higher derivatives. In mathematical analysis , factorials frequently appear in
11408-431: The factorials. Daniel Bernoulli and Leonhard Euler interpolated the factorial function to a continuous function of complex numbers , except at the negative integers, the (offset) gamma function . Many other notable functions and number sequences are closely related to the factorials, including the binomial coefficients , double factorials , falling factorials , primorials , and subfactorials . Implementations of
11532-401: The factorization of a binomial coefficient. Grouping the prime factors of the factorial into prime powers in different ways produces the multiplicative partitions of factorials . The special case of Legendre's formula for p = 5 {\displaystyle p=5} gives the number of trailing zeros in the decimal representation of the factorials. According to this formula,
11656-471: The first results of Paul Erdős , was based on the divisibility properties of factorials. The factorial number system is a mixed radix notation for numbers in which the place values of each digit are factorials. Factorials are used extensively in probability theory , for instance in the Poisson distribution and in the probabilities of random permutations . In computer science , beyond appearing in
11780-427: The gamma function obeys the functional equation Γ ( n ) = ( n − 1 ) Γ ( n − 1 ) , {\displaystyle \Gamma (n)=(n-1)\Gamma (n-1),} generalizing the recurrence relation for the factorials. The same integral converges more generally for any complex number z {\displaystyle z} whose real part
11904-474: The index, only the supremum or infimum of such values, respectively. For example, the sequence ( a n ) n = 1 ∞ {\textstyle {(a_{n})}_{n=1}^{\infty }} is the same as the sequence ( a n ) n ∈ N {\textstyle (a_{n})_{n\in \mathbb {N} }} , and does not contain an additional term "at infinity". The sequence (
12028-434: The integer sequence whose elements are the sum of the previous two elements. The first two elements are either 0 and 1 or 1 and 1 so that the sequence is (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...). Other examples of sequences include those made up of rational numbers , real numbers and complex numbers . The sequence (.9, .99, .999, .9999, ...), for instance, approaches the number 1. In fact, every real number can be written as
12152-449: The most salient property of factorials is the divisibility of n ! {\displaystyle n!} by all positive integers up to n {\displaystyle n} , described more precisely for prime factors by Legendre's formula . It follows that arbitrarily large prime numbers can be found as the prime factors of the numbers n ! ± 1 {\displaystyle n!\pm 1} , leading to
12276-423: The non-positive integers. In the p -adic numbers , it is not possible to continuously interpolate the factorial function directly, because the factorials of large integers (a dense subset of the p -adics) converge to zero according to Legendre's formula, forcing any continuous function that is close to their values to be zero everywhere. Instead, the p -adic gamma function provides a continuous interpolation of
12400-407: The number of bits in the factorial, a second comes from the multiplication algorithm, and a third comes from the divide and conquer. Even better efficiency is obtained by computing n ! from its prime factorization, based on the principle that exponentiation by squaring is faster than expanding an exponent into a product. An algorithm for this by Arnold Schönhage begins by finding the list of
12524-1349: The number of ways to choose 4 objects out of 8 if order does not matter; this is in equivalence with the number of possible values of an 8-bit binary number for which half the bits are on, and half are off. In seven dimensions, the number of tetrahedral cells in a 7-simplex is 70. This makes 70 the central element in a seven by seven matrix configuration of a 7-simplex in seven-dimensional space: [ 8 7 21 35 35 21 7 2 28 6 15 20 15 6 3 3 56 5 10 10 5 4 6 4 70 4 6 4 5 10 10 5 56 3 3 6 15 20 15 6 28 2 7 21 35 35 21 7 8 ] {\displaystyle {\begin{bmatrix}{\begin{matrix}8&7&21&35&35&21&7\\2&28&6&15&20&15&6\\3&3&56&5&10&10&5\\4&6&4&70&4&6&4\\5&10&10&5&56&3&3\\6&15&20&15&6&28&2\\7&21&35&35&21&7&8\end{matrix}}\end{bmatrix}}} Aside from
12648-460: The number of zeros can be obtained by subtracting the base-5 digits of n {\displaystyle n} from n {\displaystyle n} , and dividing the result by four. Legendre's formula implies that the exponent of the prime p = 2 {\displaystyle p=2} is always larger than the exponent for p = 5 {\displaystyle p=5} , so each factor of five can be paired with
12772-423: The numbers n ! + 2 , n ! + 3 , … n ! + n {\displaystyle n!+2,n!+3,\dots n!+n} must all be composite, proving the existence of arbitrarily large prime gaps . An elementary proof of Bertrand's postulate on the existence of a prime in any interval of the form [ n , 2 n ] {\displaystyle [n,2n]} , one of
12896-454: The permutations of n {\displaystyle n} grouped into subsets with the same numbers of cycles. Another combinatorial application is in counting derangements , permutations that do not leave any element in its original position; the number of derangements of n {\displaystyle n} items is the nearest integer to n ! / e {\displaystyle n!/e} . In algebra ,
13020-628: The positive integers (1, 2, 3, ...). The positions of some elements change when other elements are deleted. However, the relative positions are preserved. Formally, a subsequence of the sequence ( a n ) n ∈ N {\displaystyle (a_{n})_{n\in \mathbb {N} }} is any sequence of the form ( a n k ) k ∈ N {\textstyle (a_{n_{k}})_{k\in \mathbb {N} }} , where ( n k ) k ∈ N {\displaystyle (n_{k})_{k\in \mathbb {N} }}
13144-458: The primes up to n {\displaystyle n} , for instance using the sieve of Eratosthenes , and uses Legendre's formula to compute the exponent for each prime. Then it computes the product of the prime powers with these exponents, using a recursive algorithm, as follows: The product of all primes up to n {\displaystyle n} is an O ( n ) {\displaystyle O(n)} -bit number, by
13268-864: The product of n {\displaystyle n} with the next smaller factorial: n ! = n × ( n − 1 ) × ( n − 2 ) × ( n − 3 ) × ⋯ × 3 × 2 × 1 = n × ( n − 1 ) ! {\displaystyle {\begin{aligned}n!&=n\times (n-1)\times (n-2)\times (n-3)\times \cdots \times 3\times 2\times 1\\&=n\times (n-1)!\\\end{aligned}}} For example, 5 ! = 5 × 4 ! = 5 × 4 × 3 × 2 × 1 = 120. {\displaystyle 5!=5\times 4!=5\times 4\times 3\times 2\times 1=120.} The value of 0!
13392-949: The product of other factorials: if n {\displaystyle n} is itself any product of factorials, then n ! {\displaystyle n!} equals that same product multiplied by one more factorial, ( n − 1 ) ! {\displaystyle (n-1)!} . The only known examples of factorials that are products of other factorials but are not of this "trivial" form are 9 ! = 7 ! ⋅ 3 ! ⋅ 3 ! ⋅ 2 ! {\displaystyle 9!=7!\cdot 3!\cdot 3!\cdot 2!} , 10 ! = 7 ! ⋅ 6 ! = 7 ! ⋅ 5 ! ⋅ 3 ! {\displaystyle 10!=7!\cdot 6!=7!\cdot 5!\cdot 3!} , and 16 ! = 14 ! ⋅ 5 ! ⋅ 2 ! {\displaystyle 16!=14!\cdot 5!\cdot 2!} . It would follow from
13516-425: The product of the first happy prime in decimal, and the base (10). 70 contains an aliquot sum of 74 , in an aliquot sequence of four composite numbers (70, 74, 40 , 50 , 43 ) in the prime 43 -aliquot tree. The sum 43 + 50 + 40 = 133 represents the one-hundredth composite number, where the sum of all members in this aliquot sequence up to 70 is the fifty-ninth prime, 277 (this prime index value represents
13640-782: The recursive version takes linear space to store its call stack . However, this model of computation is only suitable when n {\displaystyle n} is small enough to allow n ! {\displaystyle n!} to fit into a machine word . The values 12! and 20! are the largest factorials that can be stored in, respectively, the 32-bit and 64-bit integers . Floating point can represent larger factorials, but approximately rather than exactly, and will still overflow for factorials larger than 170 ! {\displaystyle 170!} . The exact computation of larger factorials involves arbitrary-precision arithmetic , because of fast growth and integer overflow . Time of computation can be analyzed as
13764-560: The result (and ignoring the negligible + 1 {\displaystyle +1} term) approximates n ! {\displaystyle n!} as ( n / e ) n {\displaystyle (n/e)^{n}} . More carefully bounding the sum both above and below by an integral, using the trapezoid rule , shows that this estimate needs a correction factor proportional to n {\displaystyle {\sqrt {n}}} . The constant of proportionality for this correction can be found from
13888-417: The same number of digits. The concept of factorials has arisen independently in many cultures: From the late 15th century onward, factorials became the subject of study by Western mathematicians. In a 1494 treatise, Italian mathematician Luca Pacioli calculated factorials up to 11!, in connection with a problem of dining table arrangements. Christopher Clavius discussed factorials in a 1603 commentary on
14012-562: The sequence of all even positive integers (2, 4, 6, ...). The position of an element in a sequence is its rank or index ; it is the natural number for which the element is the image. The first element has index 0 or 1, depending on the context or a specific convention. In mathematical analysis , a sequence is often denoted by letters in the form of a n {\displaystyle a_{n}} , b n {\displaystyle b_{n}} and c n {\displaystyle c_{n}} , where
14136-426: The sequence of real numbers ( a n ) is such that all the terms are less than some real number M , then the sequence is said to be bounded from above . In other words, this means that there exists M such that for all n , a n ≤ M . Any such M is called an upper bound . Likewise, if, for some real m , a n ≥ m for all n greater than some N , then the sequence is bounded from below and any such m
14260-460: The set of indexing numbers is understood, the subscripts and superscripts are often left off. That is, one simply writes ( a k ) {\textstyle (a_{k})} for an arbitrary sequence. Often, the index k is understood to run from 1 to ∞. However, sequences are frequently indexed starting from zero, as in In some cases, the elements of the sequence are related naturally to
14384-525: The seventeenth prime number and seventh super-prime, 59 ). The sum of the first seven prime numbers aside from 7 (i.e., 2, 3, 5, 11, …, 19) is 70; the first four primes in this sequence sum to 21 = 3 × 7, where the sum of the sixth, seventh and eighth indexed primes (in the sequence of prime numbers ) 13 + 17 + 19 is the seventh square number , 49 . 70 is the fourth central binomial coefficient , preceding { 1 , 2 , 6 , 20 } {\displaystyle \{1,2,6,20\}} , as
14508-482: The subscript n refers to the n th element of the sequence; for example, the n th element of the Fibonacci sequence F {\displaystyle F} is generally denoted as F n {\displaystyle F_{n}} . In computing and computer science , finite sequences are usually called strings , words or lists , with the specific technical term chosen depending on
14632-420: The sum of the base - p {\displaystyle p} digits of n {\displaystyle n} , and the exponent given by this formula can also be interpreted in advanced mathematics as the p -adic valuation of the factorial. Applying Legendre's formula to the product formula for binomial coefficients produces Kummer's theorem , a similar result on the exponent of each prime in
14756-736: The terms of the product formula for the factorial. The factorial function of a positive integer n {\displaystyle n} is defined by the product of all positive integers not greater than n {\displaystyle n} n ! = 1 ⋅ 2 ⋅ 3 ⋯ ( n − 2 ) ⋅ ( n − 1 ) ⋅ n . {\displaystyle n!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1)\cdot n.} This may be written more concisely in product notation as n ! = ∏ i = 1 n i . {\displaystyle n!=\prod _{i=1}^{n}i.} If this product formula
14880-494: The type of object the sequence enumerates and the different ways to represent the sequence in computer memory . Infinite sequences are called streams . The empty sequence ( ) is included in most notions of sequence. It may be excluded depending on the context. A sequence can be thought of as a list of elements with a particular order. Sequences are useful in a number of mathematical disciplines for studying functions , spaces , and other mathematical structures using
15004-480: The unit-cost random-access machine model of computation, in which each arithmetic operation takes constant time and each number uses a constant amount of storage space. In this model, these methods can compute n ! {\displaystyle n!} in time O ( n ) {\displaystyle O(n)} , and the iterative version uses space O ( 1 ) {\displaystyle O(1)} . Unless optimized for tail recursion ,
15128-546: The value of a sequence at the lowest input (often 1) is called the "first element" of the sequence, the value at the second smallest input (often 2) is called the "second element", etc. Also, while a function abstracted from its input is usually denoted by a single letter, e.g. f , a sequence abstracted from its input is usually written by a notation such as ( a n ) n ∈ A {\textstyle (a_{n})_{n\in A}} , or just as (
15252-460: The whole algorithm takes time O ( n log 2 n ) {\displaystyle O(n\log ^{2}n)} , proportional to a single multiplication with the same number of bits in its result. Several other integer sequences are similar to or related to the factorials: Sequence In mathematics , a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like
15376-547: The work of Johannes de Sacrobosco , and in the 1640s, French polymath Marin Mersenne published large (but not entirely correct) tables of factorials, up to 64!, based on the work of Clavius. The power series for the exponential function , with the reciprocals of factorials for its coefficients, was first formulated in 1676 by Isaac Newton in a letter to Gottfried Wilhelm Leibniz . Other important works of early European mathematics on factorials include extensive coverage in
#437562