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


answered Jul 3 '11 at 17:15

