35
$\begingroup$

For the time being, the OEIS website contains almost $300000$ sequences. Each of these sequences is the mark of a specific mathematical concept. Sometimes two (or more) distinct concepts have the same mark, which suggests a connection between a priori independent mathematical areas. The most famous example like that is perhaps the Catalan numbers sequence: A000108.

Question: What are the examples of pair of integer sequences coinciding on all the known terms, but for which the coincidence for all the terms is unknown?

Cheating is not allowed. By cheating I mean artificial examples like:
$u_n = v_n =n$ for $n \neq 10$, and if RH is true then $u_{10} = v_{10} = 10$, else $u_{10}+1 = v_{10} = 1$.
The existence of an OEIS entry could act as safety.

EDIT: I would like to point out that all the answers below are about pair of integer sequences which were already conjectured to be the same, and of course they are on-topic (and some of them are very nice). Note that such examples can be found by searching something like "conjectured to be identical" on OEIS, as I did for some of my own examples below...
Now, a more surprising kind of answer would be a (non-cheating) pair of integer sequences which are the same on the known entries, but for which there is no evidence a priori that they are the same for all the entries or that they are related (i.e. the precise meaning of a coincidence). Such examples, also on-topic, could reveal some unexpected connections in mathematics, but could be harder to find...

Improve this question
$\endgroup$
5
  • $\begingroup$ Related: Longest coinciding pair of integer sequences known. $\endgroup$
    – dxiv
    Commented Jan 5, 2018 at 20:24
  • $\begingroup$ @dxiv: I was about to write the same comment. It should be precise that the post you linked requests pair of integer sequences coinciding up to a large $N$ but differing after that, whereas here we request that there is no known difference. $\endgroup$
    – Sebastien Palcoux
    Commented Jan 5, 2018 at 21:45
  • $\begingroup$ Right, of course. The two questions are related, but distinctly different. $\endgroup$
    – dxiv
    Commented Jan 6, 2018 at 8:22
  • 2
    $\begingroup$ I think sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/mathar.pdf belongs here as a comment, to remind us that some conjectures reformulating definitions as recurrences can be automatically proved. $\endgroup$
    – Martin Rubey
    Commented Jan 7, 2018 at 7:22
  • $\begingroup$ As I mentioned in another MO answer (mathoverflow.net/a/387473/25028), the Erdős-Szekeres conjecture asserts that the smallest $N$ for which any $N$ points in general position in the plane contain the vertices of some convex $n$-gon is $N=2^{n-2}+1$. This is known to be true for $n=3,4,5,6$ but unknown for $n \geq 7$ and I don't think there is any really strong evidence that the pattern should continue. $\endgroup$
    – Sam Hopkins
    Commented 3 hours ago

8 Answers 8

Reset to default
49
$\begingroup$

A historical example, in the sense that the conjectural equality has been refuted: A180632 (Minimum length of a string of letters that contains every permutation of $n$ letters as sub-strings) was conjectured equal to A007489 ($\sum_{k=1}^n k!$).

The exact value of A180632 at $n=6$ is still unknown, but it must be less than the conjectured value of $1!+2!+\cdots+6!=873$, because the following string of length 872 contains every permutation of 123456 as a substring:

12345612345162345126345123645132645136245136425136452136451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654132654312645316243516243156243165243162543162453164253146253142653142563142536142531645231465231456231452631452361452316453216453126435126431526431256432156423154623154263154236154231654231564213564215362415362145362154362153462135462134562134652134625134621536421563421653421635421634521634251634215643251643256143256413256431265432165432615342613542613452613425613426513426153246513246531246351246315246312546321546325146325416325461325463124563214563241563245163245613245631246532146532416532461532641532614532615432651436251436521435621435261435216435214635214365124361524361254361245361243561243651423561423516423514623514263514236514326541362541365241356241352641352461352416352413654213654123

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I did not notice that this discovery is yours: arxiv.org/abs/1408.5108. Did you find something for $n=7$? $\endgroup$
    – Sebastien Palcoux
    Commented Jan 29, 2018 at 18:40
  • 2
    $\begingroup$ Today's Numberphile video is on the superpermutations: youtu.be/wJGE4aEWc28 $\endgroup$
    – Sebastien Palcoux
    Commented Jan 29, 2018 at 18:49
  • 2
    $\begingroup$ @SebastienPalcoux No; but I’m trying to capitalise on the interest the video has generated to gather a group of people who are interested in pushing the computations further, so we may see some progress as a result of that. $\endgroup$
    – Robin Houston
    Commented Jan 30, 2018 at 20:59
30
$\begingroup$

[EDITED] The classic example is A000396: "Perfect numbers n: n is equal to the sum of the proper divisors of n" and A000668(n)*(A000668(n)+1)/2 where A000668 are the Mersenne primes.

They are the same if and only if there are no odd perfect numbers.

See also sequences which agree for a long time.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ There was a time, in the 1970s, when the number of known perfect numbers was equal to the number of known sporadic simple groups (but I don't think anyone conjectured that they'd be equal when all was said and done). $\endgroup$
    – Gerry Myerson
    Commented Jan 5, 2018 at 14:51
  • 2
    $\begingroup$ Following those links, it looks like the sequences diverge after 2658455991569831744654692615953842176. Is that an error in one of the OEIS pages? $\endgroup$
    – user2357112
    Commented Jan 6, 2018 at 0:31
  • 2
    $\begingroup$ There is a careless mistake in your answer because A136007 is a strict subsequence of the Mersenne primes A000668, and so A152953 is also a strict subsequence of what you expected. You should write a(n) = A000668(n)*(A000668(n)+1)/2 or A006516(A000043(n)) or A139256(n)/2. $\endgroup$
    – Sebastien Palcoux
    Commented Jan 7, 2018 at 0:13
  • $\begingroup$ Oops, OK. Editing... $\endgroup$
    – Robert Israel
    Commented Jan 7, 2018 at 6:12
14
$\begingroup$

Just another instance of the (second) Strong Law of Small Numbers:

We have A157656(n) = A059100(n-1) for all known terms (i.e., $n\leq 6$), but it's also known that A157656(29) > A059100(28). So, the two sequences diverge somewhere.

Improve this answer
$\endgroup$
10
$\begingroup$

Some sequences have conjectured formulas, for example the following which I encountered recently, A227404.

$a_n$ is the total number of inversions, among all permutations on $[n]$ that is a single cycle in the cycle decomposition. It is conjectured that $a_n = n! (3n-1)/12$, and I find it rather amazing that there is no proof of this.

Improve this answer
$\endgroup$
5
  • 17
    $\begingroup$ I understand that your point is more general, but the formula for $a_n$ you mention can -- if I'm not mistaken -- be proven by counting the number of cyclic permutations $\sigma$ for which $\{a,b\}$ is an inversion. Indeed, if $a<b$ we must have $\sigma(a)>\sigma(b)$ which (as $\sigma(a)=a$, $\sigma(b)=b$, and $\{a,b\}=\{\sigma(a),\sigma(b)\}$ are disallowed) gives $\binom{n}{2} - n + b -a$ options for $(\sigma(a),\sigma(b))$. Each of these options can be extended to $(n-3)!$ cyclic permutations. So $a_n = (n-3)! \sum_{a < b} (\binom{n}{2} - n + b - a) = n!(3n-1)/12$. $\endgroup$
    – user133281
    Commented Jan 5, 2018 at 13:09
  • $\begingroup$ Similar to oeis.org/A216239 $\endgroup$
    – Max Alekseyev
    Commented Jan 5, 2018 at 13:34
  • 7
    $\begingroup$ "No proof" often means that the sequence did not attract enough attention. $\endgroup$
    – Max Alekseyev
    Commented Jan 5, 2018 at 13:35
  • $\begingroup$ @MaxAlekseyev: Yes, indeed. I like the proof given in the comment - I have another family of combinatorial objects that seem to be in bijection with these, so hence, I was interested in the proof :) $\endgroup$
    – Per Alexandersson
    Commented Jan 5, 2018 at 14:15
  • 3
    $\begingroup$ I've edited the sequence and removed "conjectured" from the formula. $\endgroup$
    – Max Alekseyev
    Commented Jan 5, 2018 at 15:22
5
$\begingroup$

  1. The least prime $p$ such that $p+2n$ is also prime: A020483$(n)$, and the smallest number $x$ such that $\sigma(x+2n) = \sigma(x)+2n$: A054906$(n)$.

  2. The smallest prime in which a digit appears $n$ times: A084673$(n)$, and the smallest prime containing exactly $n$ $1$'s: A037055$(n)$, for $n>1$.

  3. The number of subwords of length $n$ in the infinite word generated by $a \to aab, \ b \to b$ : A006697$(n)$, and the maximal number of distinct nonempty substrings of any binary string of length $n$, plus one: A094913$(n)+1$.

  4. The number of distinct values taken by ${\omega}$^${\omega}$^${\dots}$^${\omega}$ (with $n$ $\omega$'s and parentheses inserted in all possible ways) where $\omega$ is the first transfinite ordinal omega: A199812$(n)$, and the number of unlabeled rooted trees with at most $n$ nodes A087803$(n)$, minus $n$ plus one: A255170$(n)$.

  5. The number of transitive permutation groups of degree $n$: A002106$(n)$ is conjectured to be the number of Galois groups for irreducible polynomials (over $\mathbb{Q}$) of order $n$ (such groups are transitive). It is a particular case of the Inverse Galois problem.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ oeis.org/… yields another one, not as nice though: oeis.org/A023054 $\endgroup$
    – Martin Rubey
    Commented Jan 7, 2018 at 7:13
  • 1
    $\begingroup$ and another one, due to Callan: oeis.org/A001764 - $\binom{3n}{n}/(2n+1)$ equals the number of permutations of $[n+1]$ that avoid the patterns $4-2-3-1$ and $4-2-5-1-3$ and end with an ascent. $\endgroup$
    – Martin Rubey
    Commented Jan 7, 2018 at 7:26
3
$\begingroup$

Another example I know is A191363, i.e., numbers $n$ such that $\sigma(n) = 2n - 2$. According to OEIS all known terms are $(a_k-1)a_k/2$ where $a_k$ is the sequence of Fermat primes (A019434).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is a bit like saying that the sequence of odd perfect numbers seems to coincide with the sequence of all perfect numbers... $\endgroup$
    – darij grinberg
    Commented 5 hours ago
1
$\begingroup$

Here's an example of a pair of completely unrelated (as far as I can tell) sequences: Maximum order of an explicit Runge–Kutta method with n function evaluations in each step (A187103) and the metric dimension of the n-dimensional hypercube (A303735). The similarity of the sequences was first noted by Omar E. Pol.

Improve this answer
$\endgroup$
0
$\begingroup$

For example Recurrence relations of this type:$b_{n+1}+b_{n-1}=(n\alpha + \beta)b_n, n\geq 1 , b(0) = 0, b(1) = 1.$. with $\alpha, \beta$ real or complex appear in several contexts see sequences :A053983, A053984, A058797, A058798

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your two last hyperlinks go to the same page (and no need internal format). Thanks for sharing this answer but it is a bit off_topic... We basically request a pair of integer sequences (possibly on OEIS) whose known terms are the same but for which it is an open problem whether the rest of the terms are also the same. $\endgroup$
    – Sebastien Palcoux
    Commented Jan 6, 2018 at 14:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .