Related Research Articles
In mathematics, the factorial of a non-negative integer , denoted by , is the product of all positive integers less than or equal to . The factorial of also equals the product of with the next smaller factorial:
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
In mathematics, a polynomial is an expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2 − yz + 1.
A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
In mathematics, a transcendental number is a number that is not algebraic—that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best known transcendental numbers are π and e.
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.
Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm which, for any given Diophantine equation, can decide whether the equation has a solution with all unknowns taking integer values.
In mathematics, a recurrence relation is an equation according to which the th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of ; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
Transcendental number theory is a branch of number theory that investigates transcendental numbers, in both qualitative and quantitative ways.
In mathematical logic, Skolem arithmetic is the first-order theory of the natural numbers with multiplication, named in honor of Thoralf Skolem. The signature of Skolem arithmetic contains only the multiplication operation and equality, omitting the addition operation entirely.
In additive and algebraic number theory, the Skolem–Mahler–Lech theorem states that if a sequence of numbers satisfies a linear difference equation, then with finitely many exceptions the positions at which the sequence is zero form a regularly repeating pattern. This result is named after Thoralf Skolem, Kurt Mahler, and Christer Lech. Its known proofs use p-adic analysis and are non-constructive.
The graph realization problem is a decision problem in graph theory. Given a finite sequence of natural numbers, the problem asks whether there is a labeled simple graph such that is the degree sequence of this graph.
In mathematics and theoretical computer science, a constant-recursive sequence is an infinite sequence of numbers where each number in the sequence is equal to a fixed linear combination of one or more of its immediate predecessors. A constant-recursive sequence is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, a C-finite sequence, or a solution to a linear recurrence with constant coefficients.
In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4, or equivalently the numbers whose binary representations are nonzero only in even positions.
In mathematics a P-recursive equation is a linear equation of sequences where the coefficient sequences can be represented as polynomials. P-recursive equations are linear recurrence equationswith polynomial coefficients. These equations play an important role in different areas of mathematics, specifically in combinatorics. The sequences which are solutions of these equations are called holonomic, P-recursive or D-finite.
References
- 1 2 3 Ouaknine, Joël; Worrell, James (2012), "Decision problems for linear recurrence sequences", Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7550, Heidelberg: Springer-Verlag, pp. 21–28, doi:10.1007/978-3-642-33512-9_3, MR 3040104 .
- ↑ Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. Akad. Skrifter, I (6). Ouaknine & Worrell (2012) instead cite a 1934 paper of Skolem for this result.
- ↑ Berstel, Jean; Mignotte, Maurice (1976), "Deux propriétés décidables des suites récurrentes linéaires", Bulletin de la Société Mathématique de France (in French), 104 (2): 175–184, doi: 10.24033/bsmf.1823 , MR 0414475 .
- ↑ Mignotte, M.; Shorey, T. N.; Tijdeman, R. (1984), "The distance between terms of an algebraic recurrence sequence", Journal für die Reine und Angewandte Mathematik , 349: 63–76, MR 0743965 .
- ↑ Vereshchagin, N. K. (1985), "The problem of the appearance of a zero in a linear recursive sequence", Matematicheskie Zametki (in Russian), 38 (2): 177–189, 347, MR 0808885 .
- ↑ Blondel, Vincent D.; Portier, Natacha (2002), "The presence of a zero in an integer linear recurrent sequence is NP-hard to decide", Linear Algebra and Its Applications, 351/352: 91–98, doi:10.1016/S0024-3795(01)00466-9, MR 1917474 .