El par de secuencias enteras coincidentes más largo conocido

Question

Hay un número arbitrario de pares de secuencias enteras (de orígenes arbitrarios) que coinciden hasta un $N$ pero difieren para un $n > N$ . Supongo que, entonces, la coincidencia se considerará accidental por defecto, pero puedo estar equivocado al respecto.

No se puede llegar a ninguna conclusión a partir de las coincidencias de secuencias de números enteros a menos que se demuestre que coinciden en todos los casos. $n$ . (Incluso entonces puede que no haya conclusiones sensatas, como he aprendido aquí: Equivalencia de familias de objetos con la misma función de recuento .)

En cualquier caso, es difícil no caer en la trampa de sacar una conclusión cuando $N$ es muy grande. Pero, ¿qué es "muy grande"? De ahí mi pregunta:

¿Cuál es el mayor $N$ con dos que coinciden hasta $N$ pero que difieren para un $n > N$ ?

(¿Puede obtenerse esta información de OEIS mediante una consulta inteligente?)

(Soy consciente de que se pueden definir trivialmente pares de secuencias de números enteros que conincidan para todo $n$ sino una única y arbitrariamente grande. Debe quedar claro que no me interesan esos sino los pares que no se ajustan entre sí de esta manera).

Answer 1

El número de divisiones de $\mathbb{R}^3$ por $k \ge 0$ aviones en posición general comienza 1,2,4,8, luego 15, etc. Para $\mathbb{R}^6$ es 1,2,4,8,16,32,64 y luego 127. En general para $\mathbb{R}^N$ es la suma de los coeficientes binomiales de $\binom{k}{0}$ hasta $\binom{k}{N}$ y por lo tanto concuerda con $2^k$ para los términos 0,1,2, hasta N antes de empezar a decaer.

otras respuestas Por supuesto para prime p, $2^{p-1}=1 \mod{p}$ pero sólo se conocen 2 casos $p=1093$ y $3511$ donde $2^{p-1}=1 \mod{p^2}$ . SO primos y primos con $2^{p-1} \ne 1 \mod{ p^2}$ coinciden para los 182 primeros primos.

Para "listado en la OEIS" hay un par que van del 1 al 99 y luego se saltan el 100: números ondulantes en base 10 y céntimos que puede tener en monedas de EE.UU. sin tener cambio de un dólar (estos últimos son 1-99 junto con $105, 106, 107, 108, 109, 115, 116, 117, 118, 119$ .)

Answer 2

Los enteros Impares positivos $n$ que superan la prueba de primalidad de Euler-Jacobi para basar $2,$ $2^{(n-1)/2} \equiv \big(\frac2n\big) \mod n$ donde RHS es el Símbolo de Jacobi coinciden con los primos Impares hasta la inclusión de $561$ . Por lo tanto, estas secuencias $3, 5, 7, 11, 13, ..., 557, 561, 563, ...$ y $3, 5, 7, 11, 13, ..., 557, 563, ...$ aceptar para $101$ condiciones.

Answer 3

Es un ejemplo conocido: secuencia 1,2,3,5,7,11,13, $\dots$ de números no compuestos coincide con la secuencia de órdenes de grupos simples finitos hasta que aparece 60 (en esta última secuencia).

Answer 4

Hay muchos ejemplos naturales de una secuencia $a_{n,k}$ de dos parámetros tales que $a_{n,k}$ se aproxima a una secuencia $a_n$ como $k \to \infty$ en el sentido de que la primera $k$ términos de $a_n$ y $a_{n,k}$ de acuerdo. Aaron Meyerowitz da uno bueno; otro ejemplo es la secuencia "catalana parcial $C_{n,k}$ de todas las paréntesis que utilizan $n$ pares de paréntesis con profundidad parentética como máximo $k$ . Así que no creo que esta sea la pregunta que querías hacer.

(Un bonito punto en común entre el ejemplo de Aaron Meyerowitz y éste es que para los fijos $k$ las secuencias de aproximación $a_{n,k}$ son regulares, por lo que sus funciones generadoras son racionales. Así que se puede pensar en estas funciones generadoras como "aproximaciones racionales" a la función generadora de $a_n$ que en algunos casos puede obtenerse truncando una expansión de fracción continua. Este es el caso de mi ejemplo; véase esta entrada del blog .)

Answer 5

Un ejemplo posiblemente inmejorable: la secuencia $a(n)$ donde $a(n)$ es la periodicidad de la primera fila de la tabla de Laver basada en el conjunto $\left\lbrace 1,\ldots, 2^n\right\rbrace$ : Los primeros valores son $$1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16,\ldots$$ y luego se queda en $16$ para edades : Randall Dougherty demostró que la primera $n$ para lo cual $a(n)$ puede diferir de $16$ es A(9,A(8,A(8,255))), donde A denota la función de Ackermann, una función recursiva cuyos primeros valores ya son enormes.

Sin embargo, se puede demostrar que la secuencia realmente tiende a infinito bajo algún axioma adicional independiente de los habituales de ZFC.