[seqfan] Experimental mathematics in Python: a generator for "interesting" sequences

[Thomas Baruchel]

Dear fellow seqfans,

as some of you may remember it, I like to search for crazy identities by making
veyr heavy uses of computational resources.

Very often I need to build on the fly random continued fractions, power series,
etc. and very often I falled back to parsing the stripped.gz version of the
OEIS for feeding my various experimental algorithms.

Some other times, I decided that too many sequences from the OEIS would be of
very little interest for my own needs (sequences related to decimal or binary
radices, sequences related to lexicographic topics, etc.) and I tried to
generate on the fly random sequences relying on polynomial materials.

But I decided to go one step further, and I finally wrote a generator of
sequences (length may be any power of 2 like 32 or 64) that would generate many
sequences that should follow the requirements:

   * sequences should be interesting from an arithmetical point of view, and if
     one is detected to be interesting, finding an elegant formula for it should
     be very easy (in fact such a sequence could probably be found in the OEIS);
   * sequences should not be of a single type (periodical, repeating patterns,
     polynomial, number theory, etc.).

I decided to iterate over all finite patterns of growing sizes and growing
positive coefficients and to compute the "Euler transform" of such patterns;
the result is exactly as expected: iterating on such sequences yield very
regular (but more and more complicated) sequences; first of them are in the
OEIS; types of sequences are quickly changing; etc.

Of course, computing the "Euler Transform" is rather a heavy task, but I copied
in my script an older previously released module in which I implemented a
function for precompiling power series operations (convolution, reciprocal) by
using the Karatsuba algorithm.

Furthermore, anything that is computed is stored in some internal cache; thus
the computation should not get too slow when patterns get more and more
complicated.

You could try it (Python 3 only) with a very simple loop:

   for seq in sequences():
       print(seq)

in order to see which sequences occur (see below the 64 initial sequences).

The whole script is a standalone tool with no external requirements; it works
also with the very fast Pypy interpreter:

     https://gitlab.com/baruchel/sequences


When precompiling the iterator for size=16, the 64 initial sequences are:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8]
[1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0]
[1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1]
[1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6]
[1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 3, 3]
[1, 0, 0, 2, 0, 0, 3, 0, 0, 4, 0, 0, 5, 0, 0, 6]
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136]
[1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72]
[1, 1, 3, 3, 6, 6, 10, 10, 15, 15, 21, 21, 28, 28, 36, 36]
[1, 0, 3, 0, 6, 0, 10, 0, 15, 0, 21, 0, 28, 0, 36, 0]
[1, 2, 3, 5, 7, 9, 12, 15, 18, 22, 26, 30, 35, 40, 45, 51]
[1, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27]
[1, 0, 2, 1, 3, 2, 5, 3, 7, 5, 9, 7, 12, 9, 15, 12]
[1, 1, 1, 3, 3, 3, 6, 6, 6, 10, 10, 10, 15, 15, 15, 21]
[1, 0, 1, 2, 1, 2, 4, 2, 4, 6, 4, 6, 9, 6, 9, 12]
[1, 0, 0, 3, 0, 0, 6, 0, 0, 10, 0, 0, 15, 0, 0, 21]
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]
[1, 0, 1, 0, 2, 0, 2, 0, 3, 0, 3, 0, 4, 0, 4, 0]
[1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2]
[1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0]
[1, 2, 3, 4, 6, 8, 10, 12, 15, 18, 21, 24, 28, 32, 36, 40]
[1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 12, 12, 16, 16, 20, 20]
[1, 0, 2, 0, 4, 0, 6, 0, 9, 0, 12, 0, 16, 0, 20, 0]
[1, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 15]
[1, 0, 1, 1, 2, 1, 3, 2, 4, 3, 5, 4, 7, 5, 8, 7]
[1, 0, 0, 2, 1, 0, 3, 2, 1, 4, 3, 2, 6, 4, 3, 8]
[1, 1, 1, 1, 3, 3, 3, 3, 6, 6, 6, 6, 10, 10, 10, 10]
[1, 0, 1, 0, 3, 0, 3, 0, 6, 0, 6, 0, 10, 0, 10, 0]
[1, 0, 0, 1, 2, 0, 1, 2, 3, 1, 2, 3, 5, 2, 3, 5]
[1, 0, 0, 0, 3, 0, 0, 0, 6, 0, 0, 0, 10, 0, 0, 0]
[1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816]
[1, 3, 7, 13, 22, 34, 50, 70, 95, 125, 161, 203, 252, 308, 372, 444]
[1, 2, 5, 8, 14, 20, 30, 40, 55, 70, 91, 112, 140, 168, 204, 240]
[1, 1, 4, 4, 10, 10, 20, 20, 35, 35, 56, 56, 84, 84, 120, 120]
[1, 0, 4, 0, 10, 0, 20, 0, 35, 0, 56, 0, 84, 0, 120, 0]
[1, 3, 6, 11, 18, 27, 39, 54, 72, 94, 120, 150, 185, 225, 270, 321]
[1, 2, 4, 7, 11, 16, 23, 31, 41, 53, 67, 83, 102, 123, 147, 174]
[1, 1, 3, 4, 7, 9, 14, 17, 24, 29, 38, 45, 57, 66, 81, 93]
[1, 0, 3, 1, 6, 3, 11, 6, 18, 11, 27, 18, 39, 27, 54, 39]
[1, 2, 3, 6, 9, 12, 18, 24, 30, 40, 50, 60, 75, 90, 105, 126]
[1, 1, 2, 4, 5, 7, 11, 13, 17, 23, 27, 33, 42, 48, 57, 69]
[1, 0, 2, 2, 3, 4, 7, 6, 11, 12, 15, 18, 24, 24, 33, 36]
[1, 1, 1, 4, 4, 4, 10, 10, 10, 20, 20, 20, 35, 35, 35, 56]
[1, 0, 1, 3, 1, 3, 7, 3, 7, 13, 7, 13, 22, 13, 22, 34]
[1, 0, 0, 4, 0, 0, 10, 0, 0, 20, 0, 0, 35, 0, 0, 56]
[1, 3, 6, 10, 16, 24, 34, 46, 61, 79, 100, 124, 152, 184, 220, 260]
[1, 2, 4, 6, 10, 14, 20, 26, 35, 44, 56, 68, 84, 100, 120, 140]
[1, 1, 3, 3, 7, 7, 13, 13, 22, 22, 34, 34, 50, 50, 70, 70]
[1, 0, 3, 0, 7, 0, 13, 0, 22, 0, 34, 0, 50, 0, 70, 0]
[1, 2, 3, 5, 8, 11, 15, 20, 26, 33, 41, 50, 61, 73, 86, 101]
[1, 1, 2, 3, 5, 6, 9, 11, 15, 18, 23, 27, 34, 39, 47, 54]
[1, 0, 2, 1, 4, 2, 7, 4, 11, 7, 16, 11, 23, 16, 31, 23]
[1, 1, 1, 3, 4, 4, 7, 9, 10, 14, 17, 19, 25, 29, 32, 40]
[1, 0, 1, 2, 2, 2, 5, 4, 6, 8, 9, 10, 15, 14, 18, 22]
[1, 0, 0, 3, 1, 0, 6, 3, 1, 10, 6, 3, 16, 10, 6, 24]
[1, 2, 3, 4, 7, 10, 13, 16, 22, 28, 34, 40, 50, 60, 70, 80]
[1, 1, 2, 2, 5, 5, 8, 8, 14, 14, 20, 20, 30, 30, 40, 40]
[1, 0, 2, 0, 5, 0, 8, 0, 14, 0, 20, 0, 30, 0, 40, 0]
[1, 1, 1, 2, 4, 4, 5, 7, 10, 11, 13, 16, 21, 23, 26, 31]
[1, 0, 1, 1, 3, 1, 4, 3, 7, 4, 9, 7, 14, 9, 17, 14]

best regards,

-- 
Thomas Baruchel