XGC - Mathematica Basics

Syntax

Here is a simple function written in Mathematica. It is useful to show the syntax of the language.
In this sample, the blue color represents predefined symbols of Mathematica, while the red one predefined functions.

IsEquallySpaced[ {} ] := True IsEquallySpaced[ set_List ] := Length[ Union[ Drop[ -set, -1 ] + Drop[ set, 1 ] ] ] == 1: square brackets enclose a list of parameters or arguments

a parameter is a name that ends with an underscore sign

here is a print of the execution trace of IsEquallySpaced[ {3, 10, 17} ]
<a href="xgc_traceprint.txt">IsEquallySpaced[ {3, 10, 17} ]</a>

Conditions

Here are all the conditions that the arguments of the Mathematica functions used in the rest of this document have to satisfy to be applied.

IsInteger[ arg ]

IsInteger[ n_ ] := IntegerQ[ n ]  /; Not[ ListQ[ n ] ]
IsInteger[ set_List ] := Apply[ And, Map[ IntegerQ, Flatten[ set ] ] ]

It yields True if either arg is integer or arg is a set of numbers with such a property.
It yields False otherwise.

IsNatural[ arg ]

IsNatural[ n_ ] := IntegerQ[ n ] && Positive[ n ]  /; Not[ ListQ[ n ] ]
IsNatural[ set_List ] := Apply[ And, Map[ IsNatural, Flatten[ set ] ] ]

It yields True if either arg is natural or arg is a set of numbers with such a property.
It yields False otherwise.

IsNaturalZ[ arg ]

IsNaturalZ[ n_ ] := IntegerQ[ n ] && NonNegative[ n ]  /; Not[ ListQ[ n ] ]
IsNaturalZ[ set_List ] := Apply[ And, Map[ IsNaturalZ, Flatten[ set ] ] ]

It yields True if either arg is natural or zero or arg is a set of numbers with such a property.
It yields False otherwise.

IsCongruent[ arg, c, m ]

IsCongruent[ n_, c_Integer, m_Integer ] := IntegerQ[ n ] && IsNaturalZ[ c ] && IsNatural[ m ] && c < m \
  && Mod[ n, m ] == c  /; Not[ ListQ[ n ] ]
IsCongruent[ set_List, c_Integer, m_Integer ] := IsNaturalZ[ c ] && IsNatural[ m ] && c < m \
  && IsSetEQ[ Mod[ Flatten[ set ], m ], c ]

It yields True if either arg is congruent to class c to modulus m or arg is a set of numbers with such a property.
It yields False otherwise.

IsCoprime[ c, m ]

IsCoprime[ c_Integer, m_Integer ] := GCD[ c, m ] == 1 /; IsNatural[ {c, m} ]

It yields True if GCD[ c, m ] == 1.
It yields False otherwise.

IsEquallySpaced[ set ]

IsEquallySpaced[ {} ] := True
IsEquallySpaced[ set_List ] := Length[ Union[ Drop[ -set, -1 ] + Drop[ set, 1 ] ] ] == 1

It yields True if each term of the set is equally spaced from its adjacents.
It yields False otherwise.

IsSetLT[ set, arg ]

IsSetLT[ set_List, n_ ] := Apply[ And, Map[ (# < n)&, Flatten[ set ] ] ]  /; Not[ ListQ[ n ] ]
IsSetLT[ set1_List, set2_List ] := 
  Module[ {s1 = Flatten[ set1 ], s2 = Flatten[ set2 ]},
    Apply[ And, Table[ s1[[ i ]] < s2[[ i ]], {i, Length[ s1 ]} ] ]
  ] /; Length[ Flatten[ set1 ] ] == Length[ Flatten[ set2 ] ]

IsSetLT[ set_List, n_Integer ] yields True if each number of the set is Less Than n.
It yields False otherwise.
IsSetLT[ set1_List, set2_List ] yields True if each number of the set1 is Less Than the number in the same position in the set2.
It yields False otherwise.

IsSetLE[ set, arg ]

IsSetLE[ set_List, n_ ] := Apply[ And, Map[ (# <= n)&, Flatten[ set ] ] ]  /; Not[ ListQ[ n ] ]
IsSetLE[ set1_List, set2_List ] := 
  Module[ {s1 = Flatten[ set1 ], s2 = Flatten[ set2 ]},
    Apply[ And, Table[ s1[[ i ]] <= s2[[ i ]], {i, Length[ s1 ]} ] ]
  ] /; Length[ Flatten[ set1 ] ] == Length[ Flatten[ set2 ] ]

IsSetLE[ set_List, n_Integer ] yields True if each number of the set is Less than or Equal to n.
It yields False otherwise.
IsSetLE[ set1_List, set2_List ] yields True if each number of the set1 is Less than or Equal to the number in the same position in the set2.
It yields False otherwise.

IsSetEQ[ set, arg ]

IsSetEQ[ set_List, n_ ] := set == Table[ n, {Length[ set ]} ]  /; Not[ ListQ[ n ] ]
IsSetEQ[ set1_List, set2_List ] := set1 == set2 /; Length[ Flatten[ set1 ] ] == Length[ Flatten[ set2 ] ]

IsSetEQ[ set_List, n_Integer ] yields True if each number of the set is EQual to n.
It yields False otherwise.
IsSetEQ[ set1_List, set2_List ] yields True if each number of the set1 is EQual to the number in the same position in the set2.
It yields False otherwise.

IsSetGE[ set, arg ]

IsSetGE[ set_List, n_ ] := Apply[ And, Map[ (# >= n)&, Flatten[ set ] ] ]  /; Not[ ListQ[ n ] ]
IsSetGE[ set1_List, set2_List ] :=
  Module[ {s1 = Flatten[ set1 ], s2 = Flatten[ set2 ]},
    Apply[ And, Table[ s1[[ i ]] >= s2[[ i ]], {i, Length[ s1 ]} ] ]
  ] /; Length[ Flatten[ set1 ] ] == Length[ Flatten[ set2 ] ]

IsSetGE[ set_List, n_Integer ] yields True if each number of the set is Greater than or Equal to n.
It yields False otherwise.
IsSetGE[ set1_List, set2_List ] yields True if each number of the set1 is Greater than or Equal to the number in the same position in the set2.
It yields False otherwise.

IsSetGT[ set, arg ]

IsSetGT[ set_List, n_ ] := Apply[ And, Map[ (# > n)&, Flatten[ set ] ] ]  /; Not[ ListQ[ n ] ]
IsSetGT[ set1_List, set2_List ] :=
  Module[ {s1 = Flatten[ set1 ], s2 = Flatten[ set2 ]},
    Apply[ And, Table[ s1[[ i ]] > s2[[ i ]], {i, Length[ s1 ]} ] ]
  ] /; Length[ Flatten[ set1 ] ] == Length[ Flatten[ set2 ] ]

IsSetGT[ set_List, n_Integer ] yields True if each number of the set is Greater Than n.
It yields False otherwise.
IsSetGT[ set1_List, set2_List ] yields True if each number of the set1 is Greater Than the number in the same position in the set2.
It yields False otherwise.

IsSetLT2[ set, {set1, set2, ...} ]

IsSetLT2[ set1_List, set2_List ] := Apply[ Or, Map[ (IsSetLT[ set1, # ])&, set2 ] ]

It yields True if it does exist at least one setK such that IsSetLT[ set, setK ].
It yields False otherwise.

IsSetLE2[ set, {set1, set2, ...} ]

IsSetLE2[ set1_List, set2_List ] := Apply[ Or, Map[ (IsSetLE[ set1, # ])&, set2 ] ]

It yields True if it does exist at least one setK such that IsSetLE[ set, setK ].
It yields False otherwise.

IsSetEQ2[ set, {set1, set2, ...} ]

IsSetEQ2[ set1_List, set2_List ] := Apply[ Or, Map[ (set1 == # )&, set2 ] ]

It yields True if it does exist at least one setK such that IsSetEQ[ set, setK ].
It yields False otherwise.

IsSetGE2[ set, {set1, set2, ...} ]

IsSetGE2[ set1_List, set2_List ] := Apply[ Or, Map[ (IsSetGE[ set1, # ])&, set2 ] ]

It yields True if it does exist at least one setK such that IsSetGE[ set, setK ].
It yields False otherwise.

IsSetGT2[ set, {set1, set2, ...} ]

IsSetGT2[ set1_List, set2_List ] := Apply[ Or, Map[ (IsSetGT[ set1, # ])&, set2 ] ]

It yields True if it does exist at least one setK such that IsSetGT[ set, setK ].
It yields False otherwise.

Sequence Algebra

Here are all the sequence algebra functions we'll need for studying XGC. Note that z is the variable used in polynomial sequence formulas.

Normalize[ poly ]

Normalize[ poly_ ] := 
  Module[ {poly2},
    If[ First[ Exponent[ poly, z, List ] ] == 0,
      poly2 = Prepend[ Rest[ poly ], 1 ]
    , poly2 = poly
    ];
    poly2 /. coeff_ z_ -> z
  ]  /; PolynomialQ[ poly, z ]

It sets to 1 all the coefficients of z in the polynomial.

SetToPoly[ set ]

SetToPoly[ set_List ] := Apply[ Plus, z^set ] /; IsInteger[ set ]

It converts the set to a polynomial in z.

PolyToSet[ poly ]

PolyToSet[ poly_ ] := Exponent[ poly, z, List ] /; PolynomialQ[ poly, z ]

It converts the polynomial in z to a set.

Binary Search

Here is the classical algorithm used to find a key in a sorted set. Look at the element in the middle of the set. Does it match the key? If yes, you got it, else if the key lies before/after that element, search in the lower/higher half in the same way. Due to its half concept, the algorithm is known as binary search. The following function implements that algorithm, while the next one implements a little variation.
When the first function does not find the key in the set it returns a failure, symbolized by the 0 (zero), while the second one never fails, i.e. in that case it returns the index of the element less than the key, being the successive element of the set greater than the key.

BinSearchEQ[ key, set ]

  Module[ {bottomIndex = 1, middleIndex, topIndex = Length[ set ], middleItem},
    While[ topIndex >= bottomIndex, 
      middleIndex = Floor[ (bottomIndex + topIndex) / 2 ];
      middleItem = set[[ middleIndex ]];
      If[ middleItem == key,
        Return[ middleIndex ]
      , If[ middleItem > key,
          topIndex = middleIndex - 1
        , bottomIndex = middleIndex + 1
        ]
      ]
    ];
    0
  ] /; OrderedQ[ set ]

It gives the index i such that set[[ i ]] == key if such an index exists, otherwise it gives 0."

BinSearchLE[ key, set ]

pBinSearchLE[ key_Integer, set_List ] :=
  Module[ {bottomIndex = 1, middleIndex, topIndex = Length[ set ], term, index},
    While[ topIndex >= bottomIndex, 
      middleIndex = Floor[ (bottomIndex + topIndex) / 2 ];
      term = set[[ middleIndex ]];
      If[ term == key,
        index = middleIndex;
        Break[]
      , If[ term > key,
          index = middleIndex - 1; 
          topIndex = middleIndex - 1
        , index = middleIndex; 
          bottomIndex = middleIndex + 1
        ]
      ]
    ];
    index  (* set[[ index ]] <= key, set[[ index + 1 ]] > key *)
  ]

BinSearchLE[ key_Integer, set_List ] := pBinSearchLE[ key, set ]  /; OrderedQ[ set ]

It gives the index i such that set[[ i ]] <= key and set[[ i + 1 ]] > key.