# Computationally challenging integer sequences

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.

• Is your question restricted to sequences that are known to exist? Otherwise the sequence of odd perfect numbers would qualify. From the Mersenne Primes example I conclude, that potentially finite sequences are also in scope of your question. Mar 2, 2017 at 4:58
• @ManfredWeis That's a very good point. I think the main criterion is that it should be potentially feasible to compute the next term if one has an efficient algorithm and sufficient computing power (e.g. access to a supercomputer). So the problem is computational rather than theoretical. Though being a good example, odd perfect numbers hardly qualify then. Mar 2, 2017 at 5:03
• OEIS has a keyword "hard" for such sequences. See the "hard" paragraph in oeis.org/wiki/User:Charles_R_Greathouse_IV/Keywords/difficulty (which notes Mersenne exponents as one example). Mar 2, 2017 at 5:40
• @NoamD.Elkies thanks, I think this comment can actually be regarded as a partial answer. The only thing that I want to mention is that not all of the sequences marked with "hard" keyword require computational tools to extend them. For example, the kissing number sequence A257479 is marked as "hard", but determination of unknown terms of this sequence requires deep theoretical investigations rather than computations. Mar 2, 2017 at 6:17
• In particular, I would be interested in an extension of the hard sequence oeis.org/A060638 per the discussion in mathoverflow.net/questions/260279/… and math.stackexchange.com/questions/2120390/…. Mar 2, 2017 at 19:03

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 http://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 http://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.

http://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, http://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 http://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.

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.

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.

• What does it mean for a given BB number to be uncomputable -- it's just a number! What's uncomputable is the function $f(n)$ which returns the $n$th BB number. Mar 8, 2017 at 10:58
• @AryehKontorovich: It means that you can't prove that BB(n) is what it is.
– aorq
Mar 8, 2017 at 19:50
• Ok, but then the correct terminology is provable. Any singleton set (consisting of a number or a string) is computable. So is any finite set for that matter. Mar 8, 2017 at 22:53
• It is possible, however, for the value of $\mathrm{BB}(10)$, to be undecidable in $ZFC$, meaning that the statement $\mathrm{BB}(10)=k$ cannot be proven in $ZFC$ for any concrete $k$. Currently we know that $\mathrm{BB}(8000)$ has this property (arxiv.org/pdf/1605.04343) but the number has been reduced dramatically in subsequent efforts (to around 2000 if memory serves).
– cody
Mar 22, 2017 at 17:23

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.

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.