28 votos

¿Esta secuencia siempre termina o entra en un ciclo?

He estado jugueteando con el recursiva secuencia definida de la siguiente manera:

$$\begin{equation} f_n=\begin{cases} a, & n=1.\\ b, & n=2.\\ c, & n=3.\\ f_{n-1}f_{n-2}f_{n-3} \mod[f_{n-1}+f_{n-2}+f_{n-3}], & n>3. \end{casos} \end{equation}$$

Y no importa mi inicial opciones de enteros positivos $a,b,c$, parece $ \{ f_n \}$ siempre termina (tres ceros consecutivos) o entra en un ciclo. Por ejemplo, si $a=12,b=12,c=9$, entonces la secuencia se vuelve $12,12,9, 9,12,$ $12\dots$

Mi pregunta: ¿podemos demostrar (o refutar) que para cualquier enteros positivos $a,b,c$, la secuencia de $\{ f_n\}$ va a terminar siempre (tres ceros consecutivos) o entrar en un ciclo?


Más observaciones importantes en las comillas.

(Dec. 27) Nota 1.1: aparece (aunque no he probado) que mi conjetura es verdadera para el más simple secuencia recursiva

$$\begin{equation} f_n=\begin{cases} a, & n=1.\\ b, & n=2.\\ f_{n-1}f_{n-2} \mod[f_{n-1}+f_{n-2}], & n>2. \end{casos} \end{equation}$$

Tal vez este sería un mejor punto de partida. De ahora en adelante, sólo voy a estar refiriéndose a la anterior.

(Dec. 28) Nota 1.2: Si $f_n=f_{n-1}$ y es impar, entonces $f_k=f_n$ para todos los $k>n$. Si $f_n=f_{n-1}$ , e incluso, la secuencia de terminar. Esto puede ser demostrado de forma sencilla.

(Dec. 28) Nota 1.3: suponemos que si $a$ es impar y $b>a+1$ es incluso, la secuencia termina siempre. También, si $a$ es incluso y $b>a+1$ es impar, la secuencia nunca termina.

(Dec. 28) Nota 1.4: la secuencia alcanza el ciclo de $\dots 5,7,11,5,7,11\dots$ para la selección de $a,b.$ Algunos pares de $(a,b)$ para que $f_n$ entra en el ciclo de $\dots 5,7,11 \dots$ se $(3,5), (5,7), (7,11),$ $(7,3),(35,11),(44,13).$ probablemente Hay infinitamente muchos pares de $(a,b)$ para que esta se produce. La frecuencia con la que veo a $5,7,11$ es probablemente debido a mi relativamente pequeñas decisiones de los números enteros. Me pregunto cuál es el mínimo de $X+Y+Z > 3$ es, donde $X,Y,Z$ es un ciclo, finalmente, llegó por la función.

Me pregunto si hay arbitrariamente largas secuencias de números que esta relación de recurrencia sería ciclo a través de ciertos inicial $a,b$. No he encontrado ninguna ciclos de más de tres términos, a pesar de $5,7,11$ no es el único de tres períodos del ciclo que he encontrado. Para $(a,b) = (7,111111101)$, la secuencia final llega el ciclo de $8496495, 3641355, 6068925$. Si tenemos $(a,b) = (6, 99)$, la secuencia alcanza una longitud diferente-$3$ ciclo.

(Dec. 28) Nota 1.5: casi siempre, parece que cuando la $f_n$ no termina, las repetidas términos son múltiplos de $5$. Algunas excepciones son la $\{ f_n \}^{(9,66)}$, $\{ f_n \}^{(6,99)}$, e $\{ f_n \}^{(3,11)}$, donde $\{ f_n \}^{(x,y)}$ es la secuencia generada por $a=x,b=y$.

(Dec. 28) Nota 1.6: suponemos $5,7,11$ son los únicos números primos que aparecen en una clara ciclo (ver Def. 1.1). De hecho, puede incluso darse el caso de que $5,7,11$ es la única distintas ciclo con los números primos.

(Dec. 29) Observación 1.7: probablemente debería estado lo que los 'ciclos' a que me refiero son.

Definición 1.1: $\{ f_n \}$ se dice que para entrar en el ciclo de $X,Y,Z$ si por alguna $k>0$ tenemos $f_{k+3n} = X, f_{k+3n+1} =Y$, e $f_{k+3n+2} = Z$ para todos los enteros $n \geq 0$.

Definición 1.2: Un ciclo que se dice ser no-constante si $X,Y,Z$ no son todos iguales. Del mismo modo, un ciclo que se dice ser distinta si $X \neq Y \neq Z$.

(Dec. 29) Observación 1.8: parece Que no todos los enteros positivos es parte de una distinta ciclo (ver Def. 1.2) Que es, hay algunos (de hecho, muchos) enteros para que, independientemente de nuestra elección de números enteros $a,b > 0$, la secuencia de $\{ f_n \}^{(a,b)}$ no va a entrar en una clara ciclo con el entero. No estoy seguro de si lo mismo es cierto para los no-constante de ciclos. Para la constante de ciclos, esto es trivialmente no es el caso.

3voto

Matta Puntos 169

Esto no es una respuesta completa, sólo mis observaciones.

En resumen, que he dividido el "simple" recursividad en "reducir" y "corto" de los patrones.

Para la inicial de la recursividad, sólo he cálculos como todo parece mucho más caótico.


Las definiciones y pregunta

Deje $(a,b)$ e $(a,b,c)$ ser punto de partida para su recursiones (por $n=1,2$ e $n=1,2,3$).

Escribimos $f_n=f_n(a,b)$ de la recursividad $f_n=f_{n-1}f_{n-2} \bmod[f_{n-1}+f_{n-2}],n\gt 2$.

Escribimos $f_n=f_n(a,b,c)$ para $f_n=f_{n-1}f_{n-2}f_{n-3} \bmod[f_{n-1}+f_{n-2}+f_{n-3}],n\gt 3$.

Si no existe $n_0$ tal que $\forall n\ge n_0,f_n\in F$, escribimos $f_n\to F$, donde $F$ es una tupla (conjunto ordenado) que representa un ciclo. En este caso, decimos que la $f_n$ converge a $F$.

Además, especialmente definen $0\pmod 0:=0$ así "ceros consecutivos" (secuencia termina) pueden ahora ser tratados como un ciclo de $F_0=(0)=0$ (si $F$ tiene un solo elemento, se puede escribir como un número en su lugar).

Su pregunta ahora es:

No $f_n$ siempre converge a algún ciclo de $F$?

Si por alguna $n_0$ tenemos que $\forall n\ge n_0$, $f_n(a_1,b_1)= f_{n-n_0+1}(a_2,b_2)$, entonces podemos decir que el patrón (condiciones iniciales) $(a_1,b_1)$ convergen para el patrón (secuencia dada por) $(a_2,b_2)$.

Así que tenemos que demostrar que todas las secuencias, ya sea converge a algunos $F$ o a algún otro convergencia de la secuencia.



Sobre el "simple" $f_n(a,b)$ función recursiva

Demostrando que el "simple" recursiva secuencia $f_n=f_n(a,b)$ termina siempre parece posible, pero difícil.

Yo reclamo que, cada par de condiciones iniciales $(a,b)$ ya sea converge en la "disminución de patrón", o converge en un número finito de pasos, siguiendo uno de los "patrones cortos".

El "descender" son secuencias que podrían ampliarse a tener arbitrariamente grande, $n_0$, pero todavía convergen para algunos $F$. De lo contrario, tenemos el "corto de patrón" de secuencias que convergen en la mayoría de los $n_0\le n_0^{\text{max}}$ pasos, para algunas constantes $n_0^{\text{max}}$.

Yo reclamo el "descender" se da por estas tres familias de condiciones de partida:

$$\begin{array}{} f_n(6k+0,6k-6)\to 0, & n_0=k+1, & \text{(Ends as: %#%#%)}\\ f_n(6k+2,6k-4)\to 0, & n_0=k+5, & \text{(Ends as: %#%#%)}\\ f_n(6k+4,6k-2)\to 0, & n_0=k+3, & \text{(Ends as: %#%#%)}\\ \end{array}$$

Donde $...,12,6,0.$ es un entero positivo.

En otras palabras, afirmo que la $...,14,8,2,6,4,4,0.$ puede ser arbitrariamente grande, si y sólo si la secuencia de $...,16,10,4,12,0.$ pertenece a la "disminución de patrón" o converge en él. De lo contrario, cualquiera pertenece o converge a uno de los "patrones cortos" en la mayoría de los $k\ge2$ pasos.

Esta afirmación implica que $n_0$ siempre converge en un número finito de pasos $f_n(a,b)$.

Esta afirmación se verifica para todos los posibles pares de $n_0^{\text{max}}\lt\infty$ tal que $f_n(a,b)$, hasta ahora.

El registro de los disyuntores de los más largos de "patrones cortos", que se han observado hasta el momento, son:

$$\begin{array}{} f_n(1,1) & \to1, & n_0=2\\ f_n(1,2) & \to0, & n_0=4\\ f_n(2,1) & \to0, & n_0=5\\ f_n(3,2) & \to0, & n_0=6\\ f_n(3,4) & \to3, & n_0=7\\ f_n(2,9) & \to95, & n_0=14\\ f_n(11,2) & \to95, & n_0=15\\ f_n(12,19) & \to\{7,11,5\}, & n_0=17\\ f_n(21,8) & \to\{7,11,5\}, & n_0=20\\ f_n(24,23) & \to\{7,11,5\}, & n_0=21\\ f_n(16,27) & \to15, & n_0=23\\ f_n(29,13) & \to\{7,11,5\}, & n_0=25\\ f_n(7,32) & \to\{7,11,5\}, & n_0=27\\ f_n(28,37) & \to\{7,11,5\}, & n_0=38\\ f_n(9,52) & \to855, & n_0=59\\ f_n(57,124) & \to855, & n_0=61\\ f_n(126,113) & \to855, & n_0=77\\ f_n(145,126) & \to855, & n_0=78\\ f_n(305,261) & \to855, & n_0=79\\ f_n(948,889) & \to455, & n_0=80\\ f_n(350,1073) & \to855, & n_0=81\\ f_n(1159,1106) & \to6399, & n_0=85\\ f_n(157,1241) & \to8775, & n_0=93\\ f_n(942,1387) & \to54675, & n_0=99\\ &\dots& \end{array}$$

Que es, hasta el momento, $n_0$.

Un problema potencial podría ser que, en el "descender" es incompleta.

Es decir, hay más secuencias que podría haber arbitrariamente grande, $(a,b)$, otras de las secuencias que convergen en una de las tres familias definido en "la disminución de patrón"?

Suponiendo que no hay tal problema, el problema principal es la caracterización de todos los "patrones cortos", que se ve difícil.

En primer lugar, aquí están algunas de las conclusiones a empezar con:

  • Podemos suponer $a,b\le 2000$ ya que no es difícil ver que:

$$ f_n(a,a)\a\begin{cases}0 & (n_0=3), & 2\mid a \\a & (n_0=1), & 2\not\mid a \end{casos} $$

  • También podemos suponer $n_0^{\text{max}}\ge 99$ ya que no es difícil ver que:

$$ f_n(1,b)\a \begin{cases} 0 & (n_0=4), & 2\mid b \\ b & (n_0=2), & 2\not\mid b \end{casos} $$ $$ f_n(a,1)\a \begin{cases} 0 & (n_0=5), & 2\mid a \\ a & (n_0=3), & 2\not\mid a \end{casos} $$

  • Si $n_0(k)\gt n_0^{\text{max}}$ a continuación, supongamos $a\ne b$ es impar, y si $a,b\ge 2$ a continuación, supongamos $a=2$ es impar, ya que:

$$\begin{array}{} f(2,2k)\to 0, & (n_0=5) \\ f(2k,2)\to 0, & (n_0=6) \\ \end{array}$$

  • Suponga $b$ no son soluciones a "$b=2$", desde entonces, $a$.

Buscando en la última hipótesis, continuando a intentar caracterizar "patrones cortos" a través de tales ecuaciones $a,b$ se ve como una espiral interminable de problemas.

En cambio, las formas alternativas son necesarios para encontrar y probar $0=ab\bmod(a+b)$ y el resto de la reclamación.

Esto me recuerda más y más de la conjetura de Collatz. En otras palabras, esta repetición puede ser tan duro como ese famoso sin resolver la conjetura.

No lineal de las recidivas son generalmente caótico. Aún más, la recurrencia dependiendo del modulo operación no ayuda en absoluto.



Acerca de la $f_n(a,b)\to0, (n_0=3)$ función recursiva

Tratando de caracterizar los patrones de aquí parece demasiado duro. Incluso restringir sólo a $(x_{i}\cdot x_{i+1})\bmod (x_{i}+x_{i+1})=x_{i+2}$ secuencias, yo no estoy viendo ningún útil de las estructuras.

He computacionalmente examinado las condiciones de arranque $n_0^{\text{max}}$. Los elementos de $f_n(a,b,c)$ pueden ser grandes, pero parece que tienen un montón de pequeños factores. Por lo tanto, voy a escribir de ellos en términos de su descomposición en factores primos.

Parece $f_n(1,1,c),c\in\mathbb N$ podría ser arbitrariamente grande, así que he recopilado en la tabla de registro de $(1,1,c),c\in\mathbb N$'s $F$:

$$\begin{array}{ccl} (a,b,c) & n_0 & F \\ (1,1,1) & 1& \left(\begin{array}{}1\end{array}\right)\\ (1,1,2) & 6& \left(\begin{array}{}0\end{array}\right)\\ (1,1,3) & 8& \left(\begin{array}{}2\end{array}\right)\\ (1,1,4) & 9& \left(\begin{array}{}16\end{array}\right)\\ (1,1,5) & 10& \left(\begin{array}{}0\end{array}\right)\\ (1,1,8) & 19& \left(\begin{array}{}0\end{array}\right)\\ (1,1,9) & 143& \left(\begin{array}{}2^{33}\cdot5^2,\\2^{33}\cdot5^2,\\2^{31}\cdot5^2\cdot13,\\2^{31}\cdot5^2\cdot19\end{array}\right)\\ (1,1,18) y 493& \left(\begin{array}{}2^{73}\cdot5^3\cdot7^2\cdot11^2,\\2^{71}\cdot5^3\cdot7^3\cdot11^2,\\2^{70}\cdot5^4\cdot7^2\cdot11^2,\\2^{70}\cdot5^4\cdot7^2\cdot11^2\end{array}\right)\\ (1,1,73) & 1169& \left(\begin{array}{}2^{183}\cdot5^{13}\cdot7^{9}\cdot11^{6}\cdot13^{1}\cdot17^{2}\end{array}\right)\\ (1,1,128) & 4351& \left(\begin{array}{}2^{685}\cdot5^{83}\cdot7^{35}\cdot11^{6}\cdot13^{1}\cdot17^{2}\cdot19^{2}\cdot23^{2}\end{array}\right)\\ (1,1,877) & 5529& \left(\begin{array}{}2^{800}\cdot5^{87}\cdot7^{42}\cdot11^{13}\cdot13^{9}\cdot17^{1}\cdot19^{6}\cdot83^{1}\end{array}\right)\\ (1,1,1774) & 8637& \left(\begin{array}{}2^{1298}\cdot5^{140}\cdot7^{59}\cdot11^{20}\cdot13^{9}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1},\\2^{1298}\cdot5^{140}\cdot7^{59}\cdot11^{20}\cdot13^{9}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1},\\2^{1298}\cdot5^{140}\cdot7^{58}\cdot11^{20}\cdot13^{10}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1},\\2^{1298}\cdot5^{142}\cdot7^{58}\cdot11^{20}\cdot13^{9}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1},\\2^{1298}\cdot5^{142}\cdot7^{58}\cdot11^{20}\cdot13^{9}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1}\end{array}\right)\\ \dots & \dots & \dots \end{array}$$

Otra observación es que los ciclos parecen ser capaces de ser de la longitud arbitraria así. Por ejemplo, $n_0$ converge a un ciclo de $n_0$ de $(1,1,c)$ elementos (en $f_n(1,1,7618)$):

$$\left(\begin{array}{l} 2^{106}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{2}\cdot19^{1},\\ 2^{106}\cdot5^{14}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{2},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{2}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{14}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{2},\\ 2^{109}\cdot5^{13}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{108}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{2}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1}\cdot61^{1},\\ 2^{112}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{107}\cdot5^{13}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{14}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{108}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{109}\cdot5^{13}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{14}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{2},\\ 2^{108}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1}\cdot31^{1} \end{array}\right)$$

Incluso si sólo observamos $F$'s tal que $32$, la $n_0=556$'s todavía parecen crecer de forma arbitraria.

Por ejemplo, $c$ converge a $f_n(1,1,c)\to 0$ después $n_0$ pasos.

Lo que es peor en comparación con el "simple" recursividad, es que aquí el "descender", si es que existe, no se ve fácil.

3voto

freethinker Puntos 283

Creo que puede haber ciclos de cualquier longitud impar.
Tome $2n+1$ impares primos $p_k$, para que cualquier $n$ de ellos tienen una suma menor que la de los otros $n+1$.
Deje $a_i = p_i-p_{i+1}+p_{i+2}-....+p_{i-1}$, donde el índice se toma de forma cíclica. A continuación, $a_i+a_{i+1}=2p_i$, y todas las $a_i$ son impares.
Deje $N$ ser un número impar para que $Na_ia_{i+1}=a_{i+2}\pmod{a_i+a_{i+1}}$. Es que eso es posible por el Teorema del Resto Chino.
Luego tomar los números de $\{Na_i\}$ como el ciclo.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X