# Longest coinciding pair of integer sequences known

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

-
Your question strongly reminds me of a very similar earlier question on the phenomenon of eventual counterexamples. mathoverflow.net/questions/15444/… –  Willie Wong Jan 14 '11 at 19:13
I was also thinking of the eventual counterexamples thread, but couldn't recall the name. –  Suvrit Jan 14 '11 at 19:27
It's actually a trivial variant on the same question isn't it? –  Daniel Mehkeri Jan 16 '11 at 7:08

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

-

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.

-
Hans, I don't understand what criteria you are using to judge these answers. I could turn the observations in math.sjsu.edu/~hsu/courses/126/Law-of-Small-Numbers.pdf into answers where the first differing index is huge, e.g. #13 leads to two sequences where the first index which differs is n = 4700063497. –  Qiaochu Yuan Jan 15 '11 at 1:39

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

-

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

-
Thanks for the patience! –  Hans Stricker Jan 14 '11 at 21:03

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

-

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

-
+1. How many reps do you need? For the future, your comment could be simply turned into an answer by giving the explicit coincidence interval for some $k$ which beats others' records. $k=4$ would be more than sufficient. :-) –  Wadim Zudilin Jan 14 '11 at 23:09
true, but once $k=4$ becomes a record, $k=5$ beats it and so on :D –  N S Jan 15 '11 at 2:45

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 .

-
@Wadim: true, now that you mention this. I didn't have my example in mind in terms of general sequences, but rather just as an isolated, curious observation in the context of iteration of functions. Sorry - didn't decode the more general formulation of Qiaochu in time... –  Gottfried Helms Jan 15 '11 at 6:41
@Gottfried, +1 for your honesty! –  Wadim Zudilin Jan 15 '11 at 7:51
@Wadim: thanks, Wadim, that's very kind. And with this... I've got some vague idea to begin to understand better one of the rationale of the scheme of this site... Not a bad idea, indeed ;-) –  Gottfried Helms Jan 16 '11 at 0:03

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.

-

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.

-

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

Computer Algebra Errors

-
@Laurent, The answer? 23 answers were given to that question. Which one did you have in mind? –  Gerry Myerson Jul 3 '11 at 23:36
I meant the first one, sorry! –  Laurent Berger Jul 4 '11 at 7:01

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

-