Computationally challenging integer sequences

Question

I wonder what are the examples of integer sequences, where only few elements are known and the researchers are still actively looking for the new terms. I think this discussion might be a good reference for those who would like to contribute to mathematical community by doing large scale calculations, extending the numerical data and providing computational evidence towards known conjectures.

The examples should include only those sequences where it is potentially feasible to compute one of the unknown terms if one has an optimized algorithm and enough computing power. In other words, the problem should be more computational rather than theoretical.

Perhaps, the most famous example are Mersenne primes (A001348), where only the first 45 consecutive terms are known (even though 49 Mersenne primes are known):

$3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647, \ldots$

The members of GIMPS (Great Internet Mersenne Prime Search) are actively searching for the new terms, and according to the website are currently trying to prove that $M_{37156667}$ is the 46th Mersenne prime.

Another interesting example is the number of arrangements of $n$ circes in the affine plane (A250001), where only the first 5 terms are known:

$1, 1, 3, 14, 173.$

All of these elements got computed by Jon Wild, and on the OEIS webpage for this sequence he mentioned that the 5th element (the sequence starts with the 0th term) is probably equal to 16942.

I'd be interested to see other curious examples.

Answer 1

I think the question is too broad. There are a variety of such examples, and it seems that many combinatorial items and computational complexity items would fit the bill. The OEIS has a "most wanted" list, and so do I, but it is not clear which of these are a best fit for your question.

I start with https://oeis.org/A051236 which relates to the determinant spectrum problem mentioned by Will Orrick in https://mathoverflow.net/a/21510. Even conjectured values are known only for the first twenty or so terms. There are many related sequences, including https://oeis.org/A003432, the maximal determinant of an order n real 0-1 matrix. These are computationally challenging because we only know what such a matrix looks like for some n. We do not understand the determinant function as a combinatiorial entity enough to predict its range on certain sets.

Ramsey numbers provide several easily estimated and computationally hard sequences. I'll let an expert expound on these.

https://oeis.org/A005245 is another favorite of mine relating to integer complexity. Harry Altman has studied this, and posted on MathOverflow about it. Many terms can be computed now, but since for each n it involves a minimum over exponentially many configurations, one has to be clever in how to compute it. It is less challenging than computing Ramsey numbers, but you can't analyze it and compute bits of it like you can a Fibonacci sequence.

There is Dedekind's problem, https://oeis.org/A000372, or for universal algebraists, the size of the free distributive lattice generated by n elements. In fact, free spectra and enumeration of structures satisfying certain not necessarily equationally expressed conditions are subjects of ongoing research. Union closed families fall under https://oeis.org/A102897, and are another personal favorite.

Under suitable encoding/listings, various sequences of 0's and 1's are of interest. These are languages of varying computational complexity, usually corresponding to whether the nth structure of a list has property P or not, for example if a given graph has a Hamiltonian cycle.

I think all of these examples and many more fit your criteria. You might consider revising your question to give more examples and nonexamples from the OEIS corpus.

Gerhard "Or Maybe Check Their Website" Paseman, 2017.03.02.

Answer 2

Here is a sequence that is quite famous but not in OEIS I think (perhaps because too few elements are known). A hypergraph is $v$-uniform if every edge has $v$ vertices, and 2-colourable if the vertices can be coloured using two colours so that no edge is monochromatic (this is also called "Property B").

Now define $m(v)$ to be the least number of edges in a $v$-uniform hypergraph that is not 2-colourable.

Erdős and Hajnal noted about a million years ago that $m(1)=1$, $m(2)=3$ and $m(3)=7$. In 2014 Patric R.J. Östergård proved $m(4)=23$ using an extensive computation. No other values are known.

Answer 3

How about busy beaver numbers. I think the first 5 are known, and there are very large lower bounds for the 6th and 7th, which may already be uncomputible. The sequence definitely becomes uncomputable after some probably low number of entries. But it might be possible to establish the 6th or 7th number.

Answer 4

The Hales-Jewett numbers $c_{n,k}$ are defined, essentially, to be the largest possible size of a subset of $\mathbb Z_k^n$ free of $k$-term arithmetic progressions with the difference in $\{0,1\}^n$ and satisfying the additional restriction that the support of the initial term of the progression is disjoint from the support of its difference. A significant part of the Polymath project Density Hales-Jewett and Moser Numbers consists in determining the numbers $c_{n,3}$. We know the first seven Hales-Jewett numbers (with $k=3$): $$ c_{0,3}=1,\ c_{1,3}=2,\ c_{2,3}=6,\ c_{3,3}=18,\ c_{4,3}=52,\ c_{5,3}=150,\ c_{6,3}=450; $$ see Theorem 1.4 of the aforementioned project, or OEIS sequence A156989.

What if we drop the support disjointness restriction and define, say, $\mu_n$ to be the largest possible size of a subset of $\mathbb F_3^n$ free of three-term arithmetic progressions with the difference in $\{0,1\}^n$? It is not particularly difficult to see that $$ \mu_0=1,\ \mu_1=2,\ \mu_2=6,\ \mu_3=14,\ \text{and}\ 36\le\mu_4\le 40. $$

Virtually nothing is known about the order of growth of the numbers $\mu_n$, and to develop some intuition, it would be extremely helpful to compute several more of them.

---

Added March 13, 2017

Robert Israel reports $\mu_4=36$ and $\mu_5\ge 102$, using cplex. Moreover, computations seem to suggest that, indeed, $\mu_5=102$ may hold true.

Answer 5

Longest non-repeating sequence of Conway's game of life states, on an $n \times n$-torus, A294241.

In order to compute the $n$th term, one needs to compute the longest path in a graph with $2^{n^2}$ vertices. Only the first 6 terms are known: 2, 2, 3, 10, 52, 91

Answer 6

Let $f(n)$ be the minimum $M$ for which any $M$ points in general position contain a convex $n$-gon. (It is a famous early result of Erdős and Szekeres that $f(n)$ is finite for all $n\geq 3$.) It is known that $f(3)=3$, $f(4)=5$, $f(5)=9$, $f(6)=17$, but the value of $f(n)$ is unknown for $n \geq 7$.

It was conjectured by Erdős and Szekeres that $f(n) = 2^{n-2}+1$ for all $n$, and it is known that this is a lower-bound, and a 2016 result of Suk says this is asymptotically the right order, but I'm not sure how much evidence really supports their conjecture. I'm also not sure how hard it would be to compute $f(7)$ (but presumably pretty hard since no one has done it). See https://en.wikipedia.org/wiki/Happy_ending_problem for more information.

Answer 7

A quite computationally challenging integer sequence I know is the sequence of odd positive integers $n$ for which $2n-\sigma(n)=6$, i.e. $n$ with ''abundance'' -6. Here $\sigma(n)$ denotes the sum of positive divisors of $n$. Only 8 terms of this sequence are known, and the largest one, 815634435, was computed on 2011 (sequence A141548). Larger terms of this sequence could be related to an eventual proof of the existence of odd weird numbers, an old open question raised by Erdös and Benkoski.

Answer 8

A semi-magic square of order $n$ is an $n\times n$ matrix with nonnegative integer entries, with all row sums and all column sums equal, e.g., $$ A_3=\pmatrix{2&2&3\cr3&3&1\cr2&2&3\cr} $$ We write $c(A)$ for the common row and column sum of a semi-magic square $A$, e.g., $c(A_3)=7$.

Every semi-magic square of order $n$ can be written as a positive integer linear combination of permutation matrices. We write $\beta(A)$ for the smallest possible number of distinct permutation matrices in such an expression for the semi-magic square $A$. It is known that if $A$ is of order $n$, then $\beta(A)\le n^2-2n+2$, and this bound is best possible. That is, every order $n$ semi-magic square can be written as a positive integer linear combination of at most $n^2-2n+2$ permutation matrices, and for every $n$ there exist order $n$ semi-magic squares that can't be written using fewer than $n^2-2n+2$ permutation matrices.

It can easily be shown that $A_3$ meets this bound, that is $\beta(A_3)=3^3-2\cdot3+2=5$

Now let $a_n$ be the smallest value of $c(A)$ over all order $n$ semi-magic squares with $\beta(A)=n^2-2n+2$. This is the integer sequence I nominate as computationally difficult.

It's not hard to show that for $n=3$, if $c(A)<7$, then $\beta(A)<5$, so from the facts given above about $A_3$, we get $a_3=7$.

Let $$ A_4=\pmatrix{5&5&7&14\cr11&18&1&1\cr10&3&16&2\cr5&5&7&14\cr} $$ Note $c(A_4)=31$. It can be shown by hand that $\beta(A_4)=4^2-2\cdot4+2=10$, and by exhaustive computer search that if $n=4$ then $c(A)<31$ implies $\beta(A)<10$, so $a_4=31$.

And that's as far as I got. I have a construction that gives, for each $n$, a semi-magic square $A$ of order $n$ satisfying $\beta(A)=n^2-2n+2$, and this gives a bound on $a_n$. This reduces computing $a_n$ to a finite, but computationally intensive, problem for each $n$.