Longest coinciding pair of integer sequences known - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T10:12:15Z http://mathoverflow.net/feeds/question/52101 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known Longest coinciding pair of integer sequences known Hans Stricker 2011-01-14T18:37:26Z 2011-07-03T18:04:13Z <p>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.</p> <p>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: <a href="http://mathoverflow.net/questions/38551/equivalence-of-families-of-objects-with-the-same-counting-function/38592#38592" rel="nofollow">Equivalence of families of objects with the same counting function</a>.)</p> <p>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:</p> <blockquote> <p>What is the largest $N$ with two known integer sequences coinciding upto $N$ but differing for an $n > N$?</p> </blockquote> <p>(Can this information be captured from OEIS by an intelligent query?)</p> <p>(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.)</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52106#52106 Answer by Aaron Meyerowitz for Longest coinciding pair of integer sequences known Aaron Meyerowitz 2011-01-14T18:54:02Z 2011-07-02T21:09:56Z <p>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.</p> <p><strong>other answers</strong> 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. </p> <p>For "listed in the OEIS" there are a couple which go from 1 to 99 then skip 100: <a href="http://oeis.org/A033619" rel="nofollow">undulating numbers in base 10</a> and <a href="http://oeis.org/A130734" rel="nofollow">cents you can have in US coins without having change for a dollar</a> (the latter being 1-99 along with $105, 106, 107, 108, 109, 115, 116, 117, 118, 119$.)</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52111#52111 Answer by Qiaochu Yuan for Longest coinciding pair of integer sequences known Qiaochu Yuan 2011-01-14T19:46:50Z 2011-01-14T19:46:50Z <p>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.</p> <p>(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 <a href="http://qchu.wordpress.com/2009/06/07/the-catalan-numbers-regular-languages-and-orthogonal-polynomials/" rel="nofollow">this blog post</a>.)</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52114#52114 Answer by Douglas Zare for Longest coinciding pair of integer sequences known Douglas Zare 2011-01-14T19:53:47Z 2011-01-14T19:53:47Z <p>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 <a href="http://en.wikipedia.org/wiki/Jacobi_symbol" rel="nofollow">Jacobi symbol</a>, 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.</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52115#52115 Answer by Gerry Myerson for Longest coinciding pair of integer sequences known Gerry Myerson 2011-01-14T20:49:47Z 2011-01-14T20:49:47Z <p>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, ....</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52121#52121 Answer by N S for Longest coinciding pair of integer sequences known N S 2011-01-14T21:47:01Z 2011-01-14T21:47:01Z <p>Sorry not enough points to post a comment so had to make this an answer.</p> <p>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). </p> <p>The first term not in $a_n^{(k)}$ is $p_1\cdot p_2 .... \cdot p_{k+1}$. </p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52124#52124 Answer by Fedor Petrov for Longest coinciding pair of integer sequences known Fedor Petrov 2011-01-14T22:11:14Z 2011-01-15T04:40:27Z <p>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).</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52149#52149 Answer by Gottfried Helms for Longest coinciding pair of integer sequences known Gottfried Helms 2011-01-15T05:03:08Z 2011-01-15T05:03:08Z <p>If you define the function $f$ of $h$ and $x$ by<br> $f(1,x) = 1+ x$ and<br> $f(h+1,x) = (1+x) ^ {f(h,x)}$ </p> <p>then the leading coefficents at the powers of <em>x</em> in the formal powerseries up to an index <em>k=1 ... h</em> are equal for <em>f(h+j,x)</em> and <em>j>0</em></p> <p>f(0,x) = 1 + x<br> f(1,x) = 1 + x + x^2 + 1/2*x^3 + 1/3*x^4 + 1/12*x^5 + 3/40*x^6 - ...<br> f(2,x) = 1 + x + x^2 + 3/2*x^3 + 4/3*x^4 + 3/2*x^5 + 53/40*x^6 + ...<br> f(3,x) = 1 + x + x^2 + 3/2*x^3 + 7/3*x^4 + 3*x^5 + 163/40*x^6 + ....<br> f(4,x) = 1 + x + x^2 + 3/2*x^3 + 7/3*x^4 + 4*x^5 + 243/40*x^6 + ... </p> <p>So if we use the coefficients of the powerseries of <em>f(N,x)</em> and <em>f(N+1,x)</em> the sought N can be arbitrarily high .</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52155#52155 Answer by jerr18 for Longest coinciding pair of integer sequences known jerr18 2011-01-15T08:43:40Z 2011-01-15T08:56:48Z <p>I know I am cheating :-)</p> <p>A) $a_n = n + C \lfloor \frac{n}{N}\rfloor$</p> <p>B) Integers of form $x+\prod_{1 \leq k \leq N}{(x-k)}$</p> <p>EDIT: up to $N$ A and B coincide with $\mathbb{N}$ so it is a triple in a sense.</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/52182#52182 Answer by Fedor Petrov for Longest coinciding pair of integer sequences known Fedor Petrov 2011-01-15T19:09:21Z 2011-01-15T19:09:21Z <p>or another cheating example: positive integers and remainders of positive integers modulo 100000000.</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/69408#69408 Answer by KConrad for Longest coinciding pair of integer sequences known KConrad 2011-07-03T17:15:11Z 2011-07-03T17:15:11Z <p>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. </p> <ol> <li><p>For $n \geq 1$, mark $n$ <em>equally spaced</em> 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.</p></li> <li><p>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}$.</p></li> <li><p>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.</p></li> <li><p>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.</p></li> <li><p>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.) </p></li> <li><p>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$.</p></li> <li><p>For each <em>odd</em> 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.</p></li> </ol> <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/52101/longest-coinciding-pair-of-integer-sequences-known/69409#69409 Answer by Laurent Berger for Longest coinciding pair of integer sequences known Laurent Berger 2011-07-03T18:04:13Z 2011-07-03T18:04:13Z <p>There is also, of course, what comes out of the answer which was given to this question:</p> <p><a href="http://mathoverflow.net/questions/11517/computer-algebra-errors" rel="nofollow">http://mathoverflow.net/questions/11517/computer-algebra-errors</a></p>