Generating a very large list of integers not divisible by a set of primes

Question

I have read (58520), but the solutions there do not work when using a large maximum value because they rely on Range. For example, ByteCount[Range[10^9]] yields 8000000144(8GB). Plus, I would be repeating that operation several thousand times, so memory efficiency is necessary.

If the set of primes only consists of one prime, I could use the following:

f[max_, prime_] := Flatten[Range[Range[prime - 1], max, prime]]

This solution does not generate all numbers from 1 to max, thus saving some memory (though not much because the resulting list is only about 1 / prime shorter than Range[max]).

I have created the following solution, but it has a problem:

f[max_, primes_List] := 
  Block[{y = Range[Min[max, Times @@ primes]]}, 
   Scan[(y[[# ;; ;; #]] = Nothing) &, primes]; 
   If[max > Times @@ primes, Flatten[Range[y, max, Times @@ primes]], 
    y]];

The problem is that it may attempt to generate Range[max], which is undesirable.

What are some memory efficient ways to create a list of integers that are not divisible by a set of primes?

Answer 1

Here is a block-based modification of the first method in my answer to the earlier question:

fnBlock[x1_, x2_, primes_List] := 
   Fold[
     # ~Complement~ Range[x1 + #2 - Mod[x1, #2, 1], x2, #2] &,
     Range[x1, x2],
     primes
   ]

fnMem[x_Integer, n_Integer, block_: 1*^6] :=
  With[{pr = Prime @ Range @ n}, 
    Join @@ Table[
      fnBlock[1 + i block, Min[x, (i + 1) block], pr],
      {i, 0, ⌊x/block⌋}]
  ] ~Monitor~ i

Test with the default block length of one million:

fnMem[1*^9, 30] // Length // Timing
MaxMemoryUsed[]

{60.0292, 114768524}

1883324160

So this was four times slower than Simon's method but took about one sixth the RAM.

A block-based version of Simon's sieve would presumably be faster in this case (small n) but I do not feel like coding that as well right now.

---

It appears that in many cases my use of Fold in fnBlock is counterproductive; it is far slower and doesn't save much memory until n is large, where it is very slow indeed. Here is a simpler alternative:

fnBlock2[x1_, x2_, p_List] :=
  Complement[
    Range[x1, x2],
    Join @@ Range[x1 + p - Mod[x1, p, 1], x2, p]
  ]

As an example here is a performance sample of the original fnBlock:

fnMem[1*^7, 7730] // Length // Timing
MaxMemoryUsed[]

{37.0502, 656850}

87750368

And again using the new fnBlock2 (starting as always with a fresh kernel):

(* using fnBlock2 in place of fnBlock *)

fnMem[1*^7 , 7730] // Length // Timing
MaxMemoryUsed[]

{1.31041, 656850}

124032312

So here it does use ~ 41% more memory but it is also 28 times faster.