Eliminar todo (k+1) th restantes elemento k-ésimo paso de los números naturales

Question

En los números naturales de la serie, hemos de eliminar hasta el 2º elemento en la 1ª pasada. A continuación, en el resto de los elementos, quitar cada 3er elemento en el segundo paso. A continuación, en el k-ésimo paso, quitar todos (k+1)ésimo elemento de los elementos restantes.

La serie se ve como esto

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, ...

Después de la 1ª pasada(después de la eliminación de todos los 2º elemento),

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, ...

Después de la 2ª pasada,(después de la eliminación de todos los 3er elemento),

1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ...

Después de la 3ª pasar,(después de la eliminación de todos los 4to elemento),

1, 3, 7, 13, 15, 19, 25, 27, ...

Así que, después de infinidad de paso, se convertirá en

1, 3, 7, 13, 19, 27, 39, 49, 63, 79, ...

Esta serie es también llamado Flavio-Josefo tamiz.

La solución para esto, para encontrar la 6ª elemento en la serie:

• hacer 6^2 = 36
• ir a un múltiplo de 5 que da 35
• luego, hacia abajo, a un múltiplo de 4 = 32
• luego, hacia abajo, a un múltiplo de 3 = 30
• luego, hacia abajo, a un múltiplo de 2 = 28
• luego, hacia abajo, a un múltiplo de 1 = 27
• y así, el 6 de número de la suerte es de 27.

Aunque funciona, no me voy a la comprensión de cómo funciona la solución ?

Un programa en C para esto es,

int calc(int n)
{
   if (n == 1) return 1;
   return calc_rec(n*n, n-1);
}

int calc_rec(int nu, int level)
{
   int tmp;
   if (level == 1) return (nu-1);
   tmp = nu % level;
   return calc_rec(nu - (tmp ? tmp : level), level-1);
}

El enlace explicando esto http://oeis.org/A000960

Answer 1

Primero de todo, el algoritmo que se describe tiene para todas las posiciones, no sólo para el $6^{th}$ (no sé si usted quiere que, pero tuve que convencerme de ello).

Vamos a introducir una notación. La posición de ellos el número de $n$ después de la $k^{th}$ paso se denota por a $[n]_k$, donde puedo restringir a mí mismo sólo para los $n$ que sobrevivir hasta el final de la secuencia. Para realizar la indexación menos confuso puedo elegir el $1^{st}$ paso para no hacer nada. A continuación, el $k^{th}$ paso, de hecho, elimina todos los $k^{th}$ número. A continuación, $[n]_1=n$ y para las grandes $k$ tenemos $[n]_k=[n]_{k+1}$, es decir, las posiciones se estabiliza. La posición final puede ser escrito como $[n]_\infty$. E. g. $[27]_6=[27]_\infty=6$.

¿Cómo llegamos a $[n]_k$ $[n]_{k+1}$en general? La fórmula es $$[n]_{k+1}=[n]_k-\lfloor\frac{[n]_k}{k+1}\rfloor.$$

Háganos de convencernos a nosotros mismos de esta fórmula: $[27]_1=27$ y

$$[27]_2=27-\lfloor\frac{27}{2}\rfloor=14$$

La idea es que nos tiramos una cierta cantidad de números más pequeños, es decir cada $(k+1)^{st}$ que equivale precisamente a $\lfloor\frac{[n]_k}{k+1}\rfloor$ números.

Entonces, ¿cómo podemos revertir este proceso? En nuestro ejemplo nos da $[n]_\infty=[n]_6=6$ y quieres encontrar $n=27$.

Yendo un paso atrás significa que queremos encontrar $x=[n]_5$ tal que

$$x-\lfloor\frac x6\rfloor=6$$

o, equivalentemente,

$$\lfloor\frac x6\rfloor=x-6$$

Si multiplicamos esto por $6$ (aquí es donde la cuadratura entra en juego) nos encontramos con

$$6\lfloor\frac x6\rfloor=6x-6^2$$

El lado izquierdo es entonces casi $x$ y casi en ese sentido que es ligeramente más pequeño tal que la ecuación tiene un número entero de la solución. Escribo esto como

$$x-?=6x-6^2,$$

donde el signo de interrogación indica "ligeramente maller". Mover todo a su alrededor nos da

$$5x=6^2-?.$$

Ahora recordemos que el signo de interrogación es el número más pequeño de tal manera que tenemos un entero solución, yo.e bajamos de $6^2$ a un número que es divisible por $5$, namley 35.

Si repetimos este paso vamos a tener una muy similar resultado que da

$$4[n]_4=35-?,$$

así que bajamos al siguiente número más pequeño que es divisible por 4 y así sucesivamente. Terminamos con

$$1[n]_1=28-?=27.$$

Este razonamiento funciona perfectamente para todos los puntos de partida.