Apologies if this answer is nitpicky and diverges slightly from the questions intent, but this particular soft question appears to warrant a soft answer.

Implicit in your term "mathcoin" are assumptions that the problem:

- Allows new solutions to be found in regular
*tunable* time intervals,
- Is memory hard so that specialized ASICs cannot speed up the computations, and
- Any significantly faster algorithms represent the sort of dramatic advancement that it'd emerge from across the mathematical community simultaneously and not from a secret project.

Of course, collisions in cryptographic hashed satisfies 1 and 3, while a memory hard cryptographic hash like `scrypt`

or `argon2`

satisfies 2 as well.

Almost all the answers proposed here thus far fail even 1 and maybe all here fail 2. Worse, there are probably no calculations that both pass 3 and represent useful mathematical (resp. scientific) research, at least not for 2 (resp. 10) years.

In short, a naive "mathcoin" as suggested here sounds impossible to do correctly. There might be less naive approaches where perhaps any problem goes and the problem's difficulty is established by previous attempts, but that's actually solving a social problem to achieve 1 with widely varied math problems as simply a source of randomness that defeats ASICs.

As an aside, there are proof-of-useful-work systems that could possibly support a bitcoin like currency without wasting resources, but again they all provide useful social services like file storage (filecoin) or anonymity via onion routing.

**Update 2018:** There is still no evidence of any suitable mathcoin problem but there are seemingly suitable science and engineering problems. Examples:

*Proof-of-moon*: All miners must buy telescope arrays to explore the night sky looking for specific astronomical events. If you find one, then reporting it in a canonical way and hashing the report with a nonce can win a block, with the difficulty possibly adjusted by the event.

*Proof-of-vulnerability*: All miners run advanced static analysis tools on software to discover vulnerabilities in published software. A miner wins the block with the hash specific characteristics of a vulnerability plus a nonce, so once a vulnerability is found the miner will eventually win a block. There are several challenges though: First, you must prevent a vulnerability from being used twice, potentially this could be done by resolving to a particular point in the code, but then projects with more releases become better targets. Second, static analysis tools have false positives, so you might need to test consequences somehow. Third, you'll likely need some sort of proof-of-stake system to permit humans to ultimately arbitrate the vulnerabilities. Forth, you want to tackle closed source software too, so the definition of published becomes tricky. Fifth, developers might get annoyed with vulnerabilities being posted to some blockchain without even attempting to warn them first.

for which we already have a decent algorithmwould you like to see run on some massive computer? This would make it more clear that you are not asking for whatnewcomputational horizons might become feasible from hardware advances, but rather whicholdcomputations are worth extending. Eg, at his retirement ("40 years on") talk, Birch said in 1960 they could barely think of computing with elliptic curves, whilst he fully expected people to routinely compute with motives by 2040. EC computations are still of interest, of course. $\endgroup$ – NAME_IN_CAPS Nov 28 '14 at 0:24