How to tell if a particular number will survive in this sieve?

Question

I was asked this in an interview.

We have people numbered from one to infinity: $$1, 2, 3, 4, 5, 6, 7, 8, \dotsc\,.$$ In first pass every 2^nd person is killed, so we have $$1, 3, 5, 7, 9, 11,\dotsc$$ remaining. In next pass every 3^rd remaining person in killed. Now we have: $$1, 3, 7, 9, 13, \dotsc\,.$$ This goes on and on. Given their number in line we need to tell if the person survived.

I couldn't come up with a better than a brute force solution. I was specifically told to use programming but math based ideas are also welcome. The brute force solution was to have Boolean array of size $N$ and $\log N$ passes for all $N$ elements to mark every $k$^th non marked element true. If $N$ gets marked return false else in the end return true.

Answer 1

Take the number, and if it is divisible by 2: dead. Else subtract the number of elements before it that were deleted (1/2 the number). Divisible by 3: dead. Else subtract the number of elements before it that were deleted (1/3 the number). Once the number is less than the number you are dividing by, it is safe.

The trick is to realize that you don't need to preserve the original value, just its place in the sequence.

Sample code (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: Included code for clarity (and since original question mentioned a programming answer)

Answer 2

You don't need a large boolean array to check whether a single number survives. Simply iterate over the killing distances and keep track of the number's current index until the killing distance exceeds that index.

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

Note that large $n$ turn approximately into $n\cdot(1-\frac12)(1-\frac13)(1-\frac14)\cdots (1-\frac1s)=\frac ns$ after executing all step sizes up to $s$. Hence we will execute at most $\approx \sqrt n$ rounds in the above code.

Answer 3

This is OEIS A000960 Flavius Josephus's sieve. There are some approaches given. One neat one is to get the $n^{th}$ term start with $n^2$ and successively move down to the highest multiple of $n-1, n-2,$ etc., smaller than your current number: $121, 120, 117, 112, 105, 102, 100, 96, 93, 92, 91$, so $a(11) = 91,$ from moving down to multiples of $10, 9, ..., 1. $

The series of surviving numbers starts $$1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, 207, 223, 253, 289$$