IntegerSequences 1.52

documentation notebook

Eric Rowland
https://ericrowland.github.io/packages.html

Introduction

IntegerSequences is a package for identifying and computing with integer sequences from a variety of classes.
This introduction gives an overview of the main features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.

To use IntegerSequences, first you will need to load the package by evaluating the following cell. (If you need help, see loading a package.)

<<IntegerSequences`

Named integer sequences

A number of named integer sequences are implemented in IntegerSequences:
• the 2-automatic sequence BaumSweet,
• the constant-recursive sequences JacobsthalNumber and Tribonacci,
• the 2-regular sequence SternBrocot,
• the algebraic sequence MotzkinNumber, and
• the holonomic sequence AperyNumber.

The nth term of the Baum–Sweet sequence is 1 if the binary representation of n contains no block of zeros of odd length, and 0 otherwise.

Table[BaumSweet[n],{n,0,15}]

The sequence of Jacobsthal numbers satisfies a linear recurrence of order 2:

Table[JacobsthalNumber[n],{n,0,10}]

FindLinearRecurrence[%]

The Tribonacci sequence satisfies a linear recurrence of order 3:

Table[Tribonacci[n],{n,0,10}]

FindLinearRecurrence[%]

The Stern–Brocot sequence satisfies a recurrence that reflects the binary representation of integers.

Table[SternBrocot[n],{n,0,15}]

The Motzkin numbers are closely related to the Catalan numbers.

Table[MotzkinNumber[n],{n,0,10}]

The Apéry numbers arose in Apéry’s proof that Zeta[3] is irrational.

Table[AperyNumber[n],{n,0,10}]

OEIS lookup

The function OEISWebLookup can be used to look up the first few terms of a sequence in The On-Line Encyclopedia of Integer Sequences.
It opens a web browser to the results page.

OEISWebLookup[{1,1,2,3,5,8,13,21}]

Additionally, OEISWebLookup can open the page corresponding to a sequence:

OEISWebLookup["A000002"]

Elementary number theory

The radical of an integer is the product of its prime divisors.

Radical[200]

IntegerSequences extends built-in Wolfram Language functionality for number theoretic functions on integers such as DigitCount, IntegerDigits, and BitGet.

DigitsCount counts subwords in the base-b representation of a number:

DigitsCount[1000,10,{0,0}]

DigitList allows the base to be negative:

DigitList[27,-3]

Use FromDigitList to reconstruct the integer:

FromDigitList[{0,0,0,2,1},-3]

DigitGet extracts digits in any base (positive or negative):

DigitGet[27,-3,3]

Polynomials and formal power series

FromCoefficientList provides an inverse to the Wolfram Language function CoefficientList.

FromCoefficientList[{1,2,3,4,5},x]

SeriesSolve produces series solutions for a function defined implicitly by an equation.

SeriesSolve[f[x]==x+((f[x])^5),f[x],{x,0,5}]

In counting combinatorial objects one frequently encounters systems of linear recurrences in a multidimensional counting function.  One technique is then to use generating functions to rewrite the system and in some cases solve it algebraically.  GeneratingFunctionRelations automates the process of converting a linear system of partial recurrence equations into a system of equations in the generating function.

GeneratingFunctionRelations[s[n,0]==2s[n-1,1]&&s[n,m]==s[n+1,m]-s[n-1,m-1]+3 s[n-1,m+1],s[n,m],f[x,y]]

Identifying integer sequences

The Wolfram Language has several powerful built-in symbols for sequence identification, including InterpolatingPolynomial, FindSequenceFunction, and FindGeneratingFunction.  IntegerSequences generalizes InterpolatingPolynomial to multidimensional arrays.

Find the polynomial in x and y that reproduces an array of values for 1≤x≤3 and 1≤y≤4:

FindPolynomial[{{5,29,83,179},{11,78,247,566},{21,159,519,1209}},{x,y}]

Table[-x+x y+3 (y^2)+2 (x^2) (y^3),{x,3},{y,4}]

IntegerSequences includes several symbols for identifying sequences.

A quasi-polynomial is a function that, when restricted to each residue class modulo m, is a polynomial.  For example, the coefficients of some rational series are quasi-polynomials.

Series[(1/(((1+x+(x^2)+(x^3)+(x^4)))^2)),{x,0,20}]

FindQuasiPolynomial[CoefficientList[Normal[Series[(1/(((1+x+(x^2)+(x^3)+(x^4)))^2)),{x,0,20}]],x],n+1,5]

(∑_(n=0)^20)(x^n)(Piecewise[{{0, Mod[1+n,5]==0}, {1+(n/5), Mod[1+n,5]==1}, {-(8/5)-((2 n)/5), Mod[1+n,5]==2}, {(3/5)+(n/5), Mod[1+n,5]==3}, {0, True}}])

See the next subsections for identifying k-automatic sequences and k-regular sequences.

Automata and automatic sequences

A sequence s(n) is k-automatic if there is an automaton that outputs s(n) when fed the base-k digits of n.

AutomatonGraph[Automaton[{{0->0,0},{0->1,1},{1->1,0},{1->0,1}},0]]

m=Automaton[{{"0"->"0",0},{"0"->"1",1},{"0"->"2",2},{"1"->"3",0},{"1"->"1",1},{"1"->"2",2},{"2"->"4",0},{"2"->"3",1},{"2"->"1",2},{"3"->"2",0},{"3"->"4",1},{"3"->"3",2},{"4"->"3",0},{"4"->"2",1},{"4"->"4",2}},"0",{"0"|"1"|"4"->"a","2"->"b","3"->"c"}];

AutomatonGraph[m]

This is the sequence before the output (or “coding”) rules are applied:

Table[Most[m][IntegerDigits[n,3]],{n,0,(3^3)-1}]

And with the output rules:

Table[m[IntegerDigits[n,3]],{n,0,(3^4)-1}]

Clear[m]

FindAutomaticSequenceAutomaton takes a list of terms and attempts to find an automaton that produces it:

FindAutomaticSequenceAutomaton[ThueMorse[Range[0,100]],2]
AutomatonGraph[%]

FindAutomaticSequenceRecurrence finds a recurrence instead:

FindAutomaticSequenceRecurrence[ThueMorse[Range[0,100]],2,T[n]]

Regular sequences

Regular sequences are a natural generalization of automatic sequences to infinite alphabets.  They were introduced by Allouche and Shallit in the paper "The ring of k-regular sequences" (Theoretical Computer Science 98 (1992) 163–197); the paper can be found here.

Let s(n) be the parity of the number of 1s in the binary representation of n.

Table[Mod[DigitCount[n,2,1],2],{n,0,31}]

That sequence is 2-automatic.  Therefore it is also 2-regular, and FindRegularSequenceFunction gives a representation for this sequence.

f=FindRegularSequenceFunction[%,2]

FindRegularSequenceFunction returns a RegularSequence object, which behaves as a function like DifferenceRoot.

f[Range[0,31]]

Clear[f]

If we consider instead the total number of 1s in the binary representation of n, this sequence does not take finitely many values, so it is not automatic.

Table[DigitCount[n,2,1],{n,0,31}]

However, it is 2-regular:

f=FindRegularSequenceFunction[%,2]

f[Range[0,31]]

The symbol FindRegularSequenceRecurrence gives the same information as FindRegularSequenceFunction but in a different form — as a list of linear recurrences and initial conditions that determine the sequence.

FindRegularSequenceRecurrence[Table[DigitCount[n,2,1],{n,0,31}],2,s[n]]

RegularSequenceRecurrenced produces this information from a RegularSequence object, with indexed symbolic subsequences for the generators:

RegularSequenceRecurrence[f,s[n]]

Clear[f]

Studying a regular sequence

The Thue–Morse sequence is a famous example of a 2-automatic sequence.  It is an infinite sequence of 0s and 1s with the property that no block of entries ever occurs three times in a row.

Table[ThueMorse[n],{n,0,31}]

tm=FindRegularSequenceFunction[%,2]

tm[Range[0,31]]

The Thue–Morse sequence t(n) satisfies the following system of linear recurrences.

FindRegularSequenceRecurrence[ThueMorse[Range[0,31]],2,t[n]]

Here are the first few terms of the basis subsequences:

RegularSequenceGeneratorTable[tm,15]

Clear[tm]

Other examples of regular sequences

RegularSequenceMatrixForm[FindRegularSequenceFunction[Accumulate[ThueMorse[Range[0,31]]],2]]

RegularSequenceMatrixForm[FindRegularSequenceFunction[IntegerExponent[Range[64],2],2]]

RegularSequenceMatrixForm[FindRegularSequenceFunction[IntegerExponent[Range[0,31]!,2],2]]

RegularSequenceMatrixForm[FindRegularSequenceFunction[IntegerExponent[Fibonacci[Range[(2^7)]],2],2]]

RegularSequenceMatrixForm[FindRegularSequenceFunction[IntegerExponent[Fibonacci[Range[1000]],4],4]]

RegularSequenceMatrixForm[FindRegularSequenceFunction[Accumulate[Table[Boole[Length[PowersRepresentations[n,3,2]]>0],{n,0,(2^6)}]],2]]

RegularSequenceMatrixForm[FindRegularSequenceFunction[CellularAutomaton[90,{{1},0},{(2^5)-1,{{3}}}],2]]

The number of nonzero entries in the nth row of an additive cellular automaton is a regular sequence:

RegularSequenceMatrixForm[FindRegularSequenceFunction[Total/@CellularAutomaton[{27030,2,(3/2)},{{1},0},(2^5)-1],2]]

RegularSequenceMatrixForm[FindRegularSequenceFunction[Total/@CellularAutomaton[{39270,2,(3/2)},{{1},0},(2^6)-1],2]]

Multidimensional regular sequences

IntegerSequences also supports multidimensional regular sequences.

Pascal’s triangle modulo 2 is (2,2)-regular:

RegularSequenceMatrixForm[FindRegularSequenceFunction[Table[Mod[Binomial[n,m],2],{n,0,(2^5)-1},{m,0,(2^5)-1}],2]]

More generally, sequences obtained by iterating a morphism are regular.  This is a (2,3)-regular sequence:

RegularSequenceMatrixForm[FindRegularSequenceFunction[Nest[Function[matrix,ArrayFlatten[matrix/.{1->{{1,0,1},{0,1,1}},0->{{0,1,0},{1,1,1}}},2]],{{1}},4],{2,3}]]

Package symbols

AlgebraicSequence

?AlgebraicSequence

AlgebraicSequence[Function[y,x (y^2)+(2 x-1) y+x],x][10]

Table[AlgebraicSequence[Function[y,x (y^2)+(2 x-1) y+x],x][n],{n,0,10}]

Those are the coefficients of the power series solution:

SeriesSolve[x ((f[x])^2)+(2 x-1) f[x]+x==0,f[x],{x,0,10}]

The implicit function theorem does not apply to this polynomial:

AlgebraicSequence[Function[y,x (y^2)-y+1],x][10]

Use SeriesRoot to identify a particular root by an approximation:

AlgebraicSequence[SeriesRoot[{Function[y,x (y^2)-y+1],1+x+2 (x^2)+((O[x])^3)}]][10]

AperyNumber

?AperyNumber

Table[AperyNumber[n],{n,0,10}]

AperyNumber[100]

AperyNumber[1.5]

AutomaticSequence

?AutomaticSequence

Compute a term of the Thue–Morse sequence:

AutomaticSequence[Automaton[{{0->0,0},{0->1,1},{1->1,0},{1->0,1}},0]][27]

Compute the first few terms:

Table[AutomaticSequence[Automaton[{{0->0,0},{0->1,1},{1->1,0},{1->0,1}},0]][n],{n,0,31}]

This two-dimensional automatic sequence produces Pascal’s triangle modulo 2:

ArrayPlot[Table[AutomaticSequence[Automaton[{{{0,{0,0}}->{0,{0,0}},{0,0}},{{0,{0,0}}->{1,{0,1}},{0,1}},{{0,{0,0}}->{0,{0,0}},{1,0}},{{0,{0,0}}->{0,{0,0}},{1,1}},{{1,{0,1}}->{1,{0,1}},{0,0}},{{1,{0,1}}->{1,{0,1}},{0,1}},{{1,{0,1}}->{1,{0,1}},{1,0}},{{1,{0,1}}->{1,{0,1}},{1,1}}},{0,{0,0}},{{0,{0,0}}->1,{1,{0,1}}->0}]][n,m],{n,0,63},{m,0,63}]]

AutomaticSequenceAutomaton

?AutomaticSequenceAutomaton

AutomaticSequenceAutomaton[AutomaticSequence[Automaton[{{1->1,0},{1->2,1},{2->2,0},{2->1,1}},1,{1->0,2->1}],2][n]]

AutomatonGraph[%]

AutomaticSequenceReduce

?AutomaticSequenceReduce

AutomaticSequenceReduce[ThueMorse[n],n]

AutomaticSequenceReduce[RudinShapiro[n],n]

Write an integer sequence modulo a prime power as an automatic sequence, and visualize the automaton as a graph:

AutomaticSequenceReduce[Mod[CatalanNumber[n],4],n]
AutomatonGraph[AutomaticSequenceAutomaton[%]]

Specify Monitor->True to display progress information:

AutomaticSequenceReduce[Mod[CatalanNumber[n],8],n,Monitor->True]

Write an algebraic sequence modulo a prime power as an automatic sequence:

AutomaticSequenceReduce[Mod[AlgebraicSequence[SeriesRoot[{Function[y,(x^2) (y^2)+(x-1) y+1],((O[x])^0)}]][n],4],n]
AutomatonGraph[AutomaticSequenceAutomaton[%],VertexSize->0.5]

There are three methods available to AutomaticSequenceReduce for prime modulus.

Different methods can take different amounts of time:

AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],11],n,Method->"ConstantTerm"]]]]
AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],11],n,Method->"Diagonal"]]]]
AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],11],n,Method->"OrePolynomial"]]]]

For prime power modulus, only the methods “ConstantTerm” and “Diagonal” apply:

AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],8],n,Method->"ConstantTerm"]]]
AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],8],n,Method->"Diagonal"]]]
AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],8],n,Method->"OrePolynomial"]]]

By default, automata are minimized.
The number of states in the unminimized automata can be different:

AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],16],n,Method->"ConstantTerm",Minimize->False]]]]
AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],16],n,Method->"Diagonal",Minimize->False]]]]

The method “Diagonal” supports two variants — low degree and high degree.  The default is low degree.
With "Degree"->"High", the polynomials have higher degree and therefore take up more memory but frequently produce an automaton with fewer states:

AutomaticSequenceReduce[Mod[AperyNumber[n],8],n,Method->{"Diagonal","Degree"->"High"},Minimize->False]
AutomaticSequenceReduce[Mod[AperyNumber[n],8],n,Method->{"Diagonal","Degree"->"Low"},Minimize->False]

Many more examples computing combinatorial sequences modulo prime powers appear in the computation notebook accompanying the paper “Automatic congruences for diagonals of rational functions” by Eric Rowland and Reem Yassawi.

For certain automata, state names are by default compressed so that equivalent states are often combined into one.

?CompressStateNames

Specify CompressStateNames->False to prevent compression:

AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],16],n,Method->"ConstantTerm",Minimize->False]]]]
AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],16],n,CompressStateNames->False,Method->"ConstantTerm",Minimize->False]]]]

Additional options can help manage memory when computing large automata.

?HashStateNames

Using HashStateNames->True reduces memory usage; once the transitions from a state are computed, only the hash code of the state is kept (for comparing to other states).
In the unlikely event that two state names have the same hash code, this may result in an incorrect automaton in which two states that are not equivalent are combined into one.

?StateStorage

Use StateStorage->"Disk" to export state names to disk rather than keep them in memory.
Each state receives its own file, and the files are deleted after the automaton has been computed.

AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],16],n,Method->"Diagonal",StateStorage->"Disk"]]]]

By default, files containing state names are exported to $TemporaryDirectory, but this shouldn’t be used for long computations, since the operating system can start deleting temporary files there.
Specify a different directory as follows.

AbsoluteTiming[AutomatonStateCount[AutomaticSequenceAutomaton[AutomaticSequenceReduce[Mod[MotzkinNumber[n],16],n,Method->"Diagonal",StateStorage->{"Disk","Directory"->$HomeDirectory}]]]]

Automaton

?Automaton

Define an automaton that computes terms of the Thue–Morse sequence:

m=Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{A->0,B->1}];

Generate the directed graph corresponding to the automaton:

AutomatonGraph[m]

Evaluate the automaton on an input:

m[{0,1,1,1,0,1}]

Table[m[IntegerDigits[n,2]],{n,0,31}]

Clear[m]

Specifying different output rules changes the output alphabet:

Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{A->"even",B->"odd"}][{0,1,1,1,0,1}]

An automaton outputting True and False can be thought of as recognizing a certain language:

Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{A->True,B->False}][{0,1,1,1,0,1}]

When no output rules are given, Automaton returns the last state visited:

Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A][{0,1,1,1,0,1}]

The output rules can be a rule, a list of rules, or a dispatch table, and can contain patterns:

Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{_->"constant"}][{0,1,1,1,0,1}]

Edge labels can also contain patterns:

Automaton[{{A->A,0},{A->B,1},{B->B,_}},A][{1,1,0}]

If the automaton reaches a state from which there is no edge that the current input element matches, then Automaton returns $Failed:

Automaton[{{A->B,0|1},{B->A,0}},A][{0,1}]

Including a rule for $Failed in the output rule is a convenient way to represent an automaton which accepts a certain language:

Automaton[{{A->B,0|1},{B->A,0}},A,{A->True,B->True,$Failed->False}][{0,1}]

If there are multiple edges that an input element matches, the Automaton uses the first matching edge in the edge list:

Automaton[{{A->B,0},{A->C,0}},A][{0}]

Patterns in edge labels prevent AutomatonInputAlphabet from being able to determine the input alphabet:

AutomatonInputAlphabet[Automaton[{{A->A,0},{A->B,1},{B->B,_}},A]]

Use InputAlphabet to specify the input alphabet explicitly:

AutomatonInputAlphabet[Automaton[{{A->A,0},{A->B,1},{B->B,_}},A,InputAlphabet->{0,1}]]

AutomatonAdjacencyMatrix

?AutomatonAdjacencyMatrix

The adjacency matrix counts occurrences of each state in the image of each other state.

automaton=Automaton[{{1->2,0},{1->1,1},{2->1,0},{2->3,1},{3->3,0},{3->3,1}},1,{1->1,2->1,3->0}];
AutomatonGraph[automaton]

m=AutomatonAdjacencyMatrix[automaton]

Use Normal to convert a sparse array to a list of lists:

Normal[m]
%//MatrixForm

Clear[automaton,m]

AutomatonDeterminize

?AutomatonDeterminize

When no output rules are given, the outputs of the determinized automaton are lists of states from the original automaton:

AutomatonDeterminize[Automaton[{{A->B,0|1},{A->C,0|1},{B->B,0|1},{C->C,0|1}},A,InputAlphabet->{0,1}]]

If the original automaton is underdetermined, then the empty list {} is a possible output for the determinized automaton:

AutomatonDeterminize[Automaton[{{A->B,0}},A,{A->True,B->True}]]

AutomatonGraph

?AutomatonGraph

AutomatonGraph[Automaton[{{0->0,0},{0->1,1},{1->1,0},{1->0,1}},0,{0->"even",1->"odd"}]]

The result is a directed graph, so built-in graph functionality can then be used directly:

EdgeCount[%]

The edge pointing to the initial state vertex has an invisible source vertex, so the number of vertices in the graph above is 3:

VertexCount[%%]

AutomatonInputAlphabet

?AutomatonInputAlphabet

AutomatonInputAlphabet[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{A->"even",B->"odd"}]]

Patterns in edge labels prevent AutomatonInputAlphabet from being able to determine the input alphabet:

AutomatonInputAlphabet[Automaton[{{A->A,0},{A->B,1},{B->B,_}},A]]

Use InputAlphabet to specify the input alphabet explicitly:

AutomatonInputAlphabet[Automaton[{{A->A,0},{A->B,1},{B->B,_}},A,InputAlphabet->{0,1}]]

AutomatonMinimize

?AutomatonMinimize

The two states A and D with output True in this automaton are equivalent:

M=Automaton[{{A->B,0},{A->C,1},{B->C,0},{B->C,1},{C->B,0},{C->D,1},{D->B,0},{D->C,1}},A,{A->True,B->False,C->False,D->True}];
AutomatonGraph[M]
AutomatonGraph[AutomatonMinimize[M]]
Clear[M]

M=Automaton[{{A->B,0},{B->C,0},{C->D,0},{D->A,0}},A,{A->0,B->1,C->0,D->1}];
AutomatonGraph[M]
AutomatonGraph[AutomatonMinimize[M]]
Clear[M]

AutomatonMinimize removes unreachable states:

M=Automaton[{{A->B,0},{A->C,1},{B->C,0},{B->C,1},{C->B,0},{C->A,1},{U->A,0},{U->B,1}},A];
AutomatonGraph[M]
AutomatonGraph[AutomatonMinimize[M]]
Clear[M]

AutomatonOutputAlphabet

?AutomatonOutputAlphabet

AutomatonOutputAlphabet[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{A->"even",B->"odd"}]]

If no output rules are provided, the output values are the state names:

AutomatonOutputAlphabet[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A]]

The values reported are the outputs corresponding to all states reachable from the initial state by some sequence of letters from the input alphabet.
For example, the following automaton has an unreachable state whose corresponding output is not included.

AutomatonOutputAlphabet[Automaton[{{A->A,0|1},{B->A,0|1}},A,{A->"even",B->"odd"},InputAlphabet->{0,1}]]

In the following automaton, only one state explicitly appears, and it corresponds to the output ”even”, but the input alphabet indicates that there exist inputs that result in ”odd” (due to missing edges):

AutomatonOutputAlphabet[Automaton[{{A->A,0}},A,{A->"even",_->"odd"},InputAlphabet->{0,1}]]

Changing the input alphabet results in only the output “even” being reported:

AutomatonOutputAlphabet[Automaton[{{A->A,0}},A,{A->"even",_->"odd"},InputAlphabet->{0}]]

This automaton is not deterministic, so $Failed is included to account for input for which there are missing edges:

AutomatonOutputAlphabet[Automaton[{{A->A,0},{A->B,1},{B->B,0}},A]]

If the edge labels contain patterns and no explicit input alphabet is indicated, AutomatonOutputAlphabet may not be able to determine the reachable states:

AutomatonOutputAlphabet[Automaton[{{A->A,0|1}},A,{A->"even",_->"odd"}]]

AutomatonOutputRules

?AutomatonOutputRules

AutomatonOutputRules[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{A->"even",B->"odd"}]]

A dispatch table is a valid specification for the output rules:

AutomatonOutputRules[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,Dispatch[{A->"even",B->"odd"}]]]

If no output rules are explicitly specified, AutomatonOutputRules returns the empty list:

AutomatonOutputRules[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A]]

AutomatonProduct

?AutomatonProduct

AutomatonGraph[AutomatonProduct[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A],Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A]]]

By default, the resulting product automaton is minimized.  Include Minimize->False to omit the minimization step:

AutomatonGraph[AutomatonProduct[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A],Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A],Minimize->False]]

AutomatonQ

?AutomatonQ

AutomatonQ[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A]]

The initial state must appear in the edge list for the automaton to be valid:

AutomatonQ[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},0]]

States named $Failed are disallowed:

AutomatonQ[Automaton[{{A->$Failed,0|1}},A]]

AutomatonReverse

?AutomatonReverse

If the input automaton has no unreachable states, then the reversed automaton is minimal:

automaton=Automaton[{{1->1,0},{1->2,1},{2->2,0},{2->1,1}},1,{1->0,2->1}];
AutomatonStateCount[reversedautomaton=AutomatonReverse[automaton]]
AutomatonStateCount[AutomatonMinimize[reversedautomaton]]
Clear[automaton,reversedautomaton]

If there are unreachable states, then the reversed automaton may not be minimal:

automaton=Automaton[{{1->1,0},{1->2,1},{2->2,0},{2->1,1},{3->1,0},{3->2,1}},1,{1->0,2->1,3->2}];
AutomatonStateCount[reversedautomaton=AutomatonReverse[automaton]]
AutomatonStateCount[AutomatonMinimize[reversedautomaton]]
Clear[automaton,reversedautomaton]

AutomatonStateCount

?AutomatonStateCount

AutomatonStateCount[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{A->"even",B->"odd"}]]

Unreachable states are included in the count:

AutomatonStateCount[Automaton[{{A->A,0|1},{B->A,0|1}},A]]

AutomatonStateList

?AutomatonStateList

AutomatonStateList[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A,{A->"even",B->"odd"}]]

Unreachable states are included:

AutomatonStateList[Automaton[{{A->A,0|1},{B->A,0|1}},A]]

BaumSweet

?BaumSweet

Table[BaumSweet[n],{n,0,31}]

Write BaumSweet as an automatic sequence:

AutomaticSequenceReduce[BaumSweet[n],n]

CauchyProduct

?CauchyProduct

CauchyProduct[{1,2,3,4},{a,b,c,d}]

The Cauchy product of two sequences corresponds to the multiplication of their generating functions:

CoefficientList[((∑_(i=0)^5)(Subscript[a, i]) (x^i))( (∑_(i=0)^5)(Subscript[b, i]) (x^i)),x]

CauchyProduct[PadRight[Thread[(Subscript[a, Range[0,5]])],11],PadRight[Thread[(Subscript[b, Range[0,5]])],11]]

%==%%

CompleteAutomatonQ

?CompleteAutomatonQ

CompleteAutomatonQ[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A]]

This automaton has no outgoing edge labeled 1 from its initial state:

CompleteAutomatonQ[Automaton[{{A->A,0},{A->B,1},{B->B,0}},A]]

Deleting an edge results in an automaton that is complete, however, since the input alphabet is inferred to consist only of a single letter:

CompleteAutomatonQ[Automaton[{{A->A,0},{B->B,0}},A]]

If the input alphabet cannot be determined, CompleteAutomatonQ evaluates to False:

CompleteAutomatonQ[Automaton[{{A->B,0|1},{B->A,0|1}},A]]

Use InputAlphabet to specify the input alphabet explicitly:

CompleteAutomatonQ[Automaton[{{A->B,0|1},{B->A,0|1}},A,InputAlphabet->{0,1}]]

CompleteAutomatonQ[Automaton[{{A->B,_?EvenQ},{A->C,_?OddQ},{B->B,0|1},{C->C,0|1}},A,InputAlphabet->{0,1}]]

ConstantTermSequence

?ConstantTermSequence

ConstantTermSequence[(1/x)+x+(x^2),x][10]

Table[ConstantTermSequence[(1/x)+x+(x^2),x][n],{n,0,10}]

Many combinatorial sequences can be represented as constant-term sequences.

ConstantTermSequence[(1/x)+2+x,1-x,x]/@Range[0,10]
CatalanNumber/@Range[0,10]

Use AutomaticSequenceReduce to compute an automaton for a constant-term sequence modulo a prime power:

AutomaticSequenceReduce[Mod[ConstantTermSequence[(1/x)+2+x,1-x,x][n],8],n]

ConstantTermSequenceReduce

?ConstantTermSequenceReduce

ConstantTermSequenceReduce[CatalanNumber[n],n]

ConstantTermSequenceReduce[MotzkinNumber[n],n]

ConstantTermSequenceReduce[AperyNumber[n],n]

DeterministicAutomatonQ

?DeterministicAutomatonQ

DeterministicAutomatonQ[Automaton[{{A->A,0},{A->B,1},{B->B,0},{B->A,1}},A]]

This automaton has no outgoing edge labeled 1 from its initial state:

DeterministicAutomatonQ[Automaton[{{A->A,0},{A->B,1},{B->B,0}},A]]

Deleting an edge results in an automaton that is deterministic, however, since the input alphabet is inferred to consist only of a single letter:

DeterministicAutomatonQ[Automaton[{{A->A,0},{B->B,0}},A]]

If the input alphabet cannot be determined, DeterministicAutomatonQ evaluates to False:

DeterministicAutomatonQ[Automaton[{{A->B,0|1},{B->A,0|1}},A]]

Use InputAlphabet to specify the input alphabet explicitly:

DeterministicAutomatonQ[Automaton[{{A->B,0|1},{B->A,0|1}},A,InputAlphabet->{0,1}]]

DeterministicAutomatonQ[Automaton[{{A->B,_?EvenQ},{A->C,_?OddQ},{B->B,0|1},{C->C,0|1}},A,InputAlphabet->{0,1}]]

Duplicate edges in an automaton make it nondeterministic:

DeterministicAutomatonQ[Automaton[{{A->A,0},{A->A,0}},A,InputAlphabet->{0,1}]]

More generally, if there is any state with two outgoing edges whose labels can be matched by the same letter of the input alphabet, then the automaton is nondeterministic:

DeterministicAutomatonQ[Automaton[{{A->B,_},{A->A,1},{B->B,0|1}},A,InputAlphabet->{0,1}]]

Such an automaton is considered nondeterministic even though it can be evaluated uniquely:

Automaton[{{A->B,_},{A->A,1},{B->B,0|1}},A,InputAlphabet->{0,1}][{1}]

DiagonalSequence

?DiagonalSequence

DiagonalSequence[(1/(1-x-y)),{x,y}][10]

Table[DiagonalSequence[(1/(1-x-y)),{x,y}][n],{n,0,10}]

Many combinatorial sequences can be represented as diagonal sequences.

DiagonalSequence[((1-x)/(1-(((1+x))^2) y)),{x,y}]/@Range[0,10]
CatalanNumber/@Range[0,10]

Use AutomaticSequenceReduce to compute an automaton for a diagonal sequence modulo a prime power:

AutomaticSequenceReduce[Mod[DiagonalSequence[((1-x)/(1-(((1+x))^2) y)),{x,y}][n],8],n]

DiagonalSequenceReduce

?DiagonalSequenceReduce

DiagonalSequenceReduce[CatalanNumber[n],n]

DiagonalSequenceReduce[MotzkinNumber[n],n]

DiagonalSequenceReduce[AperyNumber[n],n]

Render an algebraic sequence as the diagonal of a rational function:

DiagonalSequenceReduce[AlgebraicSequence[Function[y,(y^2)-y+x],x][n],n]

DiagonalSequenceReduce[AlgebraicSequence[SeriesRoot[{Function[y,x (y^2)-y+1],1+x+2 (x^2)+((O[x])^3)}]][n],n]

DigitGet (a generalization of BitGet)

?DigitGet

DigitGet[100,2,#]&/@Range[0,6]

DigitList[100,2]

DigitGet works with negative integer bases.

DigitList[2179,-3]

DigitGet[2179,-3,#]&/@Range[0,10]

Use FromDigitList to reconstruct the integer:

FromDigitList[{1,0,2,1,0,0,0,2,1,0,0},-3]

DigitList (a variant and generalization of IntegerDigits)

?DigitList

DigitList extends functionality of IntegerDigits to negative integer bases and some other numeration systems.

DigitList[2179,-3]

Use FromDigitList to reconstruct the integer:

FromDigitList[{1,0,2,1,0,0,0,2,1},-3]

DigitList[2179,"Factorial"]

FromDigitList[{1,0,3,0,0,3},"Factorial"]

Unlike IntegerDigits, DigitList considers 0 to have length 0:

IntegerDigits[0,2]

DigitList[0,2]

DigitsCount (a generalization of DigitCount)

?DigitsCount

DigitsCount[1111729111,10,{1,1}]

DigitsCount[1111729111,10,{1,1,1}]

DigitsCount does not pad the representation with zeros, even if the digit list ends with zeros:

DigitsCount[FromDigits["101",2],2,{1,0}]

DigitsCount[FromDigits["1010101",2],2,{0,1,0}]

Unlike DigitCount, DigitsCount considers 0 to have length 0:

DigitCount[0,2,0]

DigitsCount[0,2,0]

ExponentialFit

?ExponentialFit

The Catalan numbers grow like (4^n):

ExponentialFit[Table[CatalanNumber[n],{n,1,(2^9)}],n]

Here’s some real-number data:

data={10.`,15.612574113277207`,24.70386518931618`,39.516342548916185`,63.765170063553484`,103.61351355890355`,169.2961651538645`,277.823146596014`,457.48256843480885`,755.3413333419933`,1249.741064295883`,2071.1178815045305`,3436.6932904541945`,5708.281045106325`,9488.61735284084`,15781.892410001776`,26261.278682627835`,43714.78003088225`,72788.27311885271`,121223.85752507689`,201923.7051529616`};

exp=ExponentialFit[data,x]

Show[ListPlot[data,PlotRange->All],Plot[exp,{x,0,Length[data]},PlotRange->All]]

ExponentialFit fits a least-squares line to the logarithm of the data:

Show[ListPlot[Log[data]],Plot[Log[exp],{x,0,Length[data]}]]

Clear[data,exp]

FactorForm

?FactorForm

Grid[Table[{n,FactorForm[n!]},{n,0,10}]]

FactorForm[Zeta[8]]

FactorGrid

?FactorGrid

FactorGrid[(2^(Range[20]))-1]

FactorGrid[BernoulliB[Range[0,20,2]]]

FactorGrid[1+Range[20] I]

FindAutomaticSequenceAutomaton

?FindAutomaticSequenceAutomaton

FindAutomaticSequenceAutomaton[ThueMorse[Range[0,100]],2]

AutomaticSequence[%]/@Range[0,15]

Binomial coefficients modulo 2:

FindAutomaticSequenceAutomaton[Table[Mod[Binomial[n,m],2],{n,0,100},{m,0,100}],2]

ArrayPlot[Table[AutomaticSequence[%][n,m],{n,0,63},{m,0,63}]]

FindAutomaticSequenceAutomaton has a few options:

Options[FindAutomaticSequenceAutomaton]

?IndexedStateNames

By default, states are assigned integer names.  To preserve information about the k-kernel subsequence corresponding to each state, set the IndexedStateNames option to False.

FindAutomaticSequenceAutomaton[ThueMorse[Range[0,100]],2]
FindAutomaticSequenceAutomaton[ThueMorse[Range[0,100]],2,IndexedStateNames->False]

?FlattenInputAlphabet

For one-dimensional sequences, the digit lists are stripped by default, since they contain only one element.  To retain the lists, use the FlattenInputAlphabet option:

FindAutomaticSequenceAutomaton[ThueMorse[Range[0,100]],2]
FindAutomaticSequenceAutomaton[ThueMorse[Range[0,100]],2,FlattenInputAlphabet->False]

Use Monitor to display progress information:

AutomatonStateCount[FindAutomaticSequenceAutomaton[Mod[CatalanNumber[Range[0,5000]],32],2,Monitor->True]]

FindAutomaticSequenceFunction

?FindAutomaticSequenceFunction

t=FindAutomaticSequenceFunction[ThueMorse[Range[0,100]],2]

Table[t[n],{n,0,15}]

Clear[t]

Binomial coefficients modulo 2:

b=FindAutomaticSequenceFunction[Table[Mod[Binomial[n,m],2],{n,0,100},{m,0,100}],2]

ArrayPlot[Table[b[n,m],{n,0,63},{m,0,63}]]

Clear[b]

FindAutomaticSequenceFunction has the same options as FindAutomaticSequenceAutomaton:

Options[FindAutomaticSequenceFunction]

FindAutomaticSequenceRecurrence

?FindAutomaticSequenceRecurrence

FindAutomaticSequenceRecurrence[ThueMorse[Range[0,100]],2,T[n]]

Binomial coefficients modulo 2:

FindAutomaticSequenceRecurrence[Table[Mod[Binomial[n,m],2],{n,0,100},{m,0,100}],2,b[n,m]]

FindPolynomial (a variant of InterpolatingPolynomial)

?FindPolynomial

One-dimensional data:

Table[x-(x^2),{x,-1,3}]

FindPolynomial[{-2,0,0,-2,-6},x]

FindPolynomial[{-2,0,0,-2,-6},x,-1]

Two-dimensional data:

Table[-x+x y+3 (y^2)+2 (x^2) (y^3),{x,1,3},{y,1,4}]

FindPolynomial[{{5,29,83,179},{11,78,247,566},{21,159,519,1209}},{x,y}]

FindPolynomial[Table[3 (y^2)-3 z+x y z+2 (x^2) (y^3) z-x (z^3),{x,1,3},{y,1,4},{z,1,4}],{x,y,z}]

FindPolynomial[Table[3 (y^2)-3 z+x y z+2 (x^2) (y^3) z-x (z^3),{x,0,3},{y,0,4},{z,0,4}],{x,y,z},{0,0,0}]

The option IntermediateFunction can be used to simplify intermediate expressions:

?IntermediateFunction

AbsoluteTiming[FindPolynomial[{24 (-8+n) (-34650+4955 n-186 (n^2)+(n^3)),120 (-9+n) (-18480+2662 n-109 (n^2)+(n^3)),72 (-10+n) (-72072+10307 n-440 (n^2)+5 (n^3)),168 (-11+n) (-65520+9214 n-399 (n^2)+5 (n^3)),48 (-12+n) (-450450+61905 n-2674 (n^2)+35 (n^3)),432 (-20+n) (-13+n) (4620-387 n+7 (n^2)),720 (-14+n) (-97240+12629 n-528 (n^2)+7 (n^3)),528 (-15+n) (-222768+28048 n-1145 (n^2)+15 (n^3)),72 (-16+n) (-2645370+322631 n-12826 (n^2)+165 (n^3)),312 (-17+n) (-957600+113090 n-4371 (n^2)+55 (n^3)),168 (-18+n) (-2713200+310265 n-11648 (n^2)+143 (n^3)),360 (-19+n) (-1884960+208762 n-7609 (n^2)+91 (n^3)),96 (-20+n) (-10296594+1104829 n-39090 (n^2)+455 (n^3)),1632 (-21+n) (-865260+89991 n-3091 (n^2)+35 (n^3)),864 (-22+n) (-2294250+231405 n-7718 (n^2)+85 (n^3))},m,IntermediateFunction->Factor]]
ByteCount[%[[2]]]

Without intermediate simplification, the computation takes longer and uses more memory:

AbsoluteTiming[ByteCount[FindPolynomial[{24 (-8+n) (-34650+4955 n-186 (n^2)+(n^3)),120 (-9+n) (-18480+2662 n-109 (n^2)+(n^3)),72 (-10+n) (-72072+10307 n-440 (n^2)+5 (n^3)),168 (-11+n) (-65520+9214 n-399 (n^2)+5 (n^3)),48 (-12+n) (-450450+61905 n-2674 (n^2)+35 (n^3)),432 (-20+n) (-13+n) (4620-387 n+7 (n^2)),720 (-14+n) (-97240+12629 n-528 (n^2)+7 (n^3)),528 (-15+n) (-222768+28048 n-1145 (n^2)+15 (n^3)),72 (-16+n) (-2645370+322631 n-12826 (n^2)+165 (n^3)),312 (-17+n) (-957600+113090 n-4371 (n^2)+55 (n^3)),168 (-18+n) (-2713200+310265 n-11648 (n^2)+143 (n^3)),360 (-19+n) (-1884960+208762 n-7609 (n^2)+91 (n^3)),96 (-20+n) (-10296594+1104829 n-39090 (n^2)+455 (n^3)),1632 (-21+n) (-865260+89991 n-3091 (n^2)+35 (n^3)),864 (-22+n) (-2294250+231405 n-7718 (n^2)+85 (n^3))},m]]]

Interpolate a 2-dimensional sequence of symbolic polynomials in y and z:

polynomial=FromCoefficientList[RandomInteger[{-10,10},{2,3,4,5}],{w,x,y,z}];
AbsoluteTiming[FindPolynomial[Table[polynomial,{w,0,10},{x,0,10}],{w,x}]]
ByteCount[%[[2]]]

Without expanding intermediate steps in the variables y and z, the computation takes longer and uses more memory:

AbsoluteTiming[ByteCount[FindPolynomial[Table[polynomial,{w,0,10},{x,0,10}],{w,x},IntermediateFunction->None]]]

Clear[polynomial]

FindQuasiPolynomial

?FindQuasiPolynomial

s=FindQuasiPolynomial[{0,8,11,13,20,30,18,35,41,45,57,73,55,81,90,96,113,135,111,146,158,166,188,216,186,230,245,255,282,316,280,333,351,363,395},x,6]

Table[s,{x,35}]

Clear[s]

Begin indexing the list at 0:

s=FindQuasiPolynomial[{0,8,11,13,20,30,18,35,41,45,57,73,55,81,90,96,113,135,111,146,158,166,188,216,186,230,245,255,282,316,280,333,351,363,395},x,6,0]

Table[s,{x,0,34}]

Clear[s]

FindRegularSequenceFunction

?FindRegularSequenceFunction

s=FindRegularSequenceFunction[Table[DigitCount[n,2,1],{n,0,31}],2]

Table[s[n],{n,0,15}]

Clear[s]

RegularSequenceMatrixForm[FindRegularSequenceFunction[Table[Total[IntegerDigits[n,2]],{n,0,(2^5)-1}],2]]

RegularSequenceMatrixForm[FindRegularSequenceFunction[Nest[Function[matrix,ArrayFlatten[matrix/.{1->{{{1,0},{1,1}},{{1,1},{0,1}}},0->{{{0,1},{1,1}},{{1,1},{1,0}}}},3]],{{{1}}},5],2]]

The array of binomial coefficients modulo 6 is not (6,6)-regular:

FindRegularSequenceFunction[Table[Mod[Binomial[n,m],6],{n,0,(6^3)-1},{m,0,(6^3)-1}],6]//Short

FindRegularSequenceRecurrence

?FindRegularSequenceRecurrence

FindRegularSequenceRecurrence[Table[DigitCount[n,2,1],{n,0,31}],2,s[n]]

Find the 2-regular system of recurrences that defines a three-dimensional morphic sequence:

FindRegularSequenceRecurrence[Nest[Function[matrix,ArrayFlatten[matrix/. {1->{{{1,0},{1,1}},{{1,1},{0,1}}},0->{{{0,1},{1,1}},{{1,1},{1,0}}}},3]],{{{1}}},4],2,s[n1,n2,n3]]//Column

Specifying "Output"->Full gives a list where each equation only has two sides:

FindRegularSequenceRecurrence[Nest[Function[matrix,ArrayFlatten[matrix/. {1->{{{1,0},{1,1}},{{1,1},{0,1}}},0->{{{0,1},{1,1}},{{1,1},{1,0}}}},3]],{{{1}}},4],2,s[n1,n2,n3],"Output"->Full]//Column

FromCoefficientList

?FromCoefficientList

FromCoefficientList[{1,0,-10,0,1},x]

FromCoefficientList[IdentityMatrix[3],{x,y}]

FromCoefficientList provides an inverse to CoefficientList:

FromCoefficientList[{a,b,c,d},x]

CoefficientList[a+b x+c (x^2)+d (x^3),x]

FromDigitList (a variant and generalization of FromDigits)

?FromDigitList

DigitList[2179,-3]

FromDigitList[{1,0,2,1,0,0,0,2,1},-3]

DigitList[2179,"Factorial"]

FromDigitList[{1,0,3,0,0,3},"Factorial"]

Compute the number of seconds in 2 weeks, 1 day, 15 hours, 45 minutes, and 3 seconds:

FromDigitList[Reverse[{2,1,15,45,3}],{60,60,24,7}]

FromDigits evaluates by dropping information when a mixed radix has too few bases:

FromDigits[{8,1,0,0},MixedRadix[{2,3}]]
IntegerDigits[%,MixedRadix[{2,3}]]

FromDigitList does not drop information; it returns unevaluated instead:

FromDigitList[{0,0,1,8},{3,2}]

FromRecurrence

?FromRecurrence

Define CentralTrinomialCoefficient by its recurrence:

FromRecurrence[n CentralTrinomialCoefficient[n]==3 (n-1) CentralTrinomialCoefficient[n-2]+(2 n-1) CentralTrinomialCoefficient[n-1]&&CentralTrinomialCoefficient[0]==1&&CentralTrinomialCoefficient[1]==1,CentralTrinomialCoefficient[n]]

Now you can use it as a function:

CentralTrinomialCoefficient/@Range[0,10]

Each time CentralTrinomialCoefficient is used to compute a new value, it caches the new value and removes from the cache values that are not needed to compute higher-index values:

?CentralTrinomialCoefficient

Make sure to clear a symbol before attempting to redefine it; otherwise initial conditions in the input can evaluate to True or False and won’t be picked up:

FromRecurrence[n CentralTrinomialCoefficient[n]==3 (n-1) CentralTrinomialCoefficient[n-2]+(2 n-1) CentralTrinomialCoefficient[n-1]&&CentralTrinomialCoefficient[0]==1&&CentralTrinomialCoefficient[1]==1,CentralTrinomialCoefficient[n]]

Clear[CentralTrinomialCoefficient]
FromRecurrence[n CentralTrinomialCoefficient[n]==3 (n-1) CentralTrinomialCoefficient[n-2]+(2 n-1) CentralTrinomialCoefficient[n-1]&&CentralTrinomialCoefficient[0]==1&&CentralTrinomialCoefficient[1]==1,CentralTrinomialCoefficient[n]]

Clear[CentralTrinomialCoefficient]

Somos 4 sequence:

FromRecurrence[Somos[n]==((Somos[n-1] Somos[n-3]+((Somos[n-2])^2))/(Somos[n-4]))&&Somos[0]==Somos[1]==Somos[2]==Somos[3]==1,Somos[n]]

Somos/@Range[0,20]

Clear[Somos]

GeneratingFunctionRelations

?GeneratingFunctionRelations

Find an equation satisfied by the generating function for the Fibonacci sequence:

GeneratingFunctionRelations[u[n+2]==u[n+1]+u[n],u[n],f[x]]

Here is the generating function itself:

Solve[%,f[x]]/. {u[0]->0,u[1]->1}

Compute the first few terms of the series:

Series[f[x]/. %,{x,0,10}]

RSolve can't solve systems of a certain complexity, but GeneratingFunctionEquations can give equations satisfied by the generating function:

RSolve[c[0,0]==1&&c[p,0]==2 n c[p-1,1]&&c[p,l]==c[p-1,l-1]+(2 n-1) c[p-1,l+1],c[p,l],{p,l}]

Column[GeneratingFunctionRelations[c[0,0]==1&&c[p,0]==2 n c[p-1,1]&&c[p,l]==c[p-1,l-1]+(2 n-1) c[p-1,l+1],c[p,l],f[x,y]]]

IntegerPrepend

?IntegerPrepend

IntegerPrepend[27,10,{0}]

IntegerPrepend[8,2,{0}]

IntegerPrepend[8,"Fibonacci",{0}]

Digits increase in significance:

IntegerPrepend[16,2,{1,0,1,1}]
DigitList[%,2]

The representation obtained by prepending is not necessarily a canonical representation in the numeration system:

IntegerPrepend[1,"Fibonacci",{1}]
DigitList[%,"Fibonacci"]

IntegerPrepend evaluates for symbolic n in integer bases:

IntegerPrepend[n,2,{1,0}]

IntegerPrepend can be used to generate arithmetic sequences:

Table[IntegerPrepend[n,2,{1,0}],{n,0,10}]

JacobsthalNumber

?JacobsthalNumber

Table[JacobsthalNumber[n],{n,0,20}]

JacobsthalNumber[100]

JacobsthalNumber[1.5]

LaurentPolynomialCoefficientList (a generalization of CoefficientList)

?LaurentPolynomialCoefficientList

LaurentPolynomialCoefficientList[(3/(x^2))+(1/x)-2+x+(x^2),x]

LaurentPolynomialCoefficientList[(3/(x^2))+(1/x)-2+x+(x^2),x,{-1,5}]

A multivariate Laurent polynomial:

LaurentPolynomialCoefficientList[1+(1/x)+x+(1/(x y))+y+(y/x),{x,y}]

LaurentPolynomialCoefficientList[1+(1/x)+x+(1/(x y))+y+(y/x),{x,y},{{-2,2},{-2,2}}]

MorphismAdjacencyMatrix

?MorphismAdjacencyMatrix

The adjacency matrix counts occurrences of each letter in the image of each letter.

m=MorphismAdjacencyMatrix[{"a"->"ab","b"->"cc","c"->"ab"}]

Use Normal to convert a sparse array to a list of lists:

Normal[m]
%//MatrixForm

The transpose of the adjacency matrix is sometimes called the “incidence matrix” in the literature.

Transpose[m]//MatrixForm

If the letter frequencies in a fixed point of a morphism exist, then they are given by the entries of an eigenvector of the transpose of its adjacency matrix.  In particular, they are the entries of the eigenvector corresponding to the dominant eigenvalue, normalized so that the entries sum to 1:

Normalize[First[Eigenvectors[Transpose[m],1]],Total]

CharacterCounts[SubstitutionSystem[{"a"->"ab","b"->"cc","c"->"ab"},"a",{{20}}]]
N[((%)/(Total[%]))]

Clear[m]

Specify a different alphabet order:

MorphismAdjacencyMatrix[{"a"->"ab","b"->"cc","c"->"ab"},{"c","a","b"}]//MatrixForm

MorphismAdjacencyMatrix works on morphisms represented by lists:

MorphismAdjacencyMatrix[{0->{0,1},1->{2,2},2->{0,1}}]//MatrixForm

MorphismAdjacencyMatrix also works on higher-dimensional morphisms:

MorphismAdjacencyMatrix[{0->{{0,1},{2,1}},1->{{2,2},{0,2}},2->{{0,1},{1,1}}}]//MatrixForm

This morphism does not specify an image for the letter c:

MorphismAdjacencyMatrix[{a->{a,b,b},b->{a,b,c}}]//MatrixForm

Therefore c is not replaced by the morphism and is its own image.

MorphismPower

?MorphismPower

MorphismPower[{"a"->"ab","b"->"cd","c"->"ac","d"->"da"},3]

MorphismPower works on morphisms represented by lists:

MorphismPower[{0->{0,1},1->{2,2},2->{0,1}},3]

MorphismPower also works on higher-dimensional morphisms:

MorphismPower[{0->{{0,1},{2,1}},1->{{2,2},{0,2}},2->{{0,1},{1,1}}},2]

MotzkinNumber

?MotzkinNumber

Table[MotzkinNumber[n],{n,0,20}]

MotzkinNumber[100]

MotzkinNumber[1.5]

OEISWebLookup

?OEISWebLookup

Open a web browser to the search results page:

OEISWebLookup[CatalanNumber[Range[0,10]]]

Open the page for a sequence directly:

OEISWebLookup["A005259"]

OrePolynomial

?OrePolynomial

OrePolynomial[2(x^2)-3x+10,x,2]

OrePolynomial[(x^2) (y^2)+(x-1) y+1,{x,y},2]

OrePolynomial[(x^2) (y^2)+(x-1) y+1,{x,y},2,Modulus->2]

OrePolynomial[(x^2) (y^2)+(x-1) y+1,{x,y},5,Modulus->5]

Radical

?Radical

Radical[200]

Radical[Range[20]]

Computing the radical of a number requires computing its factorization, and for large numbers this can take time:

AbsoluteTiming[Radical[(2^229)-1]]

RegularSequence

?RegularSequence

RegularSequence[{1,0},{{{1,0},{0,1}},{{0,1},{-1,2}}},{0,1}]/@Range[0,31]

This two-dimensional regular sequence produces Pascal’s triangle modulo 2:

ArrayPlot[Table[RegularSequence[{1},{{{{1}},{{0}}},{{{1}},{{1}}}},{1}][n,m],{n,0,63},{m,0,63}]]

RegularSequenceGeneratorTable

?RegularSequenceGeneratorTable

FindRegularSequenceFunction[DigitCount[Range[0,31],2,1],2]

RegularSequenceGeneratorTable[%,31]

FindRegularSequenceFunction[Nest[Function[matrix,ArrayFlatten[matrix/.{1->{{{1,0},{1,1}},{{1,1},{0,1}}},0->{{{0,1},{1,1}},{{1,1},{1,0}}}},3]],{{{1}}},5],2]

RegularSequenceGeneratorTable[%,{6,5,4}-1]

Dimensions[%]

RegularSequenceMatrixForm

?RegularSequenceMatrixForm

FindRegularSequenceFunction[DigitCount[Range[0,31],2,1],2]

RegularSequenceMatrixForm[%]

RegularSequenceMatrixLength

?RegularSequenceMatrixLength

FindRegularSequenceFunction[DigitCount[Range[0,31],2,1],2]

RegularSequenceMatrixLength[%]

RegularSequenceRecurrence

?RegularSequenceRecurrence

FindRegularSequenceFunction[DigitCount[Range[0,31],2,1],2]

RegularSequenceRecurrence[%,s[n]]

FindRegularSequenceRecurrence gives the relations in terms of subsequences of the original rather than as generators of the k-kernel:

FindRegularSequenceRecurrence[DigitCount[Range[0,31],2,1],2,s[n]]

A 3-dimensional sequence:

FindRegularSequenceFunction[Nest[Function[matrix,ArrayFlatten[matrix/. {1->{{{1,0},{1,1}},{{1,1},{0,1}}},0->{{{0,1},{1,1}},{{1,1},{1,0}}}},3]],{{{1}}},5],2]

RegularSequenceRecurrence[%,s[l,m,n]]

RegularSequenceReduce

?RegularSequenceReduce

Rewrite built-in functions as regular sequences:

RegularSequenceReduce[ThueMorse[n],n]

RegularSequenceReduce[RudinShapiro[n],n]

RegularSequenceReduce[BitShiftRight[n],n]

RegularSequenceReduce[IntegerLength[n],n]

RegularSequenceReduce[IntegerExponent[n+1,5],n]

Sum and product of regular sequences:

RegularSequenceReduce[RegularSequence[{1,0},{(({{1, 1}, {0, -2}})),(({{2, 0}, {-1, -1}}))},{1,0}][n]+RegularSequence[{-1,0},{(({{0, 1}, {2, -1}})),(({{2, 0}, {2, -1}}))},{1,1}][n],n]//RegularSequenceMatrixForm

RegularSequenceReduce[RegularSequence[{1,0},{(({{1, 1}, {0, -2}})),(({{2, 0}, {-1, -1}}))},{1,0}][n]*RegularSequence[{-1,0},{(({{0, 1}, {2, -1}})),(({{2, 0}, {2, -1}}))},{1,1}][n],n]//RegularSequenceMatrixForm

The Stern–Brocot sequence is 2-regular:

RegularSequenceReduce[SternBrocot[n],n]

Rewrite automatic sequences as regular sequences:

RegularSequenceReduce[BaumSweet[n],n]

RegularSequenceReduce[AutomaticSequence[Automaton[{{1->1,0},{1->2,1},{2->2,0},{2->1,1}},1,{1->0,2->1}]][n],n]

RegularSequenceReduce[AutomaticSequence[Automaton[{{1->1,0},{1->2,1},{2->2,0},{2->1,1}},1,{1->0,2->1}],2][n],n]

SequenceRiffle

?SequenceRiffle

s=SequenceRiffle[{n,(n^2),(n^3)},n]

Table[s,{n,30}]

Flatten[Table[{n,(n^2),(n^3)},{n,10}]]

Transpose[Partition[%,3]]

Clear[s]

SeriesRoot

?SeriesRoot

SeriesRoot objects define algebraic sequences:

AlgebraicSequence[SeriesRoot[{Function[\[FormalY],\[FormalX] (\[FormalY]^2)-\[FormalY]+1],1+\[FormalX]+2 (\[FormalX]^2)+((O[\[FormalX]])^3)}]][10]

Table[AlgebraicSequence[SeriesRoot[{Function[\[FormalY],\[FormalX] (\[FormalY]^2)-\[FormalY]+1],1+\[FormalX]+2 (\[FormalX]^2)+((O[\[FormalX]])^3)}]][n],{n,0,10}]

SeriesSolve

?SeriesSolve

SeriesSolve[(1-x)f[x]==1,f[x],{x,2,10}]

An irreducible polynomial of degree d has d distinct Puiseux series roots:

SeriesSolve[(x^2)+x f[x]+((f[x])^3)==0,f[x],{x,0,5}]

SeriesSolve[f[x]==1+x f[x]+(x^2) ((f[x])^2)+(x^3) ((f[x])^3),f[x],{x,0,5}]

SeriesSolve takes a Modulus option:

SeriesSolve[(x^2)+x f[x]+((f[x])^2)+((f[x])^3)==0,f[x],{x,0,10},Modulus->7]

SeriesSolve may produce results for small orders when in fact no series solutions exist:

SeriesSolve[(x-2)f[x]+2==0,f[x],{x,0,0},Modulus->4]

SeriesSolve[(x-2)f[x]+2==0,f[x],{x,0,10},Modulus->4]

One of the solutions here is not a Puiseux series but a Hahn series:

SeriesSolve[(x^6)+(1+(x^6)) ((f[x])^2)+(1+(x^4)+(x^8)+(x^12)) ((f[x])^7)==0,f[x],{x,0,17},Modulus->2]

Requesting more terms causes SeriesSolve to enter an infinite loop, since there are infinitely many terms with exponent less than 18:

TimeConstrained[SeriesSolve[(x^6)+(1+(x^6)) ((f[x])^2)+(1+(x^4)+(x^8)+(x^12)) ((f[x])^7)==0,f[x],{x,0,18},Modulus->2],5]

Specify a MaxDenominator to restrict the exponents in solutions:

SeriesSolve[(x^6)+(1+(x^6)) ((f[x])^2)+(1+(x^4)+(x^8)+(x^12)) ((f[x])^7)==0,f[x],{x,0,18},MaxDenominator->1,Modulus->2]

SeriesSolve does not repeat solutions according to their multiplicity:

SeriesSolve[((f[x])^3)==0,f[x],{x,0,10}]

SeriesSolve issues messages when PossibleZeroQ cannot determine whether numeric quantities are equal to zero:

SeriesSolve[f[x]==1+x f[x]+(x^2) ((f[x])^2)+(x^3) ((f[x])^3),f[x],{x,2,3}]

Specify Method->"ExactAlgebraics" to use exact methods for explicit algebraic numbers:

SeriesSolve[f[x]==1+x f[x]+(x^2) ((f[x])^2)+(x^3) ((f[x])^3),f[x],{x,2,3},Method->"ExactAlgebraics"]

SternBrocot

?SternBrocot

Table[SternBrocot[n],{n,0,31}]

ListPlot[SternBrocot[Range[0,127]]]

Write SternBrocot as a regular sequence:

RegularSequenceReduce[SternBrocot[n],n]

Column[FindRegularSequenceRecurrence[SternBrocot[Range[0,(2^10)]],2,s[n]]]

Tribonacci

?Tribonacci

Table[Tribonacci[n],{n,0,10}]

The Fibonacci numbers are the lengths of certain words generated by this morphism on two letters:

Table[StringLength[Nest[StringReplace[#,{"a"->"ab","b"->"a"}]&,"a",n]],{n,0,12}]

The Tribonacci numbers are the lengths of the corresponding words for this morphism:

Table[StringLength[Nest[StringReplace[#,{"a"->"ab","b"->"ac","c"->"a"}]&,"a",n]],{n,0,12}]