[seqfan] Re: Purely algorithmic number sequence identification
olivier.gerard at gmail.com
Mon Feb 23 11:42:45 CET 2015
Dear Philipp Emmanuel,
your program Sequencer is really interesting. In spirit, one can say it is
Robert Munafo's RIES
but for integer sequences
It would be nice to test it on "hard" sequences and other sequences without
I have a first candidate (which is inspired by the same kind of brute force
"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, ...
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%
> 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
More information about the SeqFan