I haven't seen a good argument for why the blocks need to be prevented from being found in advance or why the proof-of-work has to depend on the contents of a particular new block (rather than simply authenticating that block).
If that requirement is removed, anything that's (1) useful, (2) hard to do, and (3) easy to check could satisfy. Searching for Mersenne primes could work, for example.
That said, the need for proof-of-work comes only from Bitcoin's arbitrary design criterion of full decentralization. It's an academically interesting criterion but one that is almost certainly too expensive in practice for nearly all applications. Eliminate full decentralization and, even if you allow practically useful forms of decentralization, you get a much simpler, easier-to-defend, secure, and cheaper system. Even if Bitcoin plods along under its current speculative bubble, there's very little reason to think it will be able to compete successfully with other payment systems on transaction fees, because in the long term, those transaction fees will need to pay for all the proof of work.
If that requirement is removed, anything that's (1) useful, (2) hard to do, and (3) easy to check could satisfy. Searching for Mersenne primes could work, for example.
That said, the need for proof-of-work comes only from Bitcoin's arbitrary design criterion of full decentralization. It's an academically interesting criterion but one that is almost certainly too expensive in practice for nearly all applications. Eliminate full decentralization and, even if you allow practically useful forms of decentralization, you get a much simpler, easier-to-defend, secure, and cheaper system. Even if Bitcoin plods along under its current speculative bubble, there's very little reason to think it will be able to compete successfully with other payment systems on transaction fees, because in the long term, those transaction fees will need to pay for all the proof of work.