The Sequencer OEIS survey

The previously introduced software Sequencer identifies number sequences algorithmically. The On-Line Encyclopedia of Integer Sequences (OEIS) is by far the largest collection of curated number sequences available today. It therefore seems natural to employ Sequencer in a quest to uncover patterns that have been previously overlooked, by virtue of sheer brute force computing power brought down upon even the most "uninteresting" sequences.

The idea of using software to automatically identify patterns in the OEIS database is not new. Hieu Nguyen's 2012 talk "Data Mining the Online Encyclopedia of Integer Sequences for New Identities" describes a system that applies various transformations to sequences and attempts to correlate the results to experimentally discover candidate identities involving multiple sequences. At least one attempt has also been made before to find sequences that satisfy recurrence relations: Tanya Khovanova maintains a page with the results of such a search conducted in 2007, and in particular has identified some sequences whose elements as given by the OEIS pass recurrence tests, but are known to break that pattern at a later point not covered by the numerical data. The OEIS Wiki itself also has a list of sequences which agree for a long time but are nonetheless different. These examples serve as a reminder of the age-old wisdom that even mountains of numerical "evidence" can be misleading, which is why all results presented here should be taken with caution.

Search parameters

Because the goal was to find unknown formulas, OEIS entries possessing a "formula" field were excluded from the search, leaving only those without an associated formula. As of 8th March 2015, there were 156,592 such entries in the OEIS (the complete list was kindly provided to me by Charles Greathouse).

A total of around 650 CPU hours @ 3.2 GHz were spent running Sequencer on those entries, equivalent to 15 CPU seconds per entry on average. Unfortunately, it quickly turned out that absence of the "formula" field is an unreliable indicator for the absence of a formula in an entry: Formulas are often found in the title of the entry (e.g. A215137) or in the "comments" field (e.g. A203400). Nevertheless, exclusion of entries with known formulas prevented the rediscovery of thousands of redundant closed-form expressions which would have made manually examining the results very tedious.

All results may be reproduced by running the Sequencer JAR as follows:

java -jar sequencer.jar -r 1 -n -t [numbers]

Results

The full search output can be found here. A quick glance shows that most of the formulas found are in fact recurrence relations. This is because Sequencer constructs expressions going from simple to complex, and the complexity of closed-form expressions can often be "tucked away" in the initial values of a recurrence, which are simply pulled from the input numbers. At the risk of waxing philosophical here, there seems to be a deeper computational truth in the sense that recurrence relations are more "elementary" descriptions of number sequences than index-based ones.

Note that Sequencer always uses one-based indexing, i.e. the formulas consider $a_1$ to be the first element of the sequence, irrespective of the value of the OEIS entry's "offset" field.

Statistics

Out of 156,592 entries examined, Sequencer identified closed-form relations for 1318 of them. The vast majority of these results are immediately recognized as useless, falling into three broad categories:

1. The formula is already known and present in the title or description of the entry (e.g. A215137, see above). This turns out to be the case for 597 of the identified formulas, or 45 %.
2. The formula describes the numbers in the database correctly, but is obviously not a general pattern. This happens in particular for very short sequences (e.g. A014136) where Sequencer will construct complex formulas to match the given numbers (overfitting). This accounts for 346 cases, or 26 %.
3. The pattern found in the sequence is trivial (e.g. A020773). There are 268 such cases (20 %).

The remaining 107 cases contain a mixture of moderately interesting and marginally interesting candidate formulas, a selection of which is presented here:

Some conjectures

Each of the following conjectures holds for all elements of the given sequence as provided by the OEIS.

A003223

Superpositions of cycles of order $n$ of the groups $S_2$ and $D_n$.

Numbers

1, 2, 4, 10, 28, 130, ...

Conjecture

$$
a_n = a_{n-2} \, (a_{n-2}+3)
$$

A027983

$T(n,n+1) + T(n,n+2) + \dots + T(n,2n)$, $T$ given by A027960.

Numbers

1, 5, 14, 35, 81, 180, 389, 825, 1726, 3575, 7349, 15020, 30561, 61965, 125294, 252795, 509161, 1024100, 2057549, 4130225, 8284926, 16609455, 33282989, 66669660, 133507081, 267285605, 535010414, 1070731475, 2142612801, ...

Conjecture

$$
a_n = a_{n-2} + a_{n-1} + 2^n
$$

This recurrence can be solved algebraically and is probably related/equivalent to the formula from A027974.

A056084

Numbers $n$ such that $n^8 \equiv 1 \pmod{9^3}$.

Numbers

1, 728, 730, 1457, 1459, 2186, 2188, 2915, 2917, 3644, 3646, 4373, 4375, 5102, 5104, 5831, 5833, 6560, 6562, 7289, 7291, 8018, 8020, 8747, 8749, 9476, 9478, 10205, 10207, 10934, 10936, 11663, 11665, 12392, 12394, 13121, 13123, 13850, 13852, ...

Theorem

$$
a_n = \frac{1}{4} \, (1458 n - 729 + (-1)^n \times 725)
$$

Proof (due to Robert Israel)

It is clear that $x$ is in A056084 iff $x + 9^3$ is, so (once you verify that $1$ and $728$ are the only entries $< 9^3$) the conjectured formula is certainly true.

A121177

"Catapolyoctagons (see Cyvin et al. for precise definition)."

Numbers

0, 2, 12, 62, 312, ...

Conjecture

An entry without details (apparently motivated by chemistry), but it might be that

$$
a_n = \frac{1}{10} \, (5^n - 5)
$$

A121194

Number of $n$-celled polyominoes, where the cells are $1 \times 2$ rectangles with one edge of length $2$ replaced by a curved arc that either sags inwards or bulges outwards, subject to some restrictions.

Numbers

1, 2, 10, 84, ...

Conjecture

$$
a_n = C_n \, (n - 1)!
$$

where $C_n$ is the $n$th Catalan number.

Given that there are only four known elements, any conjecture based on numerical evidence alone is daring indeed, but this looks like a "natural" identity for a combinatorial process.

A129254

Numbers $n$ such that both $n$ and $n+1$ have at least one divisor of the form $p^e$ with $p\le e$, $p$ prime.

Numbers

27, 80, 135, 188, 243, 296, 351, 404, 459, 512, 567, 620, 675, 728, 783, 836, 891, 944, 999, 1052, 1107, 1160, 1215, 1268, 1323, 1376, 1431, 1484, 1539, 1592, 1647, 1700, 1755, 1808, 1863, 1916, 1971, 2024, 2079, 2132, 2187, 2240, 2295, 2348, 2403, 2456, ...

Conjecture

$$
a_n = 54n - \frac{1}{2} \, (55 + (-1)^n)
$$

Disproof (due to Hugo van der Sanden)

The conjecture for A129254 will match little more than the values listed – the pattern will break as soon as we start to reach [neighbours of] multiples of $5^5$, $3124$ being the first example.

A140590

Exchange successive pairs of terms of A000051. (i.e. $2^n + 1$)

Numbers

3, 2, 9, 5, 33, 17, 129, 65, 513, 257, 2049, 1025, 8193, 4097, 32769, 16385, ...

Theorem

$$
a_n = 2^{n-3} \, (5 - 3 \times (-1)^n) + 1
$$

Proof

Observe that

$$
4 \, (a_n - 1) + 1 = a_{n+2}
$$

and solve the recurrence relation.

A145052

One-third of the number of $n \times n$ nonnegative integer arrays with every $3 \times 3$ subblock summing to $1$.

Numbers

3, 7, 11, 15, 27, 39, 51, 87, 123, 159, 267, 375, 483, 807, 1131, 1455, 2427, 3399, 4371, 7287, 10203, 13119, 21867, 30615, ...

Conjecture

$$
a_n = 3 \, (a_{n-3} + 2)
$$

A152929

"Number of sets (in the Hausdorff metric geometry) at each location between two sets defining a polygonal configuration consisting of two $4$-gonal polygonal components chained with string components of length $l$ as $l$ varies."

Numbers

113, 176, 289, 465, 754, 1219, 1973, 3192, 5165, 8357, ...

Conjecture

$$
a_n = \frac{1}{2} \, (163 \, F_n + 63 \, L_n)
$$

where $F_n$ is the $n$th Fibonacci number and $L_n$ is the $n$th Lucas number.

I must admit that I have absolutely no clue what the definition actually means, or what it is useful for. However, the OEIS entry includes a very complex Maple program for computing the sequence, which could be dramatically simplified if the conjecture were true.

A169627

"A conjectured sequence of bud numbers for eucalyptus flowers."

Numbers

1, 3, 7, 13, 21, 31, ...

Conjecture

$$
a_n = n^2 - n + 1
$$

Biological processes usually don't precisely follow the mathematics drawn up to describe them. Whether or not this formula is an actual pattern I cannot even speculate about.

A186357

Adjusted joint rank sequence of $(f(i))$ and $(g(j))$ with $f(i)$ after $g(j)$ when $f(i)=g(j)$, where $f(i)=3i$ and $g(j)=j(j+1)/2$ (triangular number). Complement of A186357.

Numbers

1, 2, 4, 7, 9, 12, 16, 19, 23, 28, 32, 37, 43, 48, 54, 61, 67, 74, 82, 89, 97, 106, 114, 123, 133, 142, 152, 163, 173, 184, 196, 207, 219, 232, 244, 257, 271, 284, 298, 313, 327, 342, 358, 373, 389, 406, 422, 439, 457, 474, 492, 511, 529, 548, 568, 587, 607, 628, 648, 669, 691, 712, 734, 757, 779, 802, 826, 849, 873, 898, 922, 947, 973, 998, 1024, 1051, 1077, 1104, 1132, 1159, 1187, 1216, 1244, 1273, 1303, 1332, 1362, 1393, 1423, 1454, ...

Conjecture

$$
a_n = \frac{1}{18} \, \left( 3n^2 + 21n - 8 \, \sin \left( \frac{\pi}{6} - \frac{2 \pi n}{3} \right) - 14 \right)
$$

This relatively complex formula is the solution to the recurrence relation

$$
a_n = a_{n-3} + n + 2
$$

which was found by Sequencer, given the initial values from the sequence. A186355 and A186498 appear to satisfy the same recurrence, with different initial values.

A193129

Numbers of spanning trees of the barbell graphs. (Should this be "Number of spanning trees ..." instead?)

Numbers

9, 256, 15625, 1679616, 282475249, 68719476736, 22876792454961, 10000000000000000, 5559917313492231481, 3833759992447475122176, 3211838877954855105157369, 3214199700417740936751087616, 3787675244106352329254150390625, 5192296858534827628530496329220096, 8193465725814765556554001028792218849, 14747559712960682275277163588165279154176, 30034640110980377619945846078500632729311721, 68719476736000000000000000000000000000000000000, ...

Conjecture

$$
a_n = (n+2)^{2n}
$$

A210379

Number of $2 \times 2$ matrices with all terms in ${0,1,\dots,n}$ and odd trace.

Numbers

0, 8, 36, 128, 300, 648, 1176, 2048, 3240, 5000, 7260, 10368, 14196, 19208, 25200, 32768, 41616, 52488, 64980, 80000, 97020, 117128, 139656, 165888, 195000, 228488, 265356, 307328, 353220, 405000, 461280, 524288, 592416, 668168, ...

Theorem

$$
a_n = n^2 \, \left\lfloor \frac{n^2}{2} \right\rfloor
$$

Note that this formula also implies a formula for A210378 via the observation in the comments section of A210379 that A210379(n)+A210378(n)=(n+1)^4.

Proof (due to Max Alekseyev)

Note that this proof uses the offset $0$ as given in the entry.

The factor $(n+1)^2$ stands for the number of elements at entries $(1,2)$ and $(2,1)$ of the matrix, which do not participate in the trace calculation and thus each can independently take all $n+1$ different values. The factor $\lfloor (n+1)^2/2 \rfloor$ counts number of pairs of elements (indexed $(1,1)$ and $(2,2)$ in the matrix) from $\{0,1,...,n\}$ with odd sum. If $n$ is odd, there are $(n+1)/2$ even and $(n+1)/2$ odd numbers in the set, implying that the number of pairs with odd sum is $$(n+1)/2 \times (n+1)/2 + (n+1)/2 \times (n+1)/2 = (n+1)^2/2 = \lfloor (n+1)^2/2 \rfloor$$ If $n$ is even, there are $(n+2)/2$ even and $n/2$ odd numbers in the set, implying that there are $$(n+2)/2 \times n/2 + n/2 \times (n+2)/2 = n \times (n+2)/2 = \lfloor (n+1)^2/2 \rfloor$$

A218564

Numbers $n$ such that $n^2 + 1$ is divisible by a $5$th power.

Numbers

1068, 2057, 4193, 5182, 7318, 8307, 10443, 11432, 13568, 14557, 16693, 17682, 19818, 20807, 22943, 23932, 26068, 27057, 29193, 30182, 32318, 33307, 35443, 36432, 38568, 39557, 41693, 42682, 44818, 45807, 47943, 48932, 51068, 52057, 54193, 55182, 57318, 58307, ...

Conjecture

$$
a_n = \frac{1}{4} \, (6250 n - 1147 \times (-1)^n - 3125)
$$

Similar formulas exist for A218565 and A218574.

Disproof (due to Max Alekseyev)

The conjectured formula for A218564 (Numbers $n$ such that $n^2+1$ is divisible by a $5$th power) is wrong. The "period" in the conjectured formula is $5^5$, and the listed sequence terms just not yet reached the next possible fifth power divisor, which is $13^5$. E.g., there is a term $143044$ of A218564 (with $143044^2 + 1$ divisible by $13^5$), which does not fit the proposed formula.

A231002

Number of years after which it is possible to have a date falling on same day of the week, but the entire year does not have the same calendar, in the Julian calendar.

Numbers

5, 23, 33, 51, 61, 79, 89, 107, 117, 135, 145, 163, 173, 191, 201, 219, 229, 247, 257, 275, 285, 303, 313, 331, 341, 359, 369, 387, 397, 415, 425, 443, 453, 471, 481, 499, 509, 527, 537, 555, 565, 583, 593, 611, 621, 639, 649, 667, 677, 695, 705, 723, 733, 751, 761, 779, 789, ...

Theorem

$$
a_n = 14n + 2 \times (-1)^n - 7
$$

Proof (due to Maximilian F. Hasler)

The conjecture about A231002 is more or less explained in the sequence, but incorrectly stated as "the sequence has a period of $28$". What is meant is that the characteristic sequence of these years has a period of $28$, i.e., $n>0$ is in the sequence iff $n+28$ is in the sequence, and since $5$ and $23$ ($\equiv -5 \pmod{28}$) are the only terms $\le 28$, this is the sequence of numbers congruent to $+$/$-$ $5 \pmod{28}$.

Cover image: Alexandre Duret-Lutz (Wikimedia Commons, CC-BY-SA)