Longest coinciding pair of integer sequences known

Question

There are arbitrarily many pairs of integer sequences (of arbitrary origins) that coincide upto an $N$ but differ for an $n > N$. I assume, the coincidence will be considered accidentally then by default, but I may be mistaken about that.

One is disadviced to draw any conclusions from coincidences of integer sequences unless its proven, that they coincide for all $n$. (Even then there may be no sensible conclusions, as I have learned here: Equivalence of families of objects with the same counting function.)

In any case, it is hard not to be entrapped to draw a conclusion when $N$ is very large. But what is "very large"? Thus my question:

What is the largest $N$ with two known integer sequences coinciding upto $N$ but differing for an $n > N$?

(Can this information be captured from OEIS by an intelligent query?)

(I am aware of the fact that one can trivially define pairs of integer sequences which conincide for all $n$ but a single and arbitrarily large one. It should be clear that I am not interested in those but in pairs that are not adjusted to each other this way.)

Answer 1

The number of divisions of $\mathbb{R}^3$ by $k \ge 0$ planes in general position starts 1,2,4,8, then 15, etc. For $\mathbb{R}^6$ it is 1,2,4,8,16,32,64 then 127. In general for $\mathbb{R}^N$ it is the sum of the binomial coefficients from $\binom{k}{0}$ up to $\binom{k}{N}$ and hence it agrees with $2^k$ for terms 0,1,2, up to N before starting to fall off.

other answers Of course for prime p, $2^{p-1}=1 \mod{p}$ but there are only 2 known cases $p=1093$ and $3511$ where $2^{p-1}=1 \mod{p^2}$. SO primes and primes with $2^{p-1} \ne 1 \mod{ p^2}$ agree for the first 182 primes.

For "listed in the OEIS" there are a couple which go from 1 to 99 then skip 100: undulating numbers in base 10 and cents you can have in US coins without having change for a dollar (the latter being 1-99 along with $105, 106, 107, 108, 109, 115, 116, 117, 118, 119$.)

Answer 2

It is a known example: sequence 1,2,3,5,7,11,13,$\dots$ of non-composite numbers coincides with the sequence of orders of finite simple groups until 60 appears (in this last sequence).

Answer 3

The positive odd integers $n$ which pass the Euler-Jacobi primality test to base $2,$ $2^{(n-1)/2} \equiv \big(\frac2n\big) \mod n$ where the RHS is the Jacobi symbol, agree with the odd primes up to the inclusion of $561$. So, these sequences $3, 5, 7, 11, 13, ..., 557, 561, 563, ...$ and $3, 5, 7, 11, 13, ..., 557, 563, ...$ agree for $101$ terms.

Answer 4

There are many natural examples of a sequence $a_{n,k}$ of two parameters such that $a_{n,k}$ approximates a sequence $a_n$ as $k \to \infty$ in the sense that the first $k$ terms of $a_n$ and $a_{n,k}$ agree. Aaron Meyerowitz gives a good one; another example is the "partial Catalan" sequence $C_{n,k}$ of all parenthesizations using $n$ pairs of parentheses with parenthetical depth at most $k$. So I don't think this is quite the questions you meant to ask.

(A nice commonality between Aaron Meyerowitz's example and this one is that for fixed $k$ the approximating sequences $a_{n,k}$ are regular, so their generating functions are rational. So one can think of these generating functions as "rational approximations" to the generating function of $a_n$, which can in some cases be obtained by truncating a continued fraction expansion. This is the case with my example; see this blog post.)

Answer 5

A possibly unbeatable example: the sequence $a(n)$, where $a(n)$ is the periodicity of the first row in the Laver table based on the set $\left\lbrace 1,\ldots, 2^n\right\rbrace$: The first values are $$1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16,\ldots$$ and then it stays at $16$ for ages: Randall Dougherty showed that the first $n$ for which $a(n)$ can possibly differ from $16$ is A(9,A(8,A(8,255))), where A denotes the Ackermann function, a recursive function whose first values are already huge.

However, it can be shown that the sequence actually tends to infinity, under some additional axiom that is independent to the usual ones from ZFC.

Answer 6

For what it's worth, the OEIS has 99 sequences containing the string 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35, which is all I had the patience to type in. A153671, Minimal exponents m such that the fractional part of $(101/100)^m$ obtains a maximum (when starting with $m=1$), continues the pattern up to 69, then goes 110, 180, ....

Answer 7

Sorry not enough points to post a comment so had to make this an answer.

Not really the most natural sequences, but the sequences $a_n^{(k)}$ of positive integers which have at most $k$ distinct prime factors coincide a lot (among themselves and with the integers).

The first term not in $a_n^{(k)}$ is $p_1\cdot p_2 .... \cdot p_{k+1}$.

Answer 8

If you define the function $f$ of $h$ and $x$ by
$f(1,x) = 1+ x $ and
$ f(h+1,x) = (1+x) ^ {f(h,x)} $

then the leading coefficents at the powers of x in the formal powerseries up to an index k=1 ... h are equal for f(h+j,x) and j>0

f(0,x) = 1 + x
f(1,x) = 1 + x + x^2 + 1/2*x^3 + 1/3*x^4 + 1/12*x^5 + 3/40*x^6 - ...
f(2,x) = 1 + x + x^2 + 3/2*x^3 + 4/3*x^4 + 3/2*x^5 + 53/40*x^6 + ...
f(3,x) = 1 + x + x^2 + 3/2*x^3 + 7/3*x^4 + 3*x^5 + 163/40*x^6 + ....
f(4,x) = 1 + x + x^2 + 3/2*x^3 + 7/3*x^4 + 4*x^5 + 243/40*x^6 + ...

So if we use the coefficients of the powerseries of f(N,x) and f(N+1,x) the sought N can be arbitrarily high .

Answer 9

By searching OEIS for the list 1,2,4,8,16, I found the following examples of sequences that start out as 1, 2, 4, 8, 16, but do not equal the sequence of powers of 2.

1. For $n \geq 1$, mark $n$ equally spaced points around a circle and draw a line connecting each of those points to all the rest. Consider the number of regions thus formed inside the circle. This sequence begins $$1, 2, 4, 8, 16, 30, 57, 88, 163, 230$$ and is Sloane's A006533. (A general formula for the $n$th term is given in Poonen and Rubinstein's paper "The number of intersection points made by the diagonal of a regular polygon" and depends on $n$ mod 2520.)

2. For $n \geq 1$, mark $n$ points around a circle in general position and draw a line connecting each of those points to all the rest. The number of regions thus formed inside the circle. begins $$1, 2, 4, 8, 16, 31, 57, 99, 163, 256$$ and is Sloane's A000127. A general formula for the $n$th term is $1 + \binom{n}{2} + \binom{n}{4}$.

3. The number of positive divisors of $n!$ for $n \geq 1$ begins $$ 1, 2, 4, 8, 16, 30, 60, 96, 160, 270 $$ and is Sloane's A027423.

4. The set of $n \geq 1$ such that $3^n \equiv 1 \bmod n$ begins $$ 1, 2, 4, 8, 16, 20, 32, 40, 64, 80 $$ and is Sloane's A067945. The powers of 2 are a subsequence.

5. For $n \geq 0$, the smallest positive integer that needs $n$ steps to reach 1 in the $3x+1$ problem begins $$ 1, 2, 4, 8, 16, 5, 10, 3, 6, 12 $$ and is Sloane's A033491. Here we need to be careful to call this a sequence and not a set since it is not increasing. (I think everyone understands what I am trying to say in the previous sentence.)

6. For $n \geq 1$, the number of different products of distinct numbers in $\{1,2,\dots,n\}$ begins $$ 1, 2, 4, 8, 16, 26, 52, 88, 152, 238 $$ and is Sloane's A060957. The reason we don't get 32 different products when $n = 6$ is due to duplicate products like $2\cdot 3 = 6$ and $2 \cdot 6 = 3 \cdot 4$.

7. For each odd integer $n \geq 1$ (admittedly restricting to odd $n$ may make the result look rigged) the number of partitions of $n$ into an odd number of parts (e.g., 5 can be written in 4 such ways, with 1 part as 5, with 3 parts as 1+2+2 and 1+1+3, and with 5 parts as 1+1+1+1+1) begins $$ 1, 2, 4, 8, 16, 29, 52, 90, 151, 248 $$ and is Sloane's A160786.

I realize this doesn't strictly answer the original question (give very large $N$ where two sequences differ for the first time), but it seems close in spirit (giving many sequences which start out with the same first 5 terms and eventually look different). If someone knows a better MO question for which this would be a good answer, make a comment.

I had known about the first two examples above for quite a few years and about a month or so ago some answer on MO led me to learn about the last example in a paper by Arnold. Then I just typed 1,2,4,8,16 into OEIS and found the other examples. There are more 1,2,4,8,16 examples in OEIS but many of them seemed much less interesting to me.

If you know how to do web links in MO answers, feel free to make a link for each Sloane number above to the corresponding page on OEIS and then delete this sentence.

Answer 10

or another cheating example: positive integers and remainders of positive integers modulo 100000000.

Answer 11

I know I am cheating :-)

A) $a_n = n + C \lfloor \frac{n}{N}\rfloor$

B) Integers of form $x+\prod_{1 \leq k \leq N}{(x-k)}$

EDIT: up to $N$ A and B coincide with $\mathbb{N}$ so it is a triple in a sense.

Answer 12

There is also, of course, what comes out of the answer which was given to this question:

Computer Algebra Errors

Answer 13

Another non trivial exemple is the sequence of integers whose binary expansion contains digits in not increasing order : this squence in base two writes as 1,10,11,100,110,111,1000,1100,1110,1111,10000,11000,.... This sequence (A023758) coincides up to its 22nd term with the sequence of integers $n$ having as many 1's in its binary expansion as $n^2$ (sequence A077436).