|
K-regular Sequence
In mathematics and theoretical computer science, a ''k''-regular sequence is a sequence satisfying linear recurrence equations that reflect the base-''k'' representations of the integers. The class of ''k''-regular sequences generalizes the class of ''k''-automatic sequences to alphabets of infinite size. Definition There exist several characterizations of ''k''-regular sequences, all of which are equivalent. Some common characterizations are as follows. For each, we take ''R''′ to be a commutative Noetherian ring and we take ''R'' to be a ring containing ''R''′. ''k''-kernel Let ''k'' ≥ 2. The ''k-kernel'' of the sequence s(n)_ is the set of subsequences :K_(s) = \. The sequence s(n)_ is (''R''′, ''k'')-regular (often shortened to just "''k''-regular") if the R'-module generated by ''K''''k''(''s'') is a finitely-generated ''R''′- module.Allouche and Shallit (1992), Definition 2.1. In the special case when R' = R = \mathbb, the sequence s(n)_ is k-regular ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many areas of mathematics, which include number theory (the study of numbers), algebra (the study of formulas and related structures), geometry (the study of shapes and spaces that contain them), Mathematical analysis, analysis (the study of continuous changes), and set theory (presently used as a foundation for all mathematics). Mathematics involves the description and manipulation of mathematical object, abstract objects that consist of either abstraction (mathematics), abstractions from nature orin modern mathematicspurely abstract entities that are stipulated to have certain properties, called axioms. Mathematics uses pure reason to proof (mathematics), prove properties of objects, a ''proof'' consisting of a succession of applications of in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Thue–Morse Sequence
In mathematics, the Thue–Morse or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of 0s and 1s) that can be obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. It is sometimes called the fair share sequence because of its applications to fair division or parity sequence. The first few steps of this procedure yield the strings 0, 01, 0110, 01101001, 0110100110010110, and so on, which are the prefixes of the Thue–Morse sequence. The full sequence begins: :01101001100101101001011001101001.... The sequence is named after Axel Thue, Marston Morse and (in its extended form) Eugène Prouhet. Definition There are several equivalent ways of defining the Thue–Morse sequence. Direct definition To compute the ''n''th element ''tn'', write the number ''n'' in binary. If the number of ones in this binary expansion is odd then ''tn'' = 1, if even then ''tn'' = 0. Th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cambridge University Press
Cambridge University Press was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessment to form Cambridge University Press and Assessment under Queen Elizabeth II's approval in August 2021. With a global sales presence, publishing hubs, and offices in more than 40 countries, it published over 50,000 titles by authors from over 100 countries. Its publications include more than 420 academic journals, monographs, reference works, school and university textbooks, and English language teaching and learning publications. It also published Bibles, runs a bookshop in Cambridge, sells through Amazon, and has a conference venues business in Cambridge at the Pitt Building and the Sir Geoffrey Cass Sports and Social Centre. It also served as the King's Printer. Cambridge University Press, as part of the University of Cambridge, was a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Root Of Unity
In mathematics, a root of unity is any complex number that yields 1 when exponentiation, raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform. It is occasionally called a de Moivre number after French mathematician Abraham de Moivre. Roots of unity can be defined in any field (mathematics), field. If the characteristic of a field, characteristic of the field is zero, the roots are complex numbers that are also algebraic integers. For fields with a positive characteristic, the roots belong to a finite field, and, converse (logic), conversely, every nonzero element of a finite field is a root of unity. Any algebraically closed field contains exactly th roots of unity, except when is a multiple of the (positive) characteristic of the field. General definition An ''th root of unity'', where is a positive integer, is a nu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Power Series
In mathematics, a power series (in one variable) is an infinite series of the form \sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots where ''a_n'' represents the coefficient of the ''n''th term and ''c'' is a constant called the ''center'' of the series. Power series are useful in mathematical analysis, where they arise as Taylor series of infinitely differentiable functions. In fact, Borel's theorem implies that every power series is the Taylor series of some smooth function. In many situations, the center ''c'' is equal to zero, for instance for Maclaurin series. In such cases, the power series takes the simpler form \sum_^\infty a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots. The partial sums of a power series are polynomials, the partial sums of the Taylor series of an analytic function are a sequence of converging polynomial approximations to the function at the center, and a converging power series can be seen as a kind of generalized polynom ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convolution
In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions f and g that produces a third function f*g, as the integral of the product of the two functions after one is reflected about the y-axis and shifted. The term ''convolution'' refers to both the resulting function and to the process of computing it. The integral is evaluated for all values of shift, producing the convolution function. The choice of which function is reflected and shifted before the integral does not change the integral result (see #Properties, commutativity). Graphically, it expresses how the 'shape' of one function is modified by the other. Some features of convolution are similar to cross-correlation: for real-valued functions, of a continuous or discrete variable, convolution f*g differs from cross-correlation f \star g only in that either f(x) or g(x) is reflected about the y-axis in convolution; thus i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-synchronized Sequence
In mathematics and theoretical computer science, a ''k''-synchronized sequence is an infinite sequence of terms ''s''(''n'') characterized by a finite automaton taking as input two strings ''m'' and ''n'', each expressed in some fixed base ''k'', and accepting if ''m'' = ''s''(''n''). The class of ''k''-synchronized sequences lies between the classes of ''k''-automatic sequences and ''k''-regular sequences. Definitions As relations Let Σ be an alphabet of ''k'' symbols where ''k'' ≥ 2, and let 'n''sub>''k'' denote the base-''k'' representation of some number ''n''. Given ''r'' ≥ 2, a subset ''R'' of \mathbb^ is ''k''-synchronized if the relation is a right-synchronized rational relation over Σ∗ × ... × Σ∗, where (''n''1, ..., ''n''''r'') \in ''R''.Carpi & Maggi (2010) Language-theoretic Let ''n'' ≥ 0 be a natural number and let ''f'': \mathbb \rightarrow \mathbb be a map, where both ''n'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gould's Sequence
Gould's sequence is an integer sequence named after Henry W. Gould that counts how many odd numbers are in each row of Pascal's triangle. It consists only of power of two, powers of two, and begins:. :1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, ... For instance, the sixth number in the sequence is 4, because there are four odd numbers in the sixth row of Pascal's triangle (the four bold numbers in the sequence 1, 5, 10, 10, 5, 1). Gould's sequence is also a fractal sequence. Additional interpretations The th value in the sequence (starting from ) gives the highest power of 2 that divides the central binomial coefficient \tbinom, and it gives the numerator of 2^n/n! (expressed as a fraction in lowest terms). Gould's sequence also gives the number of live cells in the th generation of the Rule 90 cellular automaton starting from a single live cell.. It has a characteristic growing sawtooth wave, sawtooth shape that can be used to recognize physical processes that beha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integer-valued Polynomial
In mathematics, an integer-valued polynomial (also known as a numerical polynomial) P(t) is a polynomial whose value P(n) is an integer for every integer ''n''. Every polynomial with integer coefficients is integer-valued, but the converse is not true. For example, the polynomial : P(t) = \frac t^2 + \frac t=\fract(t+1) takes on integer values whenever ''t'' is an integer. That is because one of ''t'' and t + 1 must be an even number. (The values this polynomial takes are the triangular numbers.) Integer-valued polynomials are objects of study in their own right in algebra, and frequently appear in algebraic topology.. See in particular pp. 213–214. Classification The class of integer-valued polynomials was described fully by . Inside the polynomial ring \Q /math> of polynomials with rational number coefficients, the subring of integer-valued polynomials is a free abelian group. It has as basis the polynomials :P_k(t) = t(t-1)\cdots (t-k+1)/k! for k = 0,1,2, \dots, i.e. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sorting Number
In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort. However, there are other algorithms that use fewer comparisons. Formula and examples The nth sorting number is given by the formula The sequence of numbers given by this formula (starting with n = 1) is The same sequence of numbers can also be obtained from the recurrence relation, :A(n) = A\bigl(\lfloor n/2\rfloor\bigr) + A\bigl(\lceil n/2\rceil\bigr) + n - 1. It is an example of a 2-regular sequence. Asymptotically, the value of the nth sorting number fluctuates between approximately n\log_2 n - n and n\log_2 n - 0.915n, depending on the ratio between n and the nearest power of two. Application to sorting In 1950, Hugo Steinhaus observed that these numbers count the number of comparisons used by binary ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Merge Sort
In computer science, merge sort (also commonly spelled as mergesort and as ) is an efficient, general-purpose, and comparison sort, comparison-based sorting algorithm. Most implementations of merge sort are Sorting algorithm#Stability, stable, which means that the relative order of equal elements is the same between the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Herman Goldstine, Goldstine and von Neumann as early as 1948. Algorithm Conceptually, a merge sort works as follows: #Divide the unsorted list into ''n'' sub-lists, each containing one element (a list of one element is considered sorted). #Repeatedly Merge algorithm, merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list. Top-down implementation Example C-like code using indices for top-down merge sort algorit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stanley Sequence
In mathematics, a Stanley sequence is an integer sequence generated by a greedy algorithm that chooses the sequence members to avoid arithmetic progressions. If S is a finite set of non-negative integers on which no three elements form an arithmetic progression (that is, a Salem–Spencer set), then the Stanley sequence generated from S starts from the elements of S, in sorted order, and then repeatedly chooses each successive element of the sequence to be a number that is larger than the already-chosen numbers and does not form any three-term arithmetic progression with them. These sequences are named after Richard P. Stanley. Binary–ternary sequence The Stanley sequence starting from the empty set consists of those numbers whose ternary representations have only the digits 0 and 1. That is, when written in ternary, they look like binary numbers. These numbers are :0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... By their construction as a Stanley sequence, this ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
