Longest coinciding pair of integer sequences known - MathOverflow

Longest coinciding pair of integer sequences known

2011-01-14T18:37:26Z

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 by Aaron Meyerowitz for Longest coinciding pair of integer sequences known

2011-01-14T18:54:02Z

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 by Qiaochu Yuan for Longest coinciding pair of integer sequences known

2011-01-14T19:46:50Z

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 by Douglas Zare for Longest coinciding pair of integer sequences known

2011-01-14T19:53:47Z

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 by Gerry Myerson for Longest coinciding pair of integer sequences known

2011-01-14T20:49:47Z

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 by N S for Longest coinciding pair of integer sequences known

2011-01-14T21:47:01Z

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 by Fedor Petrov for Longest coinciding pair of integer sequences known

2011-01-14T22:11:14Z

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 by Gottfried Helms for Longest coinciding pair of integer sequences known

2011-01-15T05:03:08Z

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 by jerr18 for Longest coinciding pair of integer sequences known

2011-01-15T08:43:40Z

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 by Fedor Petrov for Longest coinciding pair of integer sequences known

2011-01-15T19:09:21Z

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

Answer by KConrad for Longest coinciding pair of integer sequences known

2011-07-03T17:15:11Z

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

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.
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}$.
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.
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.
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.)
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$.
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 by Laurent Berger for Longest coinciding pair of integer sequences known

2011-07-03T18:04:13Z

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

http://mathoverflow.net/questions/11517/computer-algebra-errors