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 initiate a counter for the next step.

  ArrayList<Long> list = new ArrayList<Long>(10000);
  long[] counters = new long[1002];
  long number = -1;
  int active_counter = 3;
  boolean removed;
  counters[active_counter] = 1;
  int total_numbers = 1;
  
  while (total_numbers <= 1000) {
      number += 2;
      removed = false;
      for (int i = 3; i <= active_counter; i++) {
          if ((counters[i] % i) == 0) {
              removed = true;
              if (i == active_counter) {
                  active_counter++;
                  counters[active_counter] = i;
              }
              counters[i]++;
              break;
          }
          counters[i]++;
      }
      if (!removed) {
          list.add(number);
          total_numbers++;
      }
  }
  

Answer 1

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

Answer 2

No this problem is not NP hard...

I have the intuition it is O(n^2), and the link proove it:

Let F(n) = number of terms <= n. Andersson, improving results of Brun,
shows that F(n) = 2 sqrt(n/Pi) + O(n^(1/6)). Hence a(n) grows like Pi n^2 / 4.

It think O(n^2) should not be give 15s for n = 10000. Yes there is something not correct :(

Edit :

I measured the number of access to counters (for n = 10000)to get a rough idea of the complexity and I have

 F = 1305646150
 F/n^2 = 13.05...

Your algorithm is between O(n^2) and O(n^2*(logn)) so you are doing things right.... :)