33

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

Sebastien Palcoux
  • 25,922

7 Answers7

46

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

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

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

Robert Israel
  • 53,594
14

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.

Max Alekseyev
  • 30,425
10

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.

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

  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.

Sebastien Palcoux
  • 25,922
  • 1
    https://oeis.org/search?q=%22Conjectured+extension%22&sort=&language=&go=Search yields another one, not as nice though: https://oeis.org/A023054 – Martin Rubey Jan 07 '18 at 07:13
  • 1
    and another one, due to Callan: https://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 07 '18 at 07:26
3

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

G. Melfi
  • 388
0

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

zeraoulia rafik
  • 2,236
  • 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 06 '18 at 14:45