Yes, but you should prove that the number of steps is short enough.
Here is some sketch of the proof. After deleting all 2nd numbers we are with $\frac{n}{2}$  numbers, after erasing all 3rd numbers we are with $\frac{2}{3}\cdot \frac{n}{2} = \frac{n}{3}$ numbers, after erasing all 4th numbers we are with $\frac{3}{4}\cdot \frac{n}{3} = \frac{n}{4}$ numbers and so on, after erasing every $k$-th number we are left with $\frac{n}{k}$ numbers, and we stop when $\frac{n}{k} < (k+1)\implies k \approx \sqrt{n}$, so after $O(\sqrt{n})$ steps the algorithm stops.

Edited by author 02.01.2021 20:07

Edited by author 02.01.2021 20:07

Edited by author 02.01.2021 20:09

1 10^9 should be 35682 (apparently? i might be wrong)

If you have a few spare gigabytes of RAM, you can simulate the thing by yourself. Initially we have 1 2 3 ... 10^9, after 1st step 1 3 5 etc (+2 +2 +2 etc), after 2nd step it's 1 3 7 9 13 15 (+2 +4 +2 +4 +2 +4 etc), after 3rd step it's 1 3 7 13 15 19 25 27 31 (+2 +4 +6 +2 +4 +6 +2 +4 +6 etc). Only on 4th step it becomes complicated and loses pattern. So for further simulation, you need 1 array of 10^9 / 2 / 2 + 1 4-byte integers from 3rd step (1 and [+2 +4 +6 cycle]), which is ~1GB, and another ~1GB array to copy elements into.

I also found the sequence on OEIS: https://oeis.org/A000960, but still, i can't quite understand some things. For example:
«To get n-th term, start with n and successively round up to next 2 multiples of n-1, n-2, ..., 1 (compare to Mancala sequence A002491). E.g.: to get 11th term: 11->30->45->56->63->72->80->84->87->90->91; i.e., start with 11, successively round up to next 2 multiples of 10, 9, .., 1. - Paul D. Hanna, Oct 10 2005»
— what is this even? I have a hard time understanding what exactly is done here...

10 18 => 1
666 999 => 6
13 100000 => 354
123456789101112 12345678910111213 => 112837915
1 1000000000 => 35682
1 1000000000000 => 1128378

Edited by author 10.07.2016 18:37