Sieve optimization

Question

A sequence is created from sequence of natural numbers: ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ``` removing every 2nd number in the 2nd step: ``` 1 3 5 7 9 11 13 15 17 19 21 23 ``` removing every 3rd number in the 3rd step (from previous sequence): ``` 1 3 7 9 13 15 19 21 ``` removing every 4th number in the 4th step (from previous sequence): ``` 1 3 7 13 19 ``` and so forth... Now, we're able to say, that the 4th number of the sequence will be 13. Definition and the right solution for this is here: http://oeis.org/A000960 My task is to find a 1000th member of the sequence. I have written an algorithm for this, but I think it's quite slow (when I try it with 10.000th member it takes about 13 seconds). What it does is: I have `number` which increases by 2 in every step, since we know that there ain't no even numbers. In `counters` array I store indexes for each step. If the number is xth in xth step, i have to remove it, e.g. number 5 in 3rd step. And I initiat…

Accepted Answer

Your link to OEIS gives us some methods for fast calculation (FORMULA etc)

Implementation of the second one:

```
function Flavius(n: Integer): Integer;
var
  m, i: Integer;
begin
  m := n * n;
  for i := n - 1 downto 1 do
    m := (m - 1) - (m - 1) mod i;
  Result := m;
end;
```

P.S. Algorithm is linear (O(n)), and result for n=10000 is 78537769

Sieve optimization

Solution

Problem