[math-fun] primes constellations as proof of work

That sounds like an excellent idea. If you ask, for, say N consecutive equispaced primes, for decently large N these become hellishly hard to find -- exponentially hard as a function of N as far as anybody knows -- but once you find them they are trivial to verify and concise to state. If instead of "prime" we asked for "Fermat-test-passing number," then so what? Still seems a perfectly legitimate problem to me.