[seqfan] Re: Purely algorithmic number sequence identification

[Olivier Gerard]

Dear Philipp Emmanuel,

your program Sequencer is really interesting. In spirit, one can say it is
close to
Robert Munafo's RIES

http://mrob.com/pub/ries/index.html

but for integer sequences

It would be nice to test it on "hard" sequences and other sequences without
formula.

I have a first candidate (which is inspired by the same kind of brute force
exploration)

https://oeis.org/A229673

"The number of subsets of nonzero integers of cardinality n, produced as
the steps in a computation starting with 1 and using the operations of
multiplication, addition, or subtraction."

1, 3, 15, 126, 1667, 31966, 828678, 27535826, 1128945382, ...

Best regards,

Olivier


On Sun, Feb 22, 2015 at 10:29 PM, Philipp Emanuel Weidmann <
pew at worldwidemann.com> wrote:

> I have been experimenting with a purely algorithmic (brute force)
> approach to the question "which formula generates this number
> sequence?", designed to complement existing systems based on database
> lookups (OEIS) and pattern transforms (Mathematica).
>
>
Mathematica has pattern transforms as part of its language but its sequence
formula recognition commands are based on mathematical theories :

 - holonomic functions, linear algebra, z-transforms, difference equations,
continuous fractions, pade approximants, ...



> The system developed for that purpose is now available, both as a
> library/executable JAR (https://github.com/p-e-w/sequencer) and as a
> simple (beta stage) web service (http://www.sequenceboss.org/).
>
> At its core, Sequencer is a tree-based expression generator plus a
> hybrid search engine combining a fast numerical pre-checker with a
> symbolic verifier. Because the numerical checker is so fast, expressions
> of relatively high complexity (7-8 nodes) can be exhaustively searched
> in minutes on commodity hardware to check whether they generate the
> given numbers.
>
> Despite its early stage of development, Sequencer can already identify
> (i.e. find a closed form expression for) many sequences that OEIS,
> Superseeker and Mathematica can not. It is particularly strong at
> finding complex, nonlinear or inhomogeneous recurrence relations like
>
>   a(1) = 1
>   a(2) = 1
>   a(3) = 1
>   a(n) = a(n-2)^2+a(n-1)+a(n-3)   for n >= 4
>
> when provided the sequence
>
>   1, 1, 1, 3, 5, 15, 43, 273
>
> something which none of the above mentioned systems is currently able to
> do. But the system can also quickly find unusual, relatively simple
> general terms for sequences like
>
>   11, 47, 123, 214, 257
>
> for which Sequencer returns
>
>   a(n) = n + Binomial(10,n)
>
> in less than one second (http://www.sequenceboss.org/?q=11%2C+47%2C+123%
> 2C+214%2C+257).
>
> By leveraging the Symja computer algebra system, Sequencer supports
> fully symbolic input and output and is not limited to integer sequences.
> For example, running the program on the input
>
>   0, 1/2, sqrt(3)/2, 1
>
> produces (search depth 6) the formula
>
>   a(n) = Sin(1/6*Pi*(n-1))
>
>
> I invite you to give the Sequencer/SequenceBoss system a try. If you are
> familiar with Scala, you will find it easy to modify the
> FormulaGenerator class to expand the range of expressions that can be
> searched beyond what the command line switches already offer. Next in
> line I plan to add multicore support based on Scala Actors which should
> almost multiply the current search performance by the number of
> available CPU cores as the search is efficiently parallelizable. Bug
> reports and code contributions are very welcome, ideally on GitHub.
>
> Best regards
>
> Philipp Emanuel Weidmann
>