You're reading: cp's mathem-o-blog, News

The OEIS now contains 300,000 integer sequences

The Online Encyclopedia of Integer Sequences just keeps on growing: at the end of last month it added its 300,000th entry.

Especially round entry numbers are set aside for particularly nice sequences to mark the passing of major milestones in the encyclopedia’s size; this time, we have four nice sequences starting at A300000. These were sequences that were originally submitted with indexes in the high 200,000s but were bumped up to get the attention associated with passing this milestone.

Here they are:

A300000: The sum of the first $n$ terms of the sequence is the concatenation of the first $n$ digits of the sequence, with $a(1) = 1$.

1, 10, 99, 999, 9990, 99900, 999000, 9990000, 99900000, 999000000, 9990000000, 99899999991, 998999999919, 9989999999190, 99899999991900, 998999999918991, 9989999999189910, 99899999991899109, 998999999918991090, 9989999999189910900, 99899999991899108991, 998999999918991089910, 998999999918991089910

The number formed by concatenating the first three digits in the sequence is $110 = 1 + 10 + 99$. This has a Golomb sequence vibe about it, though it’s a bit more straightforward to generate.

This sequence was submitted by Eric Angelini, a Belgian TV producer who has added countless sequences to the OEIS, usually generated like this by picking a constraint and working out what the sequence would need to look like in order to obey it.

A300001: Side length of the smallest equilateral triangle that can be dissected into $n$ equilateral triangles with integer sides, or $0$ if no such triangle exists.

1, 0, 0, 2, 0, 3, 4, 4, 3, 4, 5, 6, 4, 5, 6, 4, 5, 6, 5, 6, 6, 5, 7, 6, 5, 7, 6, 6, 7, 6, 7, 7, 6, 7, 7, 6, 7, 7, 8, 7, 7, 8, 7, 8, 8, 7, 8, 8, 7, 8, 9, 8, 8, 9, 8, 8, 9, 8, 9, 9, 8, 9, 9, 8, 9, 9, 9, 10, 9, 9, 10, 9, 9, 10, 9, 10, 10, 9, 10, 10, 9, 10, 10, 10, 10, 10, 11, 10, 10, 11, 10, 10, 11, 10, 11, 11, 10, 11, 11, 10

I’m amazed this one wasn’t already in! Seems like exactly the kind of thing that would appear in something like Dudeney’s Amusements. There’s an associated paper on the arXiv, by Ales Drapal and Carlo Hamalainen, which notes that some of the earliest work on triangle dissections was done by Bill Tutte, of Bletchley Park fame.

The entry page contains some fab plaintext-art drawings of solutions for a few different $n$.

A300002: Lexicographically earliest sequence of positive integers such that no $k+2$ points fall on any polynomial of degree $k$.

1, 2, 4, 3, 6, 5, 9, 16, 14, 20, 7, 15, 8, 12, 18, 31, 26, 27, 40, 30, 49, 38, 19, 10, 23, 53, 11

The definition of this one is a bit opaque if you’re not in the right frame of mind, but it’s really neat. If you plot the sequence, as the OEIS can automatically do for you, you get this:

Or, if you want to do this in your head, think of the set of points $(n, a(n))$.

Now, if you pick any polynomial of degree $k$, there’s no subset of $k+2$ of the points on the scatter plot that lie on that polynomial. It’s a ‘duck-and-dive’ sequence – it always picks the smallest number that won’t be on any of the $2^{n-1}$ polynomials defined by the sequence leading up to $a(n)$.

The OEIS entry contains a conjecture that this sequence is a permutation of the natural numbers. It’s easily shown that it contains no duplicates – otherwise, if the number $m$ is repeated, there’d be two elements lying on the line $y=m$, a degree-0 polynomial. What’s not obvious is that every number will eventually turn up. It’d be pretty wild if some numbers never did – and that’d form a new sequence, too!

A300003: Triangle read by rows: $T(n, k) =$ number of permutations that are $k$ “block reversals” away from $12…n$, for $n \geq 0$, and (for $n \gt 0$) $0 \leq k \leq n-1$.

1, 1, 1, 1, 1, 3, 2, 1, 6, 15, 2, 1, 10, 52, 55, 2, 1, 15, 129, 389, 184, 2, 1, 21, 266, 1563, 2539, 648, 2, 1, 28, 487, 4642, 16445, 16604, 2111, 2, 1, 36, 820, 11407, 69863, 169034, 105365, 6352, 2, 1, 45, 1297, 24600, 228613, 1016341, 1686534, 654030, 17337, 2

I don’t like “triangle read by rows” entries, purely because the OEIS’s web interface doesn’t make them easy to read. It’s debatable whether sequences generated by two parameters are even ‘sequences’, but that’s not a fight worth having, because there are some truly fab bits of maths hiding in the OEIS’s triangles.

The Oval Track puzzle. You can reverse four elements at a time. There’s also a cyclic permutation move, which A300003 doesn’t allow.

This one looks at what you can do by starting with the list of numbers $1,2, \ldots, n$, and repeatedly picking a block of adjacent numbers and reversing their order. It’s like a generalised version of the Oval Track puzzle.

 

Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Google+