Its an interesting idea. Instead of an arbitrary proof of work scheme, why not work on solving a problem that has some utility. as an example (i know its not a good one because this particular example wouldn't work but its just to convey a point) we could be attempting to solve pi. You could prove that you worked hard by discovering a previously undiscovered digit of pi (hence the proof of work) while adding something of value to the scientific community at the same time.