You could also efficiently sieve down the list of candidates with a Bloom filter. Toss all the numbers into a Bloom filter, then scan through them again and cu

You could also efficiently sieve down the list of candidates with a Bloom filter. Toss all the numbers into a Bloom filter, then scan through them again and cull any number, i, for which neither i-k nor i+k are present in the filter. Then run through the (now reduced) remainder with one of the deterministic methods described in the post to get the final answer. Not sure if it'll actually be faster, but it could be worth a try.