Números primos de la permutación

Question

Dejemos que $P(n)$ de una secuencia $s(1),s(2),s(3),...$ se obtiene dejando $s(1),...,s(n)$ fijo y permutando cíclicamente cada $n$ términos consecutivos a partir de entonces; aplicar $P(2)$ a $1,2,3,...$ para conseguir $PS(2)$ y, a continuación, aplique $P(3)$ a $PS(2)$ para conseguir $PS(3)$ y, a continuación, aplique $P(4)$ a $PS(3)$ etc. El límite de $PS(n)$ es $a(n)$ ( A057063 ).

La secuencia comienza $$1, 2, 4, 6, 3, 10, 12, 7, 16, 18, 11, 22, 13, 5, 28$$

Algunos ejemplos: $$1,2,(4,3),(6,5),(8,7),(10,9),(12,11),(14,13),(16,15),(18,17)$$ $$1,2,4,(6,5,3),(7,10,8),(12,11,9),(13,16,14),(18,17,15)$$ $$1,2,4,6,(3,7,10,5),(12,11,9,8),(16,14,18,13)$$ $$1,2,4,6,3,(10,5,12,11,7),(8,16,14,18,9)$$

Conjeturo que $a(n)+1$ es primo si y sólo si $a(n)=2(n-1)$ .

¿Hay alguna manera de probarlo?

Answer 1

1. Respuesta a la pregunta.

Reclamación 1. $a(n)=2(n-1)$ si el número $d=a(n)$ se mueve sólo hacia la izquierda (mientras se mueve).

Prueba. En cada movimiento, cada número móvil se desplaza a la derecha o $1$ a la izquierda.

El número $d=a(n)$ llegó a la $n$ posición durante $P(n-1)$ , moviéndose $1$ a la izquierda. Si $d$ se movió hacia la izquierda a través de todos $P(2),\dots, P(n-1)$ , entonces comenzó en la posición $n+(n-2)=2(n-1)$ (así $d=2(n-1)$ ). De lo contrario, se desplazó hacia la izquierda una distancia menor, por lo que fue menor que $2(n-1)$ . $\quad\square$

Reclamación 2. Un número $d$ se mueve sólo hacia la izquierda (mientras se mueve) si $d+1$ es primo.

Prueba. Mientras que $d$ se mueve hacia la izquierda, aparece en la posición $d-i+2$ antes de $P(i)$ . Entonces, en $P(i)$ se desplaza a la derecha si $d-i+2>i$ y $d-i+2\equiv 1\pmod i$ es decir, si $d\equiv -1\pmod i$ y $d+1\geq 2i$ o en otros wirds, $i\mid d+1$ y $(d+1)/i>1$ .

Por lo tanto, si $p\leq d/2$ es el menor divisor primo de $d+1$ , entonces en $P(p)$ el número $d-p+2=(d+1)-(p-1)>p$ se desplaza a la derecha (si no se ha desplazado antes, de hecho, no lo ha hecho). Por lo demás, $d$ es primo, y no puede desplazarse a la derecha. $\quad\square$

Las dos reclamaciones dan el resultado.

2. Prueba de que el arreglo resultante es una permutación.

Fijamos un número $d$ y describir cómo se mueve. Nuestro objetivo es demostrar que sólo se desplaza hacia la derecha un número finito de veces, lo que nos lleva claramente a que $d$ acabará por detenerse.

Dejemos que $a_n$ denotan la posición de $d$ antes de $P(n)$ y poner $b_n=a_n+n-1$ . De manera informal, $b_n-1$ denota una posición desde la que $d$ llegaría a su posición actual moviéndose sólo hacia la izquierda.

Si $d$ se mueve en $P(n)$ tenemos $a_{n+1}=a_n-1$ si $a_n\not\equiv 1\pmod n$ y $a_{n+1}=a_n+n-1$ de lo contrario. Por lo tanto, $b_{n+1}=b_n$ si $n\nmid b_n$ y $b_{n+1}=b_n+n$ en caso contrario (en este último caso llamamos $n$ a crucial ); queremos demostrar que hay un número finito de índices cruciales.

Dejemos que $n<m$ sean dos índices cruciales consecutivos. Poner $c_n=b_n/n$ ; si $c_n=1$ entonces $b_n=n$ y $d$ acaba de parar (y $m$ no existe). En caso contrario, si $c_n>1$ tenemos $b_{n+1}=n(c_n+1)$ y por lo tanto $c_n+1>b_{n+1}/(n+1)\geq b_{n+1}/m=b_m/m=c_m$ . Desde $c_m$ es un número entero, concluimos que $c_m\leq c_n$ .

Numerar todos los índices cruciales como $n_1<n_2<\dots$ ; poner $B_i=b_{n_i}$ y $C_i=c_{n_i}$ . Estas secuencias actúan de la siguiente manera: $$ C_i=B_i/n_i\leq C_{i-1}; \quad B_{i+1}=B_i+n_i=n_i(C_i+1). $$ Así, mientras $C_i$ conserva el valor $k>1$ tenemos $B_{i+1}=B_i\cdot \frac{k+1}k$ . Esto sólo puede ocurrir un número finito de veces si $k>1$ ya que todos los $B_i$ son números enteros.

Así, la secuencia (no creciente) $C_i$ no puede conservar ningún valor $k>1$ indefinidamente, por lo que disminuye de vez en cuando, y finalmente alcanza $1$ , según se desee.