Intrinsically useful proof-of-work using Mersenne or Fermat numbers factorization. Could it be possible? I was reading this question and got myself thinking - why can't a crypto-currency use as proof-of-work a difficult problem that has value outside of the network? I understand the effort to produce all those hashes is not completely "useless", but still it seems like too much electricity consumption just to secure a crypto-currency - a proof-of-work that could produce a valuable by-product would be much appreciated, I think.

So I was thinking, what problems could there be if proof-of-work were, say, the factorization of Mersenne or Fermat numbers? Validating a number's factorization is relatively easy, compared to looking for the factors. And a crypto-currency based on it could give an big bonus to finding a Mersenne prime, and a mega-enormous bonus should a miner find a new Fermat prime (assuming there are some more), for these are intrinsically valuable even though validating the discovery would also be incredibly heavy, computationally speaking...

Appart from the obvious problem of difficulty being uncontrollable and going always up, (might be solved by allowing less profitable blocks be mined using another proof-of-work), I thought of the case where a country gets disconnected from the rest of the Internet: In current bitcoin this means coins mined there during the disconnection are lost after the country's reconnected, and any merchant accepting those locally-mined coins will lose their money.

In a system aiming to have a useful by-product as proof of work, all discovered factorizations should get eventually accepted, even if they were mined in such isolated conditions or were initially included in a blockchain that happened not to be the longest - unless some other miner discovered them independently and included them in a longer blockchain. 

But then I realized this system could mean miners could attempt using this proof in more than one blockchain - I guess this would open the door for some types of fraud. 

Could it also lower difficulty for double spending attacks? What other problems could arise in a system of this type? Are they intrinsically unsolvable?

The same could be said of using protein-folding, or analyzing SETI@home packages as proof of work...
How would solving these problems secure the network? Miners are rewarded for the proof of work they do because the specific proof of work they do -- hashing block headers -- in fact secures the system. Solving other problems doesn't secure the currency. If you want to pay people for doing work, you certainly can. But don't at all confuse it with the proof-of-work that crypto-currencies use to solve the double spend problem -- that must be the actual proof-of-work that actually solves the double spend problem.

The point is that the block hashes are tied to a specific block and to specific transactions in that block. The proof of work cannot be severed from the block header and the transactions. Thus the proof of work secures that block header and those transaction. Factorization of Mersenne numbers isn't tied to a specific block or set of transactions, so it does not secure the block chain.