What is the largest prime factor of the sum of the favorited comments from all fibonacci-numbered MeFites?

October 13, 2008 3:34 AM

"Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."

Started in 2001 as a sub-section of Maths Challenge, it has since grown large enough to become its own entity. It now boasts over 200 problems, many of them insanely difficult.

"Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute."

Previously (Aug 2005)

posted by mystyk (31 comments total)

I've been working at it for about six hours over the last two days, and I've only solved 15 out of a current 212 (7%).
posted by mystyk at 3:37 AM on October 13, 2008

It's a great site, but this is a 3-year-old dupe.
posted by HaloMan at 4:16 AM on October 13, 2008

Not entirely a dupe. It's gone from 102 problems to 212. And it has its own domain instead of being linked from the Maths Challenge home page.
posted by twoleftfeet at 4:29 AM on October 13, 2008 [1 favorite]

Apparently the prominently placed "Previously" was too well hidden. Besides, even if it hadn't changed at all, that's still over three years worth of users who never saw it and may find it as entrancing as I do. I actually had it in my old bookmarks from back then, in the "I'll get around to it someday" pile, and I'm glad I finally did.
posted by mystyk at 4:42 AM on October 13, 2008 [2 favorites]

I worked on Project Euler for several weeks a couple years ago. It looks like I got 62 of them. They've done a good job of posing problems that can't be solved by direct analytic methods OR naive brute force ones. You need to figure out some heuristics or some way to reduce the problem, then an elegant brute force search.

At least that's what I always had to do. I eventually had to stop because the remainder (at the time) started requiring more and more number theory (which I lack) and less and less naivete (which is my strong suit).
posted by DU at 5:41 AM on October 13, 2008

Hm. You have a point - sorry for being an ass.
posted by HaloMan at 7:10 AM on October 13, 2008 [5 favorites]

If only the Python Challenge was framed in such a direct manner ...
posted by adipocere at 7:15 AM on October 13, 2008

Is it wrong that as that as soon I saw Project Eular I started thinking "Eular........Eular........Eular......" Anyone... Anyone?
posted by srboisvert at 8:18 AM on October 13, 2008

I doubt any of us didn't have that thought. I tried to come up with a variant that would be clever for use in the post title, but you just can't recreate the magic of that moment.

(I'm a firm believer that that was the first, last, and only good line Ben Stein ever had. Now he just runs around saying nonsense. "Evolution - there's a Visine for that...")
posted by mystyk at 8:24 AM on October 13, 2008

Is it wrong that as that as soon I saw Project Eular I started thinking "Eular........Eular........Eular......" Anyone... Anyone?

Yes, there are at least two distinct things wrong with that.
posted by Wolfdog at 8:26 AM on October 13, 2008

I heard Euler had a football team named after him at one point.
posted by burnmp3s at 9:50 AM on October 13, 2008

I never though Euler Euler Euler. It's pronounced "Oiler".
posted by DU at 11:00 AM on October 13, 2008

Which ones are insanely difficult?
posted by iconjack at 11:43 AM on October 13, 2008

ooh this is fun.
posted by Perplexity at 12:22 PM on October 13, 2008

Which ones are insanely difficult?

None, I guess, if you've already figured them out, or perhaps if you solve this sort of problem for a living. But look at something like Problem 202: the challenge is in finding the way to reduce an apparently intractable problem to a solvable one. For a lot of problems, that can require some pretty significant persistence and insight.
posted by musicinmybrain at 12:23 PM on October 13, 2008

Hm. This looks like fun. Problem 15 doesn't require a computer; it's one I happen to know off the top of my head. Though I guess I would need a calculator to get the actual numerical value.

I would probably waste a bunch of time on this if I didn't have to study for quals...
posted by kaibutsu at 12:38 PM on October 13, 2008

Hah, I already identified 202 as the only really hard one.

These are fun problems though. Let's see how long problem 211 (taken at random) takes to solve...
posted by lupus_yonderboy at 1:49 PM on October 13, 2008

I wrote a fast, unoptimized version to make sure I knew what was going on... this will take days to complete however (if that, it slows down quadratically as it goes).

Back to (real) work for me. I'll make it work reasonably fast (if I can) and report later. (This is really for my own interest only :-D).

There are some clear tiny optimizations but I think you can get a massive speedup with a recurrence relation....
posted by lupus_yonderboy at 2:28 PM on October 13, 2008

Project Euler is one the first places I go when I'm learning a wacky new computer language. It's a great way to figure out how to write clean, reusable code (a lot of problems build on the tools used in earlier ones) and how to translate basic algorithm into that language's favorite idioms.
posted by aspo at 2:44 PM on October 13, 2008

Hmm, Problem 14 is messing with me. I used a brute force approach and came up with 992283 as starting the longest chain, with 501 steps. I'm pretty confused as to what I could be doing wrong. Any suggestions? Or maybe someone could identify a number that starts a longer chain? I'm baffled.
posted by Perplexity at 3:11 PM on October 13, 2008

Aha, I was overflowing my float; had to use double.
posted by Perplexity at 3:31 PM on October 13, 2008

What is the largest prime factor of the sum of the favorited comments from all fibonacci-numbered MeFites?

Is anyone taking a stab at this?
posted by flatluigi at 4:23 PM on October 13, 2008

Why does that guy have crumpled up underwear on his head?
posted by Hello Dad, I'm in Jail at 4:25 PM on October 13, 2008 [2 favorites]

(Had a few minutes later). So I have the "trick" to that one 211 - but Python (which was what I was prototyping in) is too slow to pull it off unfortunately within the 10 minute time (based on my estimate).

Spoiler hint: if p is prime and has no common factor with q, what's f(pq)? What's f(ppq)? ("f" being the sum of the squares of the divisors). Use induction to get a formula based on the prime factoring and make a table of all of them.
posted by lupus_yonderboy at 4:37 PM on October 13, 2008

And I had a point to this. :-D That being that these are nicely tricky, attainable problems which are still honestly hard.

I just did #14 and I didn't get the same results you did. It was quite easy.

I got: (837799, 525)

#!/usr/bin/python                                        

def Next(n):
  if n % 2:
    return 3 * n + 1
  return n / 2


def FindLongestChainIndex(max_num):
  # Cache results in a dictionary!                       
  chain_length = {1:1}
  max_chain = 0
  max_length = 0
  def GetChainLength(x):
    if x not in chain_length:
      chain_length[x] = 1 + GetChainLength(Next(x))
    return chain_length[x]

  for i in range(2, max_num + 1):
    length = GetChainLength(i)
    if length > max_length:
       max_length = length
       max_chain = i
  return max_chain  # , max_length,  chain_length        


def GetChain(x):
  if x == 1:
    return [1]
  return [x] + GetChain(Next(x))


def GetLongestChain(x):
  return GetChain(FindLongestChainIndex(x))


longest_chain = GetLongestChain(1000000)
print longest_chain[0], len(longest_chain)

Runs in 5 seconds on my pretty fast Mac.
posted by lupus_yonderboy at 5:12 PM on October 13, 2008

ARG, what happened there!? It looked great on the preview pane!

So sorry, mods, any way to fix?!
posted by lupus_yonderboy at 5:12 PM on October 13, 2008

I really enjoyed #18. Once you figure out the bottom-up approach instead of a path-search, you reduce the time from O (2^n) to O (n^2). Plus, you can re-use that solution on #67, where n becomes 100.

Strangely enough, I can't get #17 to work. "If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?"

I've written and re-written the program, using strings sometimes and just adjusting counters other times, accounting for use or non-use of "and", and even worked it out on paper. It's not accepting the answer.
posted by mystyk at 5:00 AM on October 14, 2008

All I can say is the harder problems here are definitely difficult enough for me. I discovered the site about 6 months ago, and I've solved about 150 of the problems. The ones that remain are pretty tough.

You can sort the problems by "difficulty", meaning how many people have solved them. Most of the ones that have been solved by fewer than about 500 people are tough as far as I'm concerned.

By the way, claims that they're all extremely easy will be more credible if you make them after having solved the problem rather than before :) (keeping in mind that your solution is supposed to run in less than a minute.)

If anyone wants hints on some of the earlier problems you can MeMail me. Don't think I want to post spoilers and solutions here.
posted by dixie flatline at 6:30 AM on October 14, 2008

For those that use Python to solve the problems and find it too slow for certain tasks, take a look at Psyco, a JIT-like compiler. Very easy to use (Just install, then add one line to your source gode) and gives significant speed improvements.
posted by ymgve at 8:32 AM on October 14, 2008

I don't think anyone would claim that any of the problems are extremely easy. #14 was pretty easy. I spent the better part of an hour on 211 but didn't generate a solution that runs close to the time limit.

I spent about 10 minutes thinking about 202 and aside from the lightbulb OK, I guess I do now know how to do 202 :-D but I'll bet it'd take work to get it right!

These are good problems - clear goals, interesting solutions that aren't trivial but are attainable. They're good at two levels: it takes "mathematical maturity" to see the right approach - but then if someone tells you the right approach, the implementation is also entertaining and challenging. And none of them are insanely hard.

In Knuth's "Art of Computer Programming", the exercises are marked as to their level. Some of them are fairly easy - I believe some still remain unsolved thirty years later. That's insanely hard.

He references some other text which did this, except it didn't even mark the difficulty level. :-D
posted by lupus_yonderboy at 9:45 AM on October 14, 2008

Another (in)famous source for problems is Stanley's 'Enumerative Combinatorics.' He marks his problems on a 1-5 scale (with +'s and -'s). A [3-] is the hardest problem that can reasonably be assigned as homework; [5]'s are unsolved. He famously has a 66-part problem in which the answer to every part is the Catalan Numbers, expanded to 200+ parts on the website linked above.
posted by kaibutsu at 10:21 AM on October 14, 2008