[Math Pattern Hunter]: Example Usage

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_terms 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).

It is possible to specify a user defined function(s) on the command line at runtime. For example, suppose the user needs a function that has values {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_terms. Currently only fn_terms 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_terms 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_terms 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_sums), ftm (fterm_multiplys), ftms (ft_mult_sums), and ftsm (fts_multiply). Since multiple objects build off one another (starting with fn_terms), 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.