News for hackers. Stuff that matters.
Re:Project Euler's 500th problem by ipsin on Saturday January 31, 2015 @03:18PM (#8977933)
One of my favorite parts of Project Euler was getting something where the math seemed beyond me, but I could use a tool like Google to get further.

Not to cheat using Google, but to discover the name of the branch of mathematics I had no clue about, and then to learn enough to keep going.

I still remember the afternoon I spent doing chromatic polynomials by hand, each graph I drew having more mental exclamations on the end, because I was goddamn getting it.

For me, the lift from earning a right answer is palpable.

Re:Project Euler's 500th problem by jacquesm on Saturday January 31, 2015 @03:21PM (#8977950)
Yes! I had that same feeling with this one:

https://projecteuler.net/problem=307

I couldn't solve it analytically for the life of me. So I wrote a small simulator, computed the answer to within 7 decimal places or so and then tried to figure out why that was the right answer. Then the lightbulb went on and I realized what the real answer should be and it worked.

As I wrote above, I am not very good at math, but to be able to use the computer to make your math understanding better than what it was before you started solving a problem was a huge up for me.

Re:Project Euler's 500th problem by jules on Saturday January 31, 2015 @04:15PM (#8978117)
Can you solve that problem analytically? The straightforward answer is to set up a recurrence relation for p(k,n) and use dynamic programming, but even then it's far too laborious to compute p(20000,1000000) without a computer.
Re:Project Euler's 500th problem by jacquesm on Saturday January 31, 2015 @04:30PM (#8978159)
Now I can, but initially I had no idea. But the simulation can be coded up in 15 minutes or so and you'll have your first 3 decimal places in a few minutes after that. To get to 9 decimal places takes a while longer.
Re:Project Euler's 500th problem by jules on Saturday January 31, 2015 @04:39PM (#8978185)
By analytically, do you mean by hand, or just getting the exact answer by computer? Can project euler problems often be solved by hand? For example this 500th problem doesn't seem very hard with a computer, but doing it by hand seems like it will take a long long time.
Re:Project Euler's 500th problem by hyperbovine on Saturday January 31, 2015 @07:07PM (#8978575)
There is an elegant way to solve these types of problems analytically using a technique called Poissonization. The aspect that makes computing the correct answer difficult is the dependence among counts for the various chips. Instead imagine the the number of defects is now Poisson distributed with mean lambda. A convenient property of the Poisson distribution is its "binning" property whereby the number of defects hitting each chip as now Poisson(lambda/n) and, most important, the counts are mutually independent. From here you can compute the correct answer by a power series argument. I'll spare you the details but see http://bulletin.imstat.org/2014/02/student-puzzle-corner/ for a worked example.
Re:Project Euler's 500th problem by jules on Saturday January 31, 2015 @08:12PM (#8978745)
Interesting idea, but I don't quite get how that lets us compute the answer. If I understand it correctly then we need to get the coefficient of l^(10^6) of (e^-(l/20000) + (l/20000)e^-(l/20000) + (l/20000)^2/2e^-(l/20000))^20000, and I do not know how to do that. In fact that is equivalent to finding the coefficient of x^(10^6) of (1+x+x^2)^20000, and it's easy too see that directly from the original problem, so I'm also not sure what Poissonization does for us here. Perhaps I'm completely misunderstanding the technique?
Re:Project Euler's 500th problem by jeffhussmann on Sunday February 01, 2015 @12:15AM (#8979240)
You have flipped the roles of 20000 and 10^6 in your formulation.
Re:Project Euler's 500th problem by jules on Sunday February 01, 2015 @06:50AM (#8979684)
Yes I have, thanks.
Re:Project Euler's 500th problem by jacquesm on Saturday January 31, 2015 @05:00PM (#8978257)
No, it's still by computer. But some of them I can do by hand but that's only a few so far.