20
$\begingroup$

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

$\endgroup$
4
  • 5
    $\begingroup$ Your question strongly reminds me of a very similar earlier question on the phenomenon of eventual counterexamples. mathoverflow.net/questions/15444/… $\endgroup$ Jan 14, 2011 at 19:13
  • $\begingroup$ I was also thinking of the eventual counterexamples thread, but couldn't recall the name. $\endgroup$
    – Suvrit
    Jan 14, 2011 at 19:27
  • 1
    $\begingroup$ It's actually a trivial variant on the same question isn't it? $\endgroup$ Jan 16, 2011 at 7:08
  • $\begingroup$ @DanielMehkeri well it is a variant, can not really say that it is trivial. $\endgroup$
    – user137767
    Apr 11, 2019 at 13:21

13 Answers 13

36
$\begingroup$

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

$\endgroup$
0
16
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 15, 2011 at 1:39
15
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It is half an example. How is the other (different) sequence defined? Gerhard "Remember, No Slight Adjustments Allowed" Paseman, 2017.12.04. $\endgroup$ Dec 4, 2017 at 16:00
  • 5
    $\begingroup$ The same sequence, where you never get off $16$. $\endgroup$ Dec 4, 2017 at 16:03
  • 2
    $\begingroup$ Indeed, and where does the latter sequence come from? Surely from something other than Laver tables? Gerhard "Otherwise I Have Longer Counterexamples" Paseman, 2017.12.04. $\endgroup$ Dec 4, 2017 at 16:14
9
$\begingroup$

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

$\endgroup$
0
8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ +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. :-) $\endgroup$ Jan 14, 2011 at 23:09
  • $\begingroup$ true, but once $k=4$ becomes a record, $k=5$ beats it and so on :D $\endgroup$
    – N S
    Jan 15, 2011 at 2:45
6
$\begingroup$

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 .

$\endgroup$
4
  • $\begingroup$ @Gottfried, isn't it a subanswer of Qiaochu's answer? $\endgroup$ Jan 15, 2011 at 6:00
  • $\begingroup$ @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... $\endgroup$ Jan 15, 2011 at 6:41
  • $\begingroup$ @Gottfried, +1 for your honesty! $\endgroup$ Jan 15, 2011 at 7:51
  • $\begingroup$ @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 ;-) $\endgroup$ Jan 16, 2011 at 0:03
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ OEIS knows 24 sequences containing $1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384$. oeis.org/A247208 Common bases of 1093 and 3511 as generalized Wieferich primes, has powers of 2 as a subsequence, but squeezes 1717308 in between $2^{20}$ and $2^{21}$ (and has infinitely many prime members). $\endgroup$ Dec 4, 2017 at 22:00
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

Computer Algebra Errors

$\endgroup$
3
  • 1
    $\begingroup$ @Laurent, The answer? 23 answers were given to that question. Which one did you have in mind? $\endgroup$ Jul 3, 2011 at 23:36
  • $\begingroup$ I meant the first one, sorry! $\endgroup$ Jul 4, 2011 at 7:01
  • $\begingroup$ I guess "the first one" literally means mathoverflow.net/a/11518/2383 (sorted by "oldest")? @DanPiponi's answer mathoverflow.net/a/11607/2383 seems like a better candidate, and is also early, so maybe it's what you meant. $\endgroup$
    – LSpice
    Dec 5, 2017 at 3:01
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.