Albert van der Horst wrote:

Hm, I'm not sure if this really is a prime marking equivalent. E.g. look at
the task: 4 and 9 are not square-free, but 2 and 3 primes. At least you
need only find all primes up to 2^25 (16MB sieve, please use an optimized
sieve that stops marking at sqrt(N), and remember to insert the 2 in the
list).

While you walk through the list of primes up to 2^25, you can calculate how
many numbers up to 2^50 it takes out as not squarefree, but you need to
calculate how many doubles you had. This can be done by accumulation:

4 takes out 1/4 of the numbers, keep 1/4 in mind.

9 takes out 1/9 of the numbers, but 1/4 of those (1/36) have already been
taken out by 4, so you remember 1/4+1/9*(1-1/4).

25 takes out 1/25 of these numbers, but 1/4 of those have already been taken
out by 4, and 1/9-1/36 by 9.

So you start your accumulator with 0, and each time you find a new prime,
you calculate 1/prime²*(1-acc), which is how many non-square-free numbers
this particular prime² knocks out. Add this number to the accumulator. This
accumulator should converge pretty fast to about 0.4, but you need the
exact number to solve the puzzle. The result is very close to
(1-acc)*2^50 - though the last prime² knocks out only one number (note that
the number should not be different if you use 2^50 or 2^50-1, because 2^50
is knocked out by 2²).

The tricky thing seems to be to do correct rounding, everything else seems
to be O(sqrt(N)), so doable within a minute or less. The good thing
probably is that your representation of the accumulator is already binary,
so the rounding problem probably is a non-issue.

Hope this helps.