The purpose of this document is to provide information on the concepts of the program, give examples of use of the program, and to detail how to configure Math Pattern Hunter. The other important source of information about the program is the README. The README details all of the commandline options available for use with the program, as well as administrative tasks such as installation. This document is organized as follows:

- Introduction to Math Pattern Hunter
- General Configuration Options
- Function Templates / Types
- Variables
- Functions
- Form Functions
- Function Transforms
- Input Patterns
- Advanced Features

Math Pattern Hunter is a program designed to find formulas (or possibly upper and lower bounds to formulas) for an input one-dimensional rational sequence. In order to do this the program takes function templates (types) filled in with every combination of functions and variables and attempts to find matching functions by brute-force. The types, functions, and variables used depend on the options specified at runtime.

The input sequence can be specified as either all integers or
all fractions (with no spaces within the curly brackets).
Note that piping the output to `less -r`

allows
for scrolling through the output with colors.

```
$ pattern_hunter {1,2,3,4} | less -r
```

or

```
$ pattern_hunter {1/2,2/3,3/4,4/5} | less -r
```

If the user's terminal does not expand the curly braces the input sequence can be typed with spaces between each term:

```
$ pattern_hunter 1 3 5 7 | less -r
```

Most shells will do the expansion correctly. This has been
tested with recent versions of `bash`

and `ksh`

(this covers modern versions of Linux, OpenBSD, and OSX).

There are several general configuration options that can be specified at runtime. What follows is basically a listing of some of the more useful options.

Most of the options available at runtime can be alternately specified by the use of a config file. The config file can also be used to give values to properties that cannot be set on the commandline. For example, it is possible to change the default colors used for syntax highlighting from within the config file. To specify the config file use the following:

```
$ pattern_hunter {1,4,9,16} --config-file cfg_file.txt
```

An example config file is provided with the Math Pattern Hunter
source (see `/usr/share/math_pattern_hunter/config.test`

after running a `make install`

, or alternately
`files/config.test`

from within the source tree).

Next, the program uses colors for syntax highlighting in the
output. The colors are implemented using (ANSI) escape sequences.
If for some reason the user's terminal does not support the
colors, the colors can be disabled by use of the
`--nocolor`

option. Note that if the program
output including colors are saved to file the command

```
$ less -r save_file.txt
```

can be used to view the file with color highlighting.

Since the program is designed for use on the commandline, the output of program runs can be easily redirected to file most of the time. At times it is useful to have the program automatically save output to file. This can be done by specifying the output filename when the program run begins:

```
$ pattern_hunter {1,1,2,3,5} --output-file output_file.txt
```

To view a summary of the Pattern Hunter run the option
"`--print-summary`

" can be used. To view more
detailed summary output, including a complete functions list,
this option can be coupled with the "`--verbose`

"
option:

```
$ pattern_hunter {5,4,3,2,1} --print-summary --verbose
```

The last general option that is extremely useful, or at least
informative, allows for seeing the progress of the program
in realtime. When this option is enabled the display is used
for viewing progress bars. Due to this, it is necessary to
save any program output to file instead of printing to
`stdout`

. The default filename can be overridden with
the `--output-file`

option. The progress bar
functionality can be enabled by

```
$ pattern_hunter {1,2,1,4} --use-console-progress-bar --output-file output.txt
```

This feature will work only if the user's terminal supports
functions for colors (though this can be disabled by the
`--nocolor`

option), clearing the screen, and
moving the cursor. The option should be compatible with
practically every Linux machine out of the box. It's worth
an attempt since it shows the position in evaluation in some
potentially long runs of Math Pattern Hunter.

The console /
terminal functions were used for this to keep the program
source free of external libraries, such as ncurses. If this
method does not work try defining "DEBUGGING" in the source
file `patternhunter.h`

to get some indication of
progress.

There are several function templates (types) that when enabled in the program get filled in with all combinations of functions and variables in order to find matching functions. These types are described in a separate, related document that is organized as follows:

Variables in Math Pattern Hunter are used in a predictable way. The variables used in the program are unique in that when filling in all combinations of functions each variable is considered a separate case to check when attempting to brute-force a solution. The following paragraphs show how to adjust the ranges for variables, how to specify the number of variables used when filling in types, and some odd options to tweak cosmetic properties of variables when printed.

The number of variables as potential input to functions can be changed (to a maximum of 26 variables) at runtime. Note that the more variables used, the slower the program will run. Example:

```
$ pattern_hunter {1,2,3,4} --depth 3 --max-num-vars 4
```

The range of values for each variable can be specified with the
`--start-index`

and `--end-index`

options. The range of variable values can be any integer
interval, though some care should be taken in selecting the
variable ranges since runtimes with large ranges will be
a limiting factor.

Depending on the nature of the sequence input to Math Pattern
Hunter, the display names of the variables can be tweaked
with the option `--calc-style-vars`

. If this option
is given at runtime, the variables displayed will have the form
of calc vars (as in `x`

, `y`

,
`z`

, `t`

vs. the int-style variables
`n`

, `j`

, etc.).

The program searchs for matching functions for the input
sequence, but the actual "matching functions" are types based
on `fn_term`

s that are filled in with functions and
variables at each node. The treatment of the node-filling
functions in the Pattern Hunter is discussed in this section.

There are some basic functions hard-coded into the code (such as
`-1`

, `k`

, `2k`

, and
`2k+1`

), but most of the functions that will be used
are loaded dynamically at runtime. There are a couple of reasons
for this. First, dynamic loading of functions at runtime
allows for selectively including only the desired functions,
or categories of functions, when program runtime is a
consideration. Second, the On-line Encyclopedia of Integer
Sequences (OEIS)
has a wealth of information about integer sequences. Instead
of hard-coding all of the functions into the program, select
sequences from the OEIS database can be dynamically loaded from
file at runtime. The sequence numbers are displayed
when a formula match occurs, so the user can look up the
sequence(s) at that site and find detailed information about it.
[Note: the Utils section of this site
contains utility programs to help download, search, and format
the OEIS database for use with Math Pattern Hunter].

There are several categories of functions grouped from the OEIS
database that are built into the program. Use of these functions
can be enables with the `--usefns-*`

options. The
category-separated files (and file numbers) can be viewed at
`/usr/share/math_pattern_hunter`

after a `make install`

,
or alternately in the `files/`

directory in the
source distribution. For example:

```
$ pattern_hunter {2,3,5,8} --depth 3 --usefns-recurrences 0 1
```

It is also possible to load custom OEIS functions at runtime:

```
$ pattern_hunter {3/4,5/8,35/64,63/128} --depth 1 --usefns-user-input file0.txt [...] filen.txt
```

The format for the custom files must be the same as the files provided with Math Pattern Hunter. (See the Utils section of this site for utilities to download the OEIS database, search it, and format the sequences for use with Math Pattern Hunter).

`{1,1,2,3,5,8}`

over some interval greater than or equal to the size of
the sequence terms. This input can be specified as follows:
```
$ pattern_hunter {1,2,3,5,8} --depth 1 --fn {1,1,2,3,5,8} --fn-name fib
```

Note that the function name argument is mandatory if using the
"`--fn`

" option.

There is a quirk to the structure of a subset of the functions that can be used with the program. A set of functions that are generated given property values supplied at runtime (such as coefficient ranges and depth of terms) can be enabled by enabling the "form function" and setting the properties related to a specific form function.

An example form function used in Math Pattern Hunter is the use of constant functions. In this case, instead of having to enable each constant function (one for const_val=2, another for const_val=3, ...), the user need only enable the form function and set the related properties. Then all constant functions with values within the range specified are included as functions in the program.

Another example of a form function is that of polynomial
functions. Suppose the coefficient interval is [-1, 1] and
the polynomial degree is in the interval [0, 2]. When the
polynomial form function is enabled with the option
`--use-fnform-poly`

the following polynomial
functions are used in the program:

```
1, 0, -1, x + 1, x, x - 1, -x + 1, -x, -x -1, ..., x^2 + x + 1, ...
```

The form functions included with the program are the constant
functions, polynomials, one-dimensional recurrences,
two-dimensional recurrences, and prime polys (ppolys). These
form functions are diabled by default for performance
reasons, so enabling them requires use of the options
`--use-fnform-*`

at runtime. The remainder of the
section details some concrete examples of the use of form
functions.

For now consider the polynomial form function. The polynomial form function
generates functions that have values of a polynomial with a degree (`d`

) and
coefficients in some range of integers.
The relevant runtime options are: "`--poly-degree-start`

,
"`--poly-degree-end`

", "`--poly-coeff-start`

",
"`--poly-coeff-end`

", and "`--use-fnform-poly`

".
Try running:

```
$ pattern_hunter {-1,0,3,8} --depth 2 --start-index 0 --end-index 4
--poly-degree-start 1 --poly-degree-end 2 --poly-coeff-start -1
--poly-coeff-end 1 --use-fnform-poly
```

The output from this command should include the polynomial for ```
x^2
- 1
```

over the interval `[0, 3]`

.

The following command starts a run of Math Pattern Hunter where constants in the range [3, 8] are used as functions:

```
$ pattern_hunter {3/8,3/8,3/8,3/8} --use-fnform-constants --constant-start-range 3 --constant-end-range 8
```

Next consider the form function for one-dimensional recurrences.
An example of this form is the recurrence `y(k) = 2y(k - 1) + y(k - 2)`

.
This form
function generates functions that are one-dimensional recurrences with some
depth (degree), coefficients in some range of integers, and with an initial
value. The relevant options are "`--r-1dim-depth`

",
"`--r-coeff-start`

", "`--r-coeff-end`

",
"`--r-init-val-start`

", and "`--r-init-val-end`

".
Consider the following example:

```
$ pattern_hunter {1,2,3,5,8} --depth 1 --r-coeff-start 0 --r-coeff-depth 1
--r-1dim-depth 2 --r-init-val-start 0 --r-init-val-end 1
```

Next, consider the two-dimensional recurrence form function. This form function
generates functions that have the form `y(n, k) = (a*n + b*k + g)y(n - 1, k) + (a’*n + b’*k +g’)y(n - 1, k - 1)`

,
where a = alpha, b = beta, and g = gamma.
The relevant options are the
"`--2dr-*`

for the coefficient ranges and for the initial value
range. An example of this form function with default values follows:

```
$ pattern_hunter {24,50,35,10,1} --depth 1 --use-fnform-2dr
```

When interpretting intervals for a 2D function to create a 1D function the program holds one variable constant and lets the other variable range over an interval. The previous example showed a row of the triangle for Stirling numbers of the first kind (the first variable held constant). Observe that a column of values can also be used:

```
$ pattern_hunter {3,11,50,274} --depth 1 --use-fnform-2dr
```

There is a related option that works well when only the (well-known) special cases of this recurrence are desired:

```
$ pattern_hunter {1,4,6,4,1} --2dr-special-cases
```

The special cases include Stirling numbers of both kinds, Eulerian numbers of both orders, binomial coefficients, and an interesting appearance of a double factorial.

Finally, consider the prime poly (ppoly) form function. This form function
generates functions that give the kth prime of the form
` (even_coeff) * n + (odd_coeff)`

where even_coeff and odd_coeff
are in some ranges of integers. The relevant commandline options are the
"`--ppoly-*`

" options. Take a glance at the next example:

```
$ pattern_hunter {5,13,17,29,37,41,53} --use-fnform-ppoly
--ppoly-even-coeff-start 4 --ppoly-even-coeff-end 4 --ppoly-odd-coeff-start 1
--ppoly-odd-coeff-end 1
```

The output should show the prime poly for `4k + 1`

.

Function transforms are functions that take functions, such as the default
functions `-1`

, `k`

, `2k`

, and
`2k+1`

, as input and produce functions that are transoforms of the
input functions. These transforms can be enabled using the
"`--useft-*`

" options at runtime. For example, the count digits
transform takes a function and counts the number of digits in the value of that
function at the relevant variable value:

```
$ pattern_hunter {1,1,2,2,2} --depth 1 --start-index 0 --end-index 10
--useft-count-digits
```

Next, consider using the function transform for composition of functions:

```
$ pattern_hunter {6,14,22,30} --useft-compose-fns --ft-compose-num-fns-start 3
--ft-compose-num-fns-end 3
```

In this case "`--useft-compose-fns`

" enables the transformation and
the options "`--ft-compose-num-fns-*`

set the interval for the
number of functions composed.

The function transform for polynomials of functions is also interesting. This function transform generates polynomials of functions. Consider the following:

```
$ pattern_hunter {1,11,21,31} --depth 1 --ft-fnpoly-num-fns-start 3
--ft-fnpoly-num-fns-end 3 --ft-fnpoly-coeff-start 1 --ft-fnpoly-coeff-end 3
--useft-fnpoly
```

The output should show several variations of the input sequence.

The
"`--useft-*`

" options can be used to specify function transforms
that are not described in this document. A complete listing of
the `--useft-*`

options can be found in the
README, or alternately by running
Pattern Hunter with the `--help`

for a list without
descriptions.

In a usual run of the program all combinations of variables and functions are
run through a set of function templates to check for matching functions. The
form of the templates are determined by the "`--depth`

" option. To
speed up the calculations, or if only a certain type of function form is
needed, it is possible to specify input patterns from file at runtime.
Options to load input patterns at runtime are only available when
the function template being used has the same (similar)
structure as `fn_term`

s. Currently only
`fn_term`

s and
sum_terms have
these options. An example of a working input patterns file
can be found at `/usr/share/math_pattern_hunter/input_patterns.test`

after a `make install`

, or in the `files/`

directory in the source code. Note that due to simplifications
run on matching functions, the output functions may differ in
form from the input patterns given.

To load input patterns for the `fn_term`

s
use

```
$ pattern_hunter {1/3,1/5,1/7,1/9} --fnterm-input-patterns file
--fnterm-input-patterns-only
```

and to load input patterns for use with `sum_term`

s use

```
$ pattern_hunter {1/2,1/4,1/6,1/8} --sum-term-input-patterns file
--sum-term-input-patterns-only
```

The "`--*-only`

" options are optional. If given the
only patterns used for the relevant type are those in the
filename specified.

It is possible to specify input patterns for all types that support the given forms as well:

```
$ pattern_hunter {1,3,5,7,9} --all-terms-input-patterns file
--all-terms-input-patterns-only
```

If these options are given the options override the options
given for a single type. In that case, the patterns in the file
given by the "`--all-terms-*`

" are the only patterns
used. Also, if the "`--all-terms-input-patterns-only`

"
is used the usual (default) forms used for each type will be
skipped.

This section details runtime options that should only be used if the user is comfortable with the syntax of the program, and in about half of these options if the user understands relevant sections of the Math Pattern Hunter source code.

The first set of (so called) advanced options relate to the interpretation of a matching function. A default run of the program only checks for functions that are an exact match to the input sequence. In many cases it is desirable to not only check exact matches, but also to determine if there are any functions that are lower or upper bounds to the input sequence, and also whether there are matching functions where all function values are within some range of the input sequence values (as opposed to strictly lower or upper bounded functions).

To enable lower, upper, and approximate (not necessarily strictly lower or upper) bounds functions as acceptable matching functions use:

```
$ pattern_hunter {1,1,2,5,14} --allow-lower-bounds --lower-bound-range 1
--allow-upper-bounds --upper-bound-range 1/2
--allow-approx --approx-range 2/3
```

The "`--*-range`

" options are technically optional
and set how close of a bound, or approximation, matching
functions must be. These values can be given either as an
integer or as a fraction (`num/denom`

with no spaces).
Instead of setting each value explicitly the option
"`--bounds-range`

" can be used to set all three
ranges. As with the individual options the range value can
be given in integer or fractional form.

Next, there are commandline options available that allow for tweaking the way that the program operates. Adjusting these settings for optimal performance depends on the user's setup and will most likely require knowledge of the Math Pattern Hunter source and its structure. If the user is not comfortable reading through the source code it is probably better to leave these options at thier default values.

There are a set of function templates that can be used to search for matching functions (use of these function templates is described in the sections above). Within the source code these templates are built off of one another with each instance as an object. Starting at Math Pattern Hunter version 0.4-beta the program dynamically creates the objects as needed with a buffer (cache) layer to keep from having to load the same objects multiple times within a short period of time.

The file / function of interest in the source code is the
file "`fntemplates.cpp`

" and the function "`print_matching_fns()`

".
In order to keep the memory usage of the program at a reasonable
amount, combinations of the objects are loaded at a specified
size. The option to tweak this value is
"`--combos-chunk-size`

":

```
$ pattern_hunter {1,2,3,4} --combos-chunk-size 1000
```

The next options allow the user to define initial cache
sizes at runtime. These options each take a single argument
of an integer value. The options are as follows:
"`--fts-cache-size`

", "`--ftm-cache-size`

",
"`--ftms-cache-size`

", and "`--ftsm-cache-size`

".
The following abbreviations are used: fts (`fn_term_sum`

s),
ftm (`fterm_multiply`

s), ftms (`ft_mult_sum`

s), and ftsm (`fts_multiply`

).
Since multiple objects build off one another (starting with
`fn_term`

s), there will be layers of caches. It follows that a
"higher-level" cache should have a larger size than a "lower-level"
cache.

Currently (version 0.4-beta) this distinction in cache sizes is not a problem, but in future releases with more function templates this will be an issue in tuning performance of the program.