[seqfan] Purely algorithmic number sequence identification

[Philipp Emanuel Weidmann]

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

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