That's doable but you have to process a lot of traffic from the clients because the client would have to send all the answers it has calculated.
Do exactly what bitcoin does: You send a random prefix and require the client to find a random suffix so that hash(prefix+suffix) ends with, say 4 zeros.
Do exactly what bitcoin does: You send a random prefix and require the client to find a random suffix so that hash(prefix+suffix) ends with, say 4 zeros.