# Examples of integer sequences coincidences

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...

• – dxiv Jan 5 '18 at 20:24
• @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. – Sebastien Palcoux Jan 5 '18 at 21:45
• Right, of course. The two questions are related, but distinctly different. – dxiv Jan 6 '18 at 8:22
• 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. – Martin Rubey Jan 7 '18 at 7:22

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

• I did not notice that this discovery is yours: arxiv.org/abs/1408.5108. Did you find something for $n=7$? – Sebastien Palcoux Jan 29 '18 at 18:40
• Today's Numberphile video is on the superpermutations: youtu.be/wJGE4aEWc28 – Sebastien Palcoux Jan 29 '18 at 18:49
• @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. – Robin Houston Jan 30 '18 at 20:59

[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.

• 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). – Gerry Myerson Jan 5 '18 at 14:51
• Following those links, it looks like the sequences diverge after 2658455991569831744654692615953842176. Is that an error in one of the OEIS pages? – user2357112 supports Monica Jan 6 '18 at 0:31
• 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. – Sebastien Palcoux Jan 7 '18 at 0:13
• Oops, OK. Editing... – Robert Israel Jan 7 '18 at 6:12

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.

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.

• 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$. – user133281 Jan 5 '18 at 13:09
• Similar to oeis.org/A216239 – Max Alekseyev Jan 5 '18 at 13:34
• "No proof" often means that the sequence did not attract enough attention. – Max Alekseyev Jan 5 '18 at 13:35
• @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 :) – Per Alexandersson Jan 5 '18 at 14:15
• I've edited the sequence and removed "conjectured" from the formula. – Max Alekseyev Jan 5 '18 at 15:22
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.

• oeis.org/… yields another one, not as nice though: oeis.org/A023054 – Martin Rubey Jan 7 '18 at 7:13
• 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. – Martin Rubey Jan 7 '18 at 7:26

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).

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

• 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. – Sebastien Palcoux Jan 6 '18 at 14:45