No need to be hopeless about winning one of these! The "easiest" ones to target, I think for the general HN crowd, will be the EFF Cooperative Computing Awards, i.e. finding primes with 100 million and a billion digits. Looking at the winning claim from 2009 (https://www.eff.org/awards/coop/primeclaim-43112609), which was a Mersenne prime with 12M+ digits, I see that it was discovered using an "Dell Optiplex 745 computer with an Intel Core 2 Duo E6600 CPU running at 2.4 GHz" running for about 33 days. Netting the 100M prime should be doable using, e.g. a couple hundred EC2 instances for a couple of weeks.

With current EC2 prices (http://aws.amazon.com/ec2/pricing/) , for $100k one can run a c4.8xlarge instance (36 cores) for 2244 days, so for a comparable time for the 2009 award, you can run (2244/33)x36=2448 cores rather than two. Assuming that's adequate to discover the 100M digit prime, that's a net profit of $50k!

Since no body has done this there must be some significant flaws in the naive analysis above. What are they? What is a rough estimate of how fast the computational load would go up from 10M to 100M to 1B digit prime search?

I think you misread how the previous prime was found:

"4D. The Lucas-Lehmer test began on Sun Jul 20 12:33:46 2008 PDT and concluded on Sat Aug 23 00:29:27 2008 PDT. That's a total of 33 1/2 days. The Dell Optiplex was the only computer used to initially prove this candidate prime. However, the computer was part of GIMPS' "PrimeNet" network of roughly 75,000 computers testing other Mersenne number candidates."

It didnt take one computer 33 days, it took 75,000 computers searching simultaneously to find a prime.

edit: The next largest prime, at 17 million digits, took a further 5 years of searching on a network that has over 100 TFLOP/s of compute power [1].

[1] http://www.mersenne.org/primes/

The choice of a Dell Optiplex business desktop PC for a month-long calculation in 2008 is interesting for historical reasons.

A decade before that, Sun workstations that cost $30k each were used for long-running engineering tests like chip verification, while an Optiplex is less than 10% of that.

Well, in 1998, I was running a dual-processor Dell Optiplex at 400MHz for month-long simulations; it cost $5000 at the time. but yeah, most people around me were buying $25k SGIs that had about half the oomph of my machine. I think that was the year it became clear Intel was going to get enough floating point and cache to be competitive with the RISC UNIX systems.

This is interesting to me. Are there libraries for storing and doing math on floating point numbers with 17+ million digits?

At the bottom there is a list of "solved problems". I was surprised to read,

  Brexit Prize
  by Institute of Economic Affairs

  2013 - 2014

  €100,000
  Find the best plan for a UK exit from the European Union.

I was surprised, because my own personal opinion is that that's a pretty stupid idea (UK exit from the EU). Since I'm a super, super open-minded guy I decided to embetter my worldview and read the paper, since, you know, if it's in company like the "longitudinal prize" then hell, maybe 1) I'm wrong and 2) I'll learn something.

So I looked for the plan. Here it is:

http://www.iea.org.uk/sites/default/files/publications/files...

Folks, this is 15,000 words. That means he got paid $6 per word to write that. I personally skimmed the PDF, didn't find anything that caught my eye or even a point, based on the the abstract or the section titles and the whole framing, and wasn't left with the impression that the author even believed it. Perhaps his 15,000 word PDF won simply because nobody else bothered to put a plan together, not because there's anything great or wortwhile about such a plan.

So forget "lander on mars". Win a prize that consists of a meaty term paper on some stupid proposition. A+ as a term paper, though.

I was surprised with that entry too, however not because of the specifics (UK exit from EU, which I happen to agree with), but rather that it is the only prize with some sort of political outcome. All of the other prizes have some basis in math, science and technology with well defined criteria for winning. A political outcome is almost by definition subjective.

The remit is here (PDF): http://www.iea.org.uk/sites/default/files/Info%20flyer%20for...

The competition wasn't really about whether the UK should go or not, which is the main political part. Rather, the starting point is that a referendum has decided "go", and the competition was to find the best way of extricating the UK from existing institutions/agreements, what should replace them, and how.

However, the remit is very unclear on the criteria used to judge entries.

The commercial value of the solutions to some of these problems are multiple orders of magnitude higher than the prize money.

In that sense, the prize money isn't really much incentive to develop a Tricorder, or a process to remove greenhouse gases.

If the prize was higher then the cost of the solution - then there would likely be no prize (and they would simply spend the money on developing that solution).

The prize money shouldn't be the incentive for these solutions, more of a by-product.

The list is missing the Mprize for mouse longevity, which is still out there, and the Palo Alto Prize for rejuvenation treatments in mammals. Possibly others as well.

They should make it so that people can donate to the prize of their choice to increase the size of the prize. Shouldn't we try to drive the prize $ up in order to create more of an incentive to solve each of these challenges?

Having non-profit collecting crowd-funds for the solutions to the important scientific problems would be great. But I would imagine that for those most capable of solving these problems prizes are not essential, while grants that would allow them to conduct the research in the first place are.

So... Create capable non-profit with goal of crowd-funding important research.

The key innovation would be an investor (venture capitalist?) willing to give out grants themselves, in return for a share of the resulting X-prizes. Then funding the prizes would, through Market Magic™, produce grants.

My guess is except for the prizes with a big material resource need (any space one, for example), this will not make it more likely

Just see the Poincaré conjecture and how who solved it turned down the price

For most of the math prices the solution is a very big and inscrutable collection of mathematical theorems, lemmas, proofs, etc

Luckily, KSP1.0 recently came out to help us with prototyping for the Lunar XPrize.

I wouldn't call the Lunar XPrize an unsolved problem. We have already landed manned vessels on the moon, and have landed and operated rovers on other celestial bodies. The issue is more that we do not care enough to land a rover on the moon.

Of course, if you interpret the challenge as doing it withing a budget of $20,000,000, then it becomes a much more interesting challenge.

Hmmmmmmm..... I wonder what you could get away with if you're ok with having a stupidly low-mass rover, say with the mass of a go-pro.

>>> Create free Android apps to spread reading, writing, and arithmetic skills, and prove their effectiveness over an 18-month period in African pilot communities.

5 prizes of $1M and a grand prize of $10M. That seems quite viable for the HN crowd. However, this is rather subjective compared to other problems. Many other problems are more like true/false.

Still, that's quite interesting and an app, designed for learning, with heavy optimizations on UX seems like a very commercially viable product. Given you have to do the skills of enterprise sales :)

"Registration closed" on that website

This is an interesting mix.

> Google Lunar XPRIZE $20,000,000 Successfully launch, land, and operate a rover on the lunar surface.

That almost reads like a joke. It's going to take an awful lot more than $20,000,000 to accomplish that. The prize money is nearly irrelevant.

> ALS Treatment Prize $1,000,000 Develop a therapy that extends the life of ALS mice by 25%.

I surprised this one hasn't been taken yet.

The Google Lunar XPRIZE already has a bunch of teams making decent progress. The $30 million[0] certainly won't fund the whole trip, but it seems to be a big enough supplement that it is encouraging institutions to give it a serious effort.

That being said, I would love to see the competition and effort if the prize was increased by a factor of at least 25.

[0] http://lunar.xprize.org/

I looked through 2 of these that looked the most interesting to me, and the registration is closed.

Need a way to filter the list to things that you can still register to enter.

Or just build a photo sharing app called Instagram, worth $1 billion.

Yea but out of hundreds of photo sharing apps only one was worth $1 billion.

Well, the odds of finding a prime number with 1,000,000,000 digts are lower by far and you only get $250,000

And thousands of mathematicians!

I'm surprised SpaceX doesn't go for the Lunar prize.

The current plan [1] is for several teams to pool their money and launch together on a SpaceX rocket. Once they arrive together on the lunar surface, then they'll race to see who wins the prize. SpaceX will be paid their normal launch fee.

[1] http://lunar.xprize.org/press-release/two-google-lunar-xpriz...

The P vs NP one looks undoable compared to the other ones.

Why?

I'd explain, but it'd be exponentially long and boring. Or maybe not. I can never be sure.

Do let us know when you find the answer. We can check it quickly.

1. Get a infinite number of monkeys into a room

2. Give it one of these problems.

3. Profit!, of course minus the cost of the bananas.

You forgot step 2.5. Find the scrap of paper with the correct proof on it among the infinite scraps of paper without the correct proof on it.

And step 2.25: find the scraps of paper under the infinitely tall pile of monkey poo.

Finally, some humour on HN!

No need -- just submit them all!

Submit 'em all. Let peer review sort 'em out.

Then there's 2.7 -> Wait for 139 decades until they sift throught the infinite number of papers and find the correct piece of scrap with the solution.

Also, 2.8 -> Hope the prize is corrected for inflation.

Any low-hanging fruits? ;)