¿Cómo saber si un número concreto sobrevivirá en este tamiz?

Question

Me preguntaron esto en una entrevista.

Tenemos personas numeradas del uno al infinito: $$1, 2, 3, 4, 5, 6, 7, 8, \dotsc\,.$$ En la primera pasada cada 2 nd persona es asesinada, por lo que tenemos $$1, 3, 5, 7, 9, 11,\dotsc$$ restante. En la siguiente pasada cada 3 rd persona restante en la muerte. Ahora tenemos: $$1, 3, 7, 9, 13, \dotsc\,.$$ Esto sigue y sigue. Teniendo en cuenta su número en la fila tenemos que decir si la persona sobrevivió.

No se me ocurrió nada mejor que una solución de fuerza bruta. Me dijeron específicamente que usara la programación, pero las ideas basadas en las matemáticas también son bienvenidas. La solución de fuerza bruta era tener una matriz booleana de tamaño $N$ y $\log N$ pases para todos $N$ para marcar cada $k$ th elemento no marcado verdadero. Si $N$ se marca devuelve false si no al final devuelve true.

Answer 1

Toma el número, y si es divisible por 2: muerto. Si no, resta el número de elementos anteriores a él que fueron eliminados (1/2 del número). Si es divisible por 3: muerto. Si no, resta el número de elementos anteriores que se han eliminado (1/3 del número). Una vez que el número es menor que el número por el que se divide, es seguro.

El truco está en darse cuenta de que no es necesario conservar el valor original, sólo su lugar en la secuencia.

Código de ejemplo (C++):

int main() {
    std::cout << "Enter number to test: ";
    std::cin >> n;
    m = n;
    for (i = 2; i < n; i++) {
        if (m % i == 0) {
            std::cout << "\n DEAD\n";
            break;
        }
        else if (m < i) {
            std::cout << "\n Congratulations.  You live. \n";
            break;
        }
        else {
            m = m - m / i;
        }
    }
    std::cin.get();
    std::cin.ignore();
}

EDIT: Incluido el código para mayor claridad (y ya que la pregunta original mencionaba una respuesta de programación)

Answer 2

Esto es OEIS A000960 El tamiz de Flavio Josefo. Se han dado algunos enfoques. Una de ellas es obtener el $n^{th}$ el término comienza con $n^2$ y sucesivamente bajar hasta el mayor múltiplo de $n-1, n-2,$ etc., menor que su número actual: $121, 120, 117, 112, 105, 102, 100, 96, 93, 92, 91$ Así que $a(11) = 91,$ de bajar a múltiplos de $10, 9, ..., 1. $

La serie de números supervivientes comienza $$1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, 207, 223, 253, 289$$

Answer 3

No necesitas una gran matriz booleana para comprobar si un solo número sobrevive. Basta con iterar sobre las distancias de muerte y llevar la cuenta del índice actual del número hasta que la distancia de muerte supere ese índice.

bool Survives(int n) {
   for (int stepsize = 2; ; stepsize++) {
      if (stepsize > n) return true;
      if (n % stepsize == 0) return false;
      n -= n/stepsize;
   }
}

Tenga en cuenta que los grandes $n$ convertir aproximadamente en $n\cdot(1-\frac12)(1-\frac13)(1-\frac14)\cdots (1-\frac1s)=\frac ns$ después de ejecutar todos los tamaños de paso hasta $s$ . Por lo tanto, ejecutaremos como máximo $\approx \sqrt n$ en el código anterior.