Encontrar el $n$ésimo término de una secuencia particular

Question

Tengo una secuencia en $\mathbb{N}\times\mathbb{N}$ cuyas $n$th término quiero averiguar. De hecho, cualquier información referente a esta secuencia será útil. La secuencia se denota como $(x_1,y_1),(x_2,y_2),(x_3,y_3)\cdots$ y se construye como sigue:

1. Set $x_1=1$.
2. Dado que el $x_i$ ha sido construido deje $y_i=x_i+2i$.
3. Asumiendo $(x_i,y_i)$ ha sido construido definimos $x_{i+1}$ como sigue: Considerar el conjunto múltiple $M$ de todos los números de el tipo de $x_j$ o $y_j$,$1\le j\le i$. Deje $m$ ser el menos número impar en $\mathbb{N}$ que tiene multiplicidad en la mayoría de las $1$$M$. Definir $x_{i+1}=m$.
4. Vaya al paso 2.

Tenga en cuenta que la diferencia de las dos coordenadas, sucesivamente, los rendimientos de los números pares, y todos los números impares se utilizan exactamente dos veces.

Así que los primeros términos son : $(1,3),(1,5),(3,9),(5,13),(7,17),(7,19),(9,23),(11,27),(11,29)\cdots$.

Cualquier ayuda será apreciada.

Answer 1

Antes de Contestar sin la prueba:

$x_n=2\lfloor \frac{n}{\sqrt{2}}-\frac{1}{2}\rfloor+1$ o, equivalentemente,$x_n=$ $n/\sqrt{2}$ redondeado al entero más cercano, se duplicó menos 1. $y_n=x_n+2n$.

No he sido capaz de demostrar esto a pesar de speding bastante tiempo.

Agregado De La Prueba:

La secuencia puede ser de forma equivalente, definido como: $x_1=1,x_2=1$ $n>1$ $x_{n+1} = \left\{\begin{array}{1} x_n+2\text{ if }x_n=x_{n-1}\text{ or }x_n=x_j+2j\text{ for some }j \in \mathbb{N}\\x_n \text{ otherwise}\end{array}\right. $

Utilizamos la inducción para demostrar que $x_n=a_n\equiv2\lfloor \frac{n}{\sqrt{2}}-\frac{1}{2}\rfloor+1$. Las condiciones iniciales tienen como $a_1=a_2=1=x_1=x_2$. Supongamos $a_i=x_i$$i=1,...,n>1$. Vamos a mostrar que el $a_{n+1}=x_{n+1}$. Definir $f(x)=\frac{x}{\sqrt{2}}-\frac{1}{2}$$a_n=2\lfloor f(n) \rfloor+1$.

Deje $f(n)=\frac{n}{\sqrt{2}}-\frac{1}{2}=k+r$ donde $k\in \mathbb{N},0<r<1$. Nota: $a_n=2k+1$ $r$ es irracional.

Considere la posibilidad de $j=\lfloor \frac{n}{\sqrt{2}+1}+\frac{1}{2}\rfloor=\lfloor (\sqrt{2}-1)n+\frac{1}{2}\rfloor=\lfloor 2(\frac{1}{2}+k+r)-n+\frac{1}{2}\rfloor= 2k-n+1+\lfloor2r+\frac{1}{2}\rfloor$. Ahora consideramos 4 exclusivos y exhaustivos de los casos.

Caso 1: $0<r<\frac{1}{4}$.

Tenemos $k-1<k+r-\frac{1}{\sqrt{2}}=f(n-1)<k$$a_{n-1}=2k-1=a_n-2$$k<f(n+1)=k+r+\frac{1}{\sqrt{2}}<k+\frac{1}{4}+\frac{1}{\sqrt{2}}<k+1$$a_{n+1}=2k+1=a_n$. También, $j=2k-n+1$$f(j)=\sqrt{2}k-\frac{n}{\sqrt{2}}+\frac{1}{\sqrt{2}}-\frac{1}{2}=(n-\frac{1}{\sqrt{2}}-r\sqrt{2})-(\frac{1}{2}+k+r)+\frac{1}{\sqrt{2}}-\frac{1}{2}=n-k-1-r(\sqrt{2}+1)$.

El uso de $0<r<\frac{1}{4}$, $\lfloor f(j) \rfloor = n-k-2$ y $\lfloor f(j+1) \rfloor = \lfloor f(j)+\frac{1}{\sqrt{2}} \rfloor = n-k-1$. Es decir,$j+\lfloor f(j) \rfloor = k-1$$(j+1)+\lfloor f(j+1) \rfloor = k+1$. Por lo $\not\exists i \in \mathbb{N}$ tal que $i+\lfloor i \rfloor=k$ o, equivalentemente,$x_i+2i=x_n$. Por definición, $x_{n+1}=x_n=a_n=a_{n+1}$.

Caso 2: $\frac{1}{4}<r<1-\frac{1}{\sqrt{2}}$.

De nuevo, tenemos $k-1<k+r-\frac{1}{\sqrt{2}}=f(n-1)<k$$a_{n-1}=2k-1=a_n-2$$k<f(n+1)=k+r+\frac{1}{\sqrt{2}}<k+1$$a_{n+1}=2k+1=a_n$. Esta vez, $j=2k-n+2$$f(j)=\sqrt{2}k-\frac{n}{\sqrt{2}}+\sqrt{2}-\frac{1}{2}=(n-\frac{1}{\sqrt{2}}-r\sqrt{2})-(\frac{1}{2}+k+r)+\sqrt{2}-\frac{1}{2}=n-k-1+\frac{1}{\sqrt{2}}-r(\sqrt{2}+1)$.

El uso de $\frac{1}{4}<r<1-\frac{1}{\sqrt{2}}$, $\lfloor f(j) \rfloor = n-k-1$ y $\lfloor f(j-1) \rfloor = \lfloor f(j)-\frac{1}{\sqrt{2}} \rfloor = n-k-2$. Es decir,$j+\lfloor f(j) \rfloor = k+1$$(j-1)+\lfloor f(j-1) \rfloor = k-1$. Por lo $\not\exists i \in \mathbb{N}$ tal que $i+\lfloor i \rfloor=k$ o, equivalentemente,$x_i+2i=x_n$. Por definición, $x_{n+1}=x_n=a_n=a_{n+1}$.

Caso 3: $1-\frac{1}{\sqrt{2}}<r<\frac{1}{\sqrt{2}}$.

Tenemos $k-1<k+r-\frac{1}{\sqrt{2}}=f(n-1)<k$$a_{n-1}=2k-1=a_n-2$$k+1<k+r+\frac{1}{\sqrt{2}}=f(n+1)<k+2$$a_{n+1}=2k+3=a_n+2$. Como en el Caso 2, $j=2k-n+2$$f(j)=\sqrt{2}k-\frac{n}{\sqrt{2}}+\sqrt{2}-\frac{1}{2}=(n-\frac{1}{\sqrt{2}}-r\sqrt{2})-(\frac{1}{2}+k+r)+\sqrt{2}-\frac{1}{2}=n-k-1+\frac{1}{\sqrt{2}}-r(\sqrt{2}+1)$.

El uso de $1-\frac{1}{\sqrt{2}}<r<\frac{1}{\sqrt{2}}$, $\lfloor f(j) \rfloor = n-k-2$ por lo $j+\lfloor f(j) \rfloor = k$ o, equivalentemente,$x_j+2j=x_n$. Por definición, $x_{n+1}=x_n+2=a_n+2=a_{n+1}$.

Caso 4: $\frac{1}{\sqrt{2}}<r<1$.

Tenemos $k<k+r-\frac{1}{\sqrt{2}}=f(n-1)<k+1$$a_{n-1}=2k+1=a_n$$k+1<k+r+\frac{1}{\sqrt{2}}=f(n+1)<k+2$$a_{n+1}=2k+3=a_n+2$. Ya, $x_n=a_n=a_{n-1}=x_{n-1}$, por definición, $x_{n+1}=x_n+2=a_n+2=a_{n+1}$.