/* Math Pattern Hunter README : documentation for the Math Pattern Hunter; * Author: Maxie D. Schmidt (created 10/26/2006, last modified 12/20/2006) */ [README Contents]: (*) Liscencing and Copyright (*) Current Version (*) Program Overview (*) Installation (*) Usage and Runtime Options (*) Misc (*) Known Bugs (*) Feature Requests; Bug Reports; Feedback; Contact Info [Liscencing and Copyright]: The code for the Math Pattern Hunter is GPLed. The author of the program retains copyright: (C) Maxie D. Schmidt 2006 (maxieds(AT)gmail(DOT)com). The source code can be found on sourceforge (http://pattern-hunter.sf.net). Any copy, re-distribution, or modification of the code must be distributed with an un-altered form of this README. [Current Version]: 0.4.3-beta (see CHANGELOG) [Program Overview]: The Math Pattern Hunter program is designed to find formulas for integer and rational sequences. The program is designed to be used on the commandline (see Runtime Options below) and so prints the findings of the program in text. The program takes an integer or rational sequence and a set of functions and transformations and brute forces every combination of the functions (every combination being defined by options at runtime) with a set of function templates to try to find a formula for the sequence. [Installation]: The following instructions have been tested on OpenBSD 3.9 and 4.0, and Gentoo Linux 2006.1, and should work for any modern flavor of Linux or Unix. $ tar xvzf /path/to/patternhunter-.tar.gz $ cd patternhunter- $ [*] see note on debugging $ make $ su # make install [* Note On Debugging] : If you do not want the progress counters counters on the experimental matching function templates then comment out a line in "patternhunter.h": "#define DEBUGGING" => "//#define DEBUGGING". [Usage and Runtime Options]: The program usage is as follows: $ pattern_hunter {1,2,3,4,...} [options] The first argument to pattern_hunter is the sequence. Note that there should be no spaces between the commas in the sequence. The first argument should be expanded by whatever shell being used. It will definitely work for bash, ksh, and probably others. If for some reason the expansion in the braces doesn't work on your shell of choice, type the sequence with spaces between terms: $ pattern_hunter 1 2 3 4 ... [options] Math Pattern Hunter is designed to be run on the commandline. Due to this the program configuration can be fully specified at runtime. This allows the user to tweak the matching functions searched for and lets the user balance their own run of the program between features used (or disabled) and the runtime of the program. The program currently supports the following options that can be specified at runtime. Program Configuration Options: (*) [--depth d] : the depth (number) of fn_terms (see input patterns below) used in the function templates (*) [--start-index i] : the start index to use as input to functions when searching for patterns. (*) [--end-index i] : the ending index of variable input to functions when searching for a pattern. (*) [--allow-lower-bounds] : enables when searching for matching functions functions that are with in a range (set by "--lower-bound-range" or "--bounds-range") indicating an lower bound of the actual sequence value these functions are also printed. (*) [--lower-bound-range r|n/d] : set the range that a potential matching function value must be within as a lower bound. This setting is relevant when the "--allow-lower-bounds" option is set. The value can be specified as an integer or as a fraction "n/d" (internally in the program this value is stored as a fraction). (*) [--allow-upper-bounds] : enables when searching for matching functions functions that are with in a range (set by "--upper-bound-range" or "--bounds-range") indicating an upper bound of the actual sequence value these functions are also printed. (*) [--upper-bound-range r|n/d] : set the range that a potential matching function value must be within as an upper bound. This setting is relevant when the "--allow-upper-bounds" option is set. The value can be specified as an integer or as a fraction "n/d" (internally in the program this value is stored as a fraction). (*) [--allow-approx] : consider matching functions where the function values are within some range of the input sequence (not necessarily a strictly upper or lower bound). The range relevant for this option can be set with "--approx-range". The value for use with the range option may either be an integer or a fraction (form: n/d with no spaces). (*) [--approx-range r|n/d] : set the range for use when considering approximate functions. This value can also be set with "--bounds-range". For either of these options the value can be given as an integer or as a fraction (n/d with no spaces). (*) [--bounds-range r|n/d] : sets the range value for both lower and upper bounds, and for an approx function (not necessarily a strictly upper or lower bound, but bounded within some range of the input sequence). Alternately the values can be set individually with the "--lower-bound-range", "--upper-bound-range", and "--approx-range" options. The value can be specified as an integer or as a fraction "n/d" (internally in the program this value is stored as a fraction). (*) [--max-num-vars n] : the maximum number of variables that can be used in formulas (the limit for this is 26). Note that as the number of variables increases, the runtime of the program increases. (*) [--calc-style-vars] : use variables that are commonly used in infinite calculus first (as in x,y,z,w,t) instead of the variables commonly used with integer sequences (as in n,j,i). Note that the variable name 'k' is not used in formulas (I reserved it for printing function names). (*) [--config-file file] : specify the config file to use. There is an example config file at "/usr/share/math_pattern_hunter/config.test". Most commandline options can be set from the file (this includes most of the config vars in patternhunter.h). (*) [--output-file file] : save the matching functions the matching functions to "file". Note that status messages and error messages are not saved to file (these messages get printed to stdout). (*) [--fnterm-input-patterns file] : specify the file where input patterns for fn_terms are stored. Note that this setting can be overridden by the "--all-terms-*" options. (*) [--fnterm-input-patterns-only] : only use the input patterns for fn_terms specified with "--fnterm-input-patterns-file". (*) [--sum-term-input-patterns file] : specify the file where input patterns for sum_terms are stored. Note that this setting can be overridden by the "--all-terms-*" options. (*) [--sum-term-input-patterns-only] : only use the input patterns for sum_terms specified with the "--sum-term-input-patterns-file" option. (*) [--all-terms-input-patterns file] : specify the file where input patterns for fn_terms, sum_terms, and mult_terms are stored. If the function template types are enabled (elsewhere with another option) this setting will yield patterns for all of the types. This setting will override the settings from "--fnterm-input-patterns-file", "--sum-term-input-patterns-file", and "--mult-term-input-patterns-file". (*) [--all-terms-input-patterns-only] : only use the input patterns for fn_terms, sum_terms, and mult_terms (only when these function template types are enabled elsewhere) when searching for matching functions. (*) [--nocolor] : do not print output in color (color printing is done using escape codes so it may be desirable to omit the colors if the terminal doesn't recognize the codes or for saving output to file). Note that `pattern_hunter [...] | less -r` will display the colors as long as the terminal supports them. (*) [--combos-chunk-size n] : sets the number of combinations to use at a time for the function templates. If the box this is run on has low memory modify this to a lower setting. Otherwise, read the source code to figure out how best to tweak this fro your setup ("fntemplates.cpp", function "print_matching_fns()"). (*) [--fts-cache-size n] : sets the cache size for the function template called fn_term_sum. The default has this setting at 2 * COMBOS_CHUNK_SIZE. Read the source code to figure out how best to modify this setting for your setup ("fntemplates.cpp", function "print_matching_fns()"). (*) [--ftm-cache-size n] : sets the object cache size for the function template called fterm_multiply. The default setting leaves this at 2 * COMBOS_CHUNK_SIZE. Read the source code ("fntemplates.cpp", function "print_matching_fns()") to figure out how best to tweak this option for your setup. (*) [--ftms-cache-size n] : sets the cache size for the function template called ft_mult_sum. Currently there are no higher-level objects that will use this cache, but this is left in the code for future expansion. The default setting leaves this option at "1". Setting it to a higher value at this point in time is a waste of memory. (*) [--ftsm-cache-size n] : sets the cache size for the function template called fts_multiply. Currenty there are no higher-level objects that will use this cache, but it is left in the code for future expansion. The default setting leaves this at "1". At this point in time setting this option to a higher value is a waste of memory. (*) [--ftsms-cache-size n] : sets the cache size for the function template called fts_mult_sum. Currenty there are no higher-level objects that will use this cache, but it is left in the code for future expansion. The default setting leaves this at "1". At this point in time setting this option to a higher value is a waste of memory. (*) [--sum-term-cache-size n] : sets the cache size for the function template called sum_term. (*) [--sum-term-sum-cache-size n] : sets the cache size for the function template called sum_term_sum. Currenty there are no higher-level objects that will use this cache, but it is left in the code for future expansion. The default setting leaves this at "1". At this point in time setting this option to a higher value is a waste of memory. (*) [--use-console-progress-bar] : this option enables the console progress bar. The console progress bar will display progress bars indicating the current point of the program in evaluating the different types. The progress bar displayed uses functions that may not work on every setup (most Linux terminals should work ...). Additionally since the display is used for the progress bar, the output for matching functions will be written to file. If no file is specified with the "--output-file" option a date stamped file will be used in the current working directory. (*) [--print-summary] : this option enables printing a summary of the program run. The "--verbose" option will enable printing more detailed output. Examples of what is in the summary: the number of functions (the actual functions list with "--verbose"), variables used, the number of terms of each type processed, etc. (*) [--verbose] : enables more detailed output. Currently this setting is only relevant when the option "--print-summary" (see above) is used. Input Functions Options: (*) [--fn {1,2,3,4,...} --fn-name name] : this allows the user to specify a function at runtime (currently only in one dimension). (*) [--usefns-base {filenums}] : specify the file numbers of (OEIS) functions to be used when searching for patterns (see files/base*.txt). (*) [--usefns-core {filenums}] : specify the file numbers of (OEIS) functions to be used when searching for patterns (see files/core*.txt). (*) [--usefns-counting {filenums}] : specify the file numbers of (OEIS) functions to be used when searching for patterns (see files/counting*.txt). (*) [--usefns-graphs-trees {filenums}] : specify the file numbers of (OEIS) functions to be used when searching for patterns (see files/graphstrees*.txt). (*) [--usefns-misc {filenums}] : specify the file numbers of (OEIS) functions to be used when searching for patterns (see files/misc*.txt). (*) [--usefns-primes-base {filenums}] : specify the file numbers of (OEIS) functions to be used when searching for patterns (see files/primesbase*.txt). (*) [--usefns-primes-extra {filenums}] : specify the file numbers of (OEIS) functions to be used when searching for patterns (see files/primesextra*.txt). (*) [--usefns-number-theory {filenums}] : specify the file numbers of (OEIS) functiond to be used when searching for patterns (see files/numbertheory*.txt). (*) [--usefns-recurrences {filenums}] : specify the file numbers of (OEIS) functions to use when searching for patterns (see files/recurrence*.txt). (*) [--usefns-trig {filenums}] : specify the file numbers of (OEIS) functions to use when searching for patterns (see files/trig*.txt). (*) [--usefns-user-input {filenames}] : specify the file names of input files created by the user to be used when searching for patterns. Note that the files input be the user must match the formatting used by other files (see files/{base,core,counting,graphstrees,misc, primesbase,primesextra,numbertheory,recurrence,trig}*.txt). Form Function Options: (*) [--use-fnform-constants] : add constant functions to the functions used when filling in the matching function templates. The range for these functions are given in the next two options. The exceptions (even when in range) are 0 and -1. The exceptions will not be covered by the constant functions. (*) [--constant-start-range n] : set the lower bound on the interval for constant functions. The values 0 and -1 are automatically excluded from the interval. (*) [--constant-end-range n] : set the upper bound on the interval for constant functions. The values 0 and -1 are automatically excluded from the interval. (*) [--poly-degree-start d] : start degree of polynomials used as functions (see note on form functions below). Note that if the start degree used is >= 1, then constant functions will not be used when searching for formulas. (*) [--poly-degree-end d] : end degree of polynomials used as functions (see note in --poly-degree-start and on form functions below). (*) [--poly-coeff-start n] : the start of coefficients used in polynomial functions (see note below about form functions). (*) [--poly-coeff-end n] : the end of the interval used for coefficients when using polynomial functions in formula searches (see note on form functions below). (*) [--use-fnform-poly] : use the function form of polynomials. The properties of the function form can be set using the above four commandline options. (*) [--r-coeff-start n] : 1-dimensional recurrence coefficient start of interval (see note on form functions below). (*) [--r-coeff-end n] : 1-dimensional recurrence coefficient end of interval (see note on form functions below). (*) [--r-1dim-depth d] : the depth of the recurrence. For example if depth = 2 there will be at most a difference of 2 in the terms, as in f(n) = k1 * f(n - 1) + k2 * f(n - 2). (Someone e-mail me the math term for this depth). See the note on form functions below. (*) [--r-init-val-start n] : the start of initial values for a 1-dimensional recurrence used as a function when searching for formulas. See the note on form functions below. (*) [--r-init-val-end n] : the end of the initial values range when using the 1-dimensional form function(s). See the note on form functions below. (*) [--use-fnform-1dim-recurrence] : use the form function for a 1-dim recurrence. See the note about form functions below and the five previous options. (*) [--ppoly-even-coeff-start n] : the start range of the even coefficient in the polynomial pattern for the function form prime polys. This value must be >= 2. (*) [--ppoly-even-coeff-end n] : the end of the range for the even coefficient in the polynomial pattern for the form function prime polys. This value must be >= 2. (*) [--ppoly-odd-coeff-start n] : the start of the range for the odd coefficient in the form function for prime polys. (*) [--ppoly-odd-coeff-end n] : the end of the range for the odd coefficient in the form function for prime polys. (*) [--use-fnform-ppoly] : use the form function for prime polys. Given an even and an odd coeff a ppoly function returns the nth prime of the form ((even_coeff) * k + (odd_coeff)). See the note about form functions below and the four previous options. (*) [--2dr-alpha-start n] : the start of the interval for the parameter alpha in the function form for 2-dimensional recurrences. (*) [--2dr-alpha-end n] : the end of the interval for the parameter alpha in the form function for 2-dimensional recurrences. (*) [--2dr-beta-start n] : the start of the interval for the beta parameter in the form function for 2-dimensional recurrences. (*) [--2dr-beta-end n] : the end of the interval for the beta parameter in the form function for 2-dimensional recurrences. (*) [--2dr-gamma-start n] : the start of the interval for the gamma parameter in the form function for 2-dimensional recurrences. (*) [--2dr-gamma-end n] : the end of the interval for the gamma parameter in the form function for 2-dimensional recurrences. (*) [--2dr-alpha-prime-start n] : the start of the interval for the alpha prime parameter in the form function for 2-dimensional recurrences. (*) [--2dr-alpha-prime-end n] : the end of the interval for the alpha prime parameter in the form function for 2-dimensional recurrences. (*) [--2dr-beta-prime-start n] : the start of the interval for the beta prime parameter in the form function for 2-dimensional recurrences. (*) [--2dr-beta-prime-end n] : the end of the interval for the beta prime parameter in the form function for 2-dimensional recurrences. (*) [--2dr-gamma-prime-start n] : the start of the interval for the gamma prime parameter in the form function for 2-dimensional recurrences. (*) [--2dr-gamma-prime-end n] : the end of the interval for the gamma prime parameter in the form function for 2-dimensional recurrences. (*) [--2dr-init-val-start n] : the start of the interval for the initial value in the form function for 2-dimensional recurrences. (*) [--2dr-init-val-end n] : the end of the interval for the initial value in the form function for 2-dimensional recurrences (*) [--use-fnform-2dr] : use the form function for 2-dimensional recurrences. This recurrence / form function has seven parameters: alpha, beta, gamma, alpha', beta', gamma' and the initial value. These parameters correspond to the recurrence: y(n, k) = (an+bk+g)y(n-1, k)+(a'n+b'k+g')y(n-1,k-1). (*) [--2dr-special-cases] : use functions corresponding to the special cases of the 2d recurrence y(n, k) = (an+bk+g)y(n-1, k)+ (a'n+b'k+g')y(n-1,k-1). Some of the notable special cases for this recurrence are (a, b, g, a', b', g', init_val = 1) : Stirling numbers of the first kind (1, 0, -1, 0, 0, 1), Stirling numbers of the second kind (0, 1, 0, 0, 0, 1), Eulerian numbers (0, 1, 1, 1, -1, 0), "second-order Eulerian numbers" (0, 1, 1, 2, -1, -1), and binomial coefficients (0, 0, 1, 0, 0, 1). Function Transforms Options: (*) [--useft-fn-mod-fn] : use the function transform that take two functions (including the --usefns-* fns) and returns f1 (mod f2). (*) [--useft-2convolution] : use the function transform that returns the convolution (SUM(k = 0 to k = n of f1(k) * f2(n - k))) of the two sequences / functions. (*) [--useft-sum-prev] : use the function transform that returns the sum of f1 values <= n where the indices are the output of a second function f2. (*) [--ft-fnpoly-num-fns-start n] : the start of the range for the number of functions to use in the fnpoly transform. (*) [--ft-fnpoly-num-fns-end n] : the end of the range for the number of functions to use in the fnpoly transform. (*) [--ft-fnpoly-coeff-start n] : the start of the range for the coeffs to use in the fnpoly transform. Note that the program automatically removes zero from the range to keep duplication of functions to a minimum. (*) [--ft-fnpoly-coeff-end n] : the end to the range for the coeffs to use in the fnpoly transform. The zero value is automatically discarded. (*) [--useft-fnpolys] : use the fnpoly transform. The transform takes in a number of functions (the range for this number can be set with the --ft-fn-poly-num-fns-* options; the minimum number of functions to use is two since using one would duplicate other functions used in the program) and makes polynomials of functions (the coeff range involved can be set using the --ft-fnpoly-coeff-* options). For example, given two functions, f1 and f2, and a coeff range of [-1, 1] (omitting zero) one poly is -f1 - f2, another is f1 - f2, and so on. The functions resulting from using this transform are all combinations of numbers of functions and coeffs given by the ranges set. (*) [--ft-compose-num-fns-start n] : the start range of the number of functions to use with the composition transform. This value must be >= 2 to avoid duplication of functions. (*) [--ft-compose-num-fns-end n] : the end of the range of the number of functions to use with the composition transform. This value must be >= 2. (*) [--useft-compose-fns] : use the composition transform. This transform takes a number of functions (range specified by the --ft-compose-num-fns-* options) and takes the composition of them. For example, given three functions, f1, f2, and f3, the transform produces a function with values of f1(f2(f3(n))). (*) [--useft-reverse-digits] : use the reverse digits transform. This transform takes a function and reverses the digits of its values. (*) [--useft-count-digits] : use the count digits transform. This transform takes a function and returns the number of digits in its values. (*) [--useft-cycle-digits] : use the cycle digits transform. This transform takes a function and cycles the digits of its values. For example given a value 1234, cycling the digits one time yields 4123, two times yields 3412, and so on. (*) [--useft-digital-roots] : use the function transform for digital roots. Enabling this option generates functions that compute the digital root of other functions. Function Templates / Types Options: (*) [--use-fnterm-sums] : use sums of fn_terms as potential matching functions. See also the "--useft-fnpoly" option. (*) [--fnterm-sum-max-depth d] : specify the maximum number of fn_terms to sum for fn_term_sums. This option is only relevant if the "--use-fnterm-sums" option is set (see above). (*) [--use-fnterm-mult] : use the form (function template) of fn_terms multiplied together. (*) [--fnterm-mult-max-depth d] : set the depth for fnterm_mults. This value is the maximum number of terms multiplied together. The "--use-fnterm-mult" option must be set for this value to have any effect. The value must be >= 2 (if the value were 1 fn_terms would be duplicated). (*) [--use-fnterm-linear-combos] : use the function type / template of fn_term_lc when searching for matching functions (see below for a description of this type). (*) [--fnterm-lc-max-depth n] : set the maximum (minimum: 2) number of fn_terms in each fn_term_lc. (*) [--fnterm-lc-coeff-start n] : set the minimum value of coeffs to use in fn_term_lcs. (*) [--fnterm-lc-coeff-end n] : set the maximum value of coeffs to use in fn_term_lcs. (*) [--fnterm-lc-print-lc] : this option sets the print style when printing matching fn_term_lcs. If set the fn_term_lcs will be printed in the style of a linear combination with the leading coeffs before each of the the fn_terms. Otherwise (default value) the fn_terms will be printed with the linear combination coeffs combined in with the fn_terms. /////// Note that the the following options are experimental as of version 0.3-beta /////// (*) [--use-fts-mults] : use the form of fn_term_sums multiplied together when searching for function matches. Setting this option will also enable fn_term_sums. (*) [--fts-mult-max-depth d] : set the maximum number of terms that can be multiplied together. This value must be >= 2 to avoid duplication with fn_term_sums. (*) [--use-ftsms] : use the function template / type of fts_mult_sum (see below for an explanation of this type) when searching for matching functions. Enabling this option will also enable fn_term_sums and fts_multiplys. (*) [--ftsms-max-depth n] : sets the maximum (minimum: 2) number of fts_multiplys used in any given fts_mult_sum. (*) [--use-sum-terms] : use the function template / type of sum_term (see below for an explanation of this type) when searching for matching functions. Enabling this option will also enable fn_term_sums. (*) [--sum-term-max-depth n] : sets the maximum number of non-NULL nodes attached to a given start sum_term (minimum: 2 to avoid duplication with fn_terms_sums). (*) [--use-sum-term-sums] : use the function template / type of sum_term_sum (see below for an explanation of this type) when searching for matching functions. Enabling this option will also enable sum_terms and fn_term_sums. (*) [--sum-term-sum-max-depth n] : sets the maximum (minimum: 2) number of sum_terms in any given sum_term_sum. /////// end experimental options The README (this README) is intended to give a brief overview of the program, and mainly handle administrative issues such as installation and licsening. This document is also intended to give a comprehensive listing of all of the commandline options available for the program at runtime. The other main source of documentation for the program is at the Example Usage site (http://pattern-hunter.sf.net/example_usage.php). The example usage document is intended to cover the concepts used in the program (types, variations on functions, etc.) and give examples of the usage and configuration of the program. See the example usage page for definitions and usage of the terms / concepts function templates / types, variables, form functions, function transforms, input patterns, and more. [Misc]: (0) Utilities The Math Pattern Hunter site has a utilities program page for programs that relate to the Pattern Hunter. The site is: http://pattern-hunter.sourceforge.net/utils.php. Currently there are programs for download that allow the user to download the OEIS database, search it for user-defined interesting sequences, and then format the chosen sequences for use with the Pattern Hunter. (1) Places to look for more sequences to try with the program: (*) The On-line Encyclopedia of Integer Sequences (http://www.research.att.com/~njas/sequences/) (*) The Concrete Math Book (full title Concrete Mathematics : A Foundation for Computer Science) by Graham, Knuth, and Patashnik (*) Schaums Outline on Calculus of Finite Differences and Difference Equations by Speigel (2) Variations on the Print Function: fn() fn() / fn() ----------- fn()^ fn() / fn() ---- fn()^ / / fn() fn()^ / -------------------------------- fn()^ fn() fn() / ---- fn()^ / fn() fn() / ---- fn()^ fn() When the program checks for a function match to the input sequence, the formula gets simplified down to fractions. The simplify functions are useful to prevent printing messy duplicates, but the print function is actually capable of much more. The print function is capable of displaying fractions on fractions (and fractions over fractions, ...). The output may not be useful for finding formulas, but it does produce some cool-looking text graphics. If interested take a look at test_print.cpp ($ make test_print) for some examples. There are also some examples of the print function's capabilities on the program site: http://pattern-hunter.sf.net/example_formulae.php. [Known Bugs]: (1): [Note this bug should be mostly fixed starting with version 0.3-beta, however it is still possible to hit this bug if there a a large numbers of functions, variables, and forms (so it is left in the README)] At times when there are a large number of functions, a large "--depth" option, or anything that creates large numbers of function templates to check, the program may sefault. This is due to the way the fill functions for the templates operate. Instead of hard-coding for loops to fill in the functions a recursive method is used to generate all possible combinations of functions and variables (for fn_terms) or all combinations of input fn_terms (for the fn_term_sum and fterm_multiply templates). When the number of combinations grows too large the function will crash out and give a segfault (abort). [Feature Requests; Bug Reports; Feedback; Contact Info]: If there are any desirable features that have been left out of the latest release of the Math Pattern Hunter send me an e-mail (maxieds(AT)gmail(DOT)com) with a decent description of the new feature. If the features are reasonable and time permits I will add the new features to a future release of the program. There is also a TODO.txt file distributed with the source, so one might try looking there to see what features are in line to be added. If there are any bugs in the program send me an e-mail with a detailed description of the problem _AND_ how to reproduce the bug and I will do my best to fix it. If any user finds an interesting formula from running the program I would like to hear about it and post it on the sf website (I will give you credit for discovering the formula). If there is anything missing from this document or parts of it that need correction let me know via e-mail. Additionally, if there are any function transformations that I have not included in the latest version of the code I would like to hear about them. Enjoy the program and code. Happy Penguin / Pufferfish.