Thursday, September 09, 2004

My Trip to Boston (Click to Enlarge!) 

Employees of Cabot Corporation, you are immortal in this lamppost! (Boston Common)

Aw yeah! (Boston Common)

The buildings of Christian Science. Take that you disreputable Scientology wackos!

A picture of a bunch of people getting their picture taken in front of the bar that the TV show Cheers was based on. We figured this out when a big tour bus drove by, and overheard the driver pointing this out. "In there, everyone knows your name. Especially if you're wearing a nametag." Hilarious.

Some pictures of the first LISP machine at the MIT Museum. And I thought the breadboards I had to make in ECE152A were bad.

The key to successful web marketing is making it easy for people to remember your URL (Taken near MIT).

Some views of the Stata Center at MIT.

World's End. On the way back, we had to be escorted out of Weymouth by the police.

Chilling out at the Boston Aquarium.

The best thing I saw at Boston happened today at the airport. I don't have pictures of it, because I didn't realize at the onset just how entertaining the spectacle would eventually be.

As we were sitting at Logan waiting for our plane, we were right in front of another jet being loaded up for a trip to Laguardia. A guy drove up with a big baggage cart, and started pulling out cardboard containers of the sort the US Mail uses. He would grab three at a time, and hurl them into the cargo door. Not a gentle, lofting toss from overhead, but a full, start-at-the-hip out of control swing. Well, one eventually hit the side of the door, and split open, tossing letters and catalogs on the ground everywhere.

He stopped for a moment, thinking. Upon consideration, he decided it was fine for the mail to sit there on the wet ground in the rain, and started throwing more boxes into the plane. Then, all the boxes hurled, he half-heartedly picked up a few limp, dissolving items, and shoved them through the door, leaving the cardboard box and many other letters still fully submerged in the puddles they were in. His job done, he went on to other tasks. Another guy came along and pointed out that this wasn't the way to handle this, and picked up a few more letters. He tossed them in and closed the cargo door. Finally, a third guy came and bravely, as the jet was starting its engines, collected the bin and the remaining letters and bills, opened the cargo door, and loaded them on. Not rain, nor sleet, nor dark of night.
That billboard is a Google recruitment tool. As explained in this blog.
That's cool. I figured it had to be something like that. I was thinking how easy that is to solve when I saw it, so I guess that second step really helps.

- David
I thought the first part would be easy, but even finding the list of all 10-digit primes is tough; not to mention finding enough digits of e. (I thought it would be a simple search, but line breaks in the most visible listing of e would hurt that.)

In short, I think I'd have to write a program to find it, and I'm not in the mood so much to do that.
Well, I would have parsed that listing of e (piece of cake) and started taking each 10-digit number in it and checking for primeness. You could pre-generate a list of all the prime numbers between 2 and sqrt(9999999999) (approximately 100000) and try dividing by each one until you've found a root or exhausted all of them. I think that would be faster.

Actually, even easier, you can find a list of the first n primes online, and there are only 9594 primes less than 100000. Well, I think writing a function to generate the list of primes under 100000 is easier than writing one to parse the text file, but even if it isn't, it's more fun and looks prettier.

Say it's near the end of the first 5 million digits of e (biggest listing I could find), then that's a maximum of about 50000000000 divisions you'd have to try to find it. Totally managable, even though it would take a while.

Of course, if it's not in the first 5 million digits of e, and they would know this, you might have to find an algorithm to calculate the digits of e. Still, that's not too hard either, as things go. Could probably even find some code.

However, I think this might be more of a barrier than I thought at first. They're probably not looking for total geniuses. What they probably want is someone who can write a program to find that without breaking too much of a sweat. And who is intellectually curious enough to try it based on the billboard. In my experience, many people can graduate with a degree in CS and good grades, and still be a totally inept programmer.
Well, I'd use the seive to generate the prime factors I needed, instead of trying all divisors from 2 to sqrt(9999999999) each and every time.

But my plan was to turn e into a large string, and use "find" on it with the convieniently finite list of 10-digit primes (I couldn't use the seive so easily to find those, I'd have to use online lists of primes). Probably a good way to do it would be to build a regular expression out of that finite set, build the state machine for it, and go hunting in "e" for that regular expression. That way, the e string would only need to be scanned once.
I wasn't saying to try every divisor between 2 and sqrt(9999999999), just those that are prime. And you stop when you find one, so many numbers (especially those ending in 0, 2, 4, 5, 6, and 8) would short circuit. Fortunately 10-digit numbers will fit into a 64-bit int, so the math here should be fairly fast.

However, I would think there are way too many 10-digit primes to make building the exhaustive list faster than doing a prime-check on every 10-digit number in the digits of e. Way more than 5 million, at least.

That'd be one honking huge dfa, too.
True, but the DFA would fit in cache.
Post a Comment

This page is powered by Blogger. Isn't yours?