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

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?

• Please give me a practical example where fnHybrid fails. – Mr.Wizard Jul 20 '16 at 15:40
• @Mr.Wizard f[10^10, Prime[Range[30]] fails. The output should be a list of length 1147700420. – JungHwan Min Jul 20 '16 at 15:41
• fnHybrid[1*^9, 30] (my function, not yours) returns a list of 114,768,524 numbers in about 15 seconds on my system, but it does take about 12GB RAM. I'll see if I can reduce that. – Mr.Wizard Jul 20 '16 at 15:46
• I think it should be possible to do this memory efficiently in blocks but I can't seem to think clearly about it at the moment and I need to get some other things done. – Mr.Wizard Jul 20 '16 at 16:21

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.