The only way to reduce this constant would be to find a property satisfied with differenties probabilities in 2 sets:

the set of the keys stored (Space)
the set of the keys generated (Time)

For example, if you have to work in a 2^40 interval,

usually you have to precompute 2^20 keys to store (space)
and 2^20 keys at run time (time)
then 2^20 * 2^20 = 2^40

now image you find a interval of 2^20 keys where a certain property occurs with probability 1/4 while the same property occurs with probability 1/2 in the rest  of the space (example: points with coordinates X lower than 0.5 * 2^256)

you can store  2^20/2^2 = 2^18 keys, only the keys that satisfy such a property,

and then you need to generate 2^20 keys * 2 = 2^21 keys (on average you need to generate 2 keys at each step, because only 1 of 2 satisfies the property).

So: 2^18 (space) x 2^21 (time) = 2^39

But you have to find such property.