# MathToolkit

A Julia package providing various functions mainly for the purpose of experimental mathematics (detecting recurrence relations, finding integer relations, etc.).

## Usage

Implemented functions are:

`recvec`

for finding coefficients of a recurrence relation for a sequence of rational terms;`pslq`

for finding an integer relation between several floating-point values.

`recvec`

for detecting a recurrence relation

Using Argument should be a vector containing several `Integer`

or `Rational`

numbers. The general rule should be to use at least twice as many terms in the argument sequence as the expected length of the resulting vector.

```
julia> recvec([1,2,3,4,5,6,7,8,9,10])
3-element Array{Int64,1}:
1
-2
1
julia> recvec([0,1,1,2,3,5,8,13])
3-element Array{Int64,1}:
1
-1
-1
```

Resulting vector is normalized with all coefficients being integer numbers and the leading coefficient being positive:

```
julia> recvec([2^k for k=0:7])
2-element Array{Int64,1}:
1
-2
julia> recvec([1//2^k for k=0:7])
2-element Array{Int64,1}:
2
-1
```

#### Checking the result

The following example is a long sequence with a more complicated recurrence relation (of higher order); a check is performed on the last numbers of the sequences (here 16 numbers are involved):

```
a = [k^2-2*k^3+5*k-1+k%12 for k=0:64]
b = recvec(a)
transpose(a[length(a)-length(b)+1:length(a)])*b
```

(the final product is 0 meaning the recurrence is right).

#### Result when no recurrence relation is found

An empty vector is returned when no recurrence relation is found:

```
julia> recvec([[k for k=1:16];[42]])
0-element Array{Int64,1}
```

#### Changing the type used in the computation

The `compute`

keyword allows to change the integer type used in the computation; default type is `BigInt`

in order to keep the function very general as its default behaviour. Most often it is possible however to use a quicker type in order to increase the speed of the computation:

```
julia> recvec([2*k^2-3*k+7 for k=0:7], compute=Int128)
4-element Array{Int64,1}:
1
-3
3
-1
```

#### Changing the type of the resulting vector

The `output`

keyword allows to choose the integer type used in the returned value of the function; default type is `Int64`

. Many other types may be used according to the needs of the user:

```
julia> recvec([3^k-2 for k=0:15], compute=Int128, output=Float64)
3-element Array{Float64,1}:
1.0
-4.0
3.0
```

#### Algorithm

The algorithm is a very robust and optimized version of the Padé approximants method. Quicker algorithms can be found for long sequences, but this version is very efficient for most cases. It has a very low memory footprint, even when large sequences are computed.

`pslq`

for detecting integer relations

Using Two arguments are required: a vector containing several floating-point values (the type `BigFloat`

should be the type of the variables) and a precision as a floating-point value:

```
julia> z=[BigFloat(pi)*2-BigFloat(e)/3-5, BigFloat(pi), BigFloat(e), 1]
4-element Array{BigFloat,1}:
3.770913643599047318051909427747849358085897675168917836275666420409406024545445e-01
3.141592653589793238462643383279502884197169399375105820974944592307816406286198
2.718281828459045235360287471352662497757247093699959574966967627724076630353555
1.000000000000000000000000000000000000000000000000000000000000000000000000000000
julia> pslq(z,1e-10)
4-element Array{Integer,1}:
-3
6
-1
-15
julia> transpose(z)*pslq(z,1e-10)
1-element Array{BigFloat,1}:
1.381786968815111140061816298048063931378560058309805021603792555226974688505988e-76
```

The algorithm has a well-known usage for detecting if a number is algebraic or not:

```
julia> x=sin(pi/BigFloat(3))
8.660254037844386467637231707529361834714026269051903140279034897259665084543988e-01
julia> pslq([1,x,x^2],1e-20)
3-element Array{Integer,1}:
-3
0
4
```

An optional `maxiter`

argument (default being 256) allows to change the maximum number of iterations in the main loop of the algorithm.