johnkemeny.com

Τomas Rokicki is a man of many algorithms.  He co-authored Golly, a Life simulator that is super fast due to its unique hashlife algorithm.  Last month he proved that 25 face moves (where face move = a quarter or half turn) are suffficient to solve any Rubik’s cube, and he did it using a computer (similar to the solution to the famous Four Color Problem) – specifically, he used Herbert Kociemba’s Cube Solver, which you can download for free.

In 1995 Michael Reid showed that 20 moves were necessary to solve the superflip (pictured).  Kociemba ran his cube solver over 1 million random configurations, and not one needed more than 20 moves to solve.  He then ran 1000 optimal random configurations (at ~2 minutes per solution with 3 GHz processors and 8 GB memory) and found the “average” cube can be optimally solved in ~18 moves.  It clearly appears that 20 moves should suffice to solve any Rubik’s cube.  But can that be proven?

Initially, solution algorithms could take up to 75 moves.  In 1995 Reid showed Kociemba’s algorithm could reduce the maximum to 29 moves, still quite a ways from 20.  In 2006 this was improved to 27, and in 2007 to 26.  Now, thanks to Tom Rokicki, it stands at 25 - and he is on to 24.

Update: As of June, Rokicki cut it to 23 using a Sony/Spiderman render farm.

Update: As of August, Rokicki cut it to 22 using the same Sony/Spiderman render farm.

As described by the inimitable Ze Frank, Color Wars 2008 are coming. I have been assignated<sic> to Team Clear(wiki). Ironic given my rainbow-colored twitter backdrop, no?

Today, of course, is the Ides of March, when Anonymous is slated to protest Scientology again, two days after founder L. Ron Hubbard’s birthday.  But let’s look back to the future to Pi Day, the 14^th of March, which is Einstein’s birthday, and, according to Sean at Cosmic Variance, Talk Like a Physicist Day (not to be confused with any other Talk Like a PD).

To celebrate you could read Lucas Kovav’s paper, Electron Band Structure In Germanium, My Ass, which concludes:

Going into physics was the biggest mistake of my life.

Or you might want to see scientists explain their research results on video.  In that case check out SciVee.tv.  In keeping with our back to the future theme, below is Dr. David Frisch and James Smith’s demonstration, atop Mount Washington, of time dilation, first predicted by Einstein.

For more physics phun try the free Phun Software package.

Not a memorial, but a tribute – since he is a ‘missing person’ for 5 years – you can register for the technical session or reserve a transcript of the proceedings here.

It started with Google maps. Sometime back they added Satellite Views, which show decent images – of my house from above, you can see the white deck chairs out by the pool which is covered by a black tarp. They recently introduced My Maps which lets you share a map with others. Go ahead and add your location to my blog reader map by clicking Edit. Today they introduced Street Views of Boston and its surrounds, where you can actually see your neighbors in the public environment. I figured I would preserve some privacy by being located in the obscure suburbs. But no! Sometime this summer the Google camera truck rolled down Robinson Road and took a picture of our house. You can even see Lia and Alan’s red wagon parked out in front. I can’t wait for the Google picture phone with GPS to follow me around.

P.S.  Now the US government is concerned: BBC article.

P.P.S. See here.

For their third birthday, Lia and Alan both got real digital cameras. Alan’s first shot was of Dad crawling in front of the lens. Lia, the art’tist, preferred taking pictures of the Wiggles birthday cake – featuring the Big Red Car – her feet – I show her best shot omitting the rest of the series – and her Mom – at least a part of her – dancing.

As Lia – playing with sharp objects – and Alan – filling up on Mom’s chocolate pretzels – can attest, pumpkin carving was a sweet success. No one can yet say if the One Laptop Per Child (OLPC) will be a success, but for a limited time starting November 12 you can Give One Get One (G1G1) for $399. You can test drive it today using VMware’s free player (registration required) and the latest pre-made images.

Full disclosure: I work for EMC, which owns 86% of VMware – but I got no VMware stock (sad face).

I also have 3-year old twins who would love an XO laptop – but they don’t live in the third world – and their daddy ain’t rich – but their mom is good looking

 Update: Message from laptopgiving.org:

Starting Monday, November 12 at 6:00am EST, you will be able to donate one XO laptop to a child in the developing world and also receive a laptop for the child in your life, by visiting www.laptopgiving.org or calling toll-free 1-877-70-LAPTOP.

“Give One Get One” is the only time we are making the revolutionary XO laptop available to the public. For a donation of just $399 ($200 of which is tax-deductable), you will be giving the gift of education. Additionally, T-Mobile is offering donors one year of complimentary access to T-Mobile HotSpot locations throughout the United States, which can be used from any Wi-Fi-capable device, including the XO laptop.

My blogoverse buddy (B_vB^TM) Jonathan asked me to contribute to CoM-18, which he is hosting and I am happy to do so. But first a belated shoutout to my B_vB, and best reviewer, Dave Marain, who interviews Professor Lynn Steen, a principal architect of the original NCTM Standards and a highly respected voice in reform mathematics.

Don’t expect any research topics here. This is about solving a practical problem in automotive gas economy which involves a pricing anomoly, a Greek mathmatician who may have tutored Alexander the Great, and an 18th century Scottish math professor who almost loses his job by taking an unauthorized 2-year sabbatical to tour the Continent. Can you imagine not losing your job today?

So what is the problem? I have 2 cars, an older model which uses regular gas, and a slightly newer model which only uses the more expensive high-test gas, but also gets more miles per gallon (mpg). The question is which is more economical to  drive? The pricing anomaly I have observed is that no matter the price per gallon (ppg) of gasoline, and the price has fluctuated up and down quite a bit, the difference in price between regular and high-test is almost always a constant, viz., 25 cents. So which car  is more economical to drive actually depends on the price of gasoline! Observe.

The price per mile, ppm = price per gallon / miles per gallon.  The percent difference in ppm between regular and high-test,

%diff = (ppm_regular / ppm_high-test) – 1 = (p / m) – 1,

where p = ppg_regular / ppg_high-test and

m = mpg_regular / mpg_high-test.

If we take

d = ppg_high-test – ppg_regular = $0.25 and

m = 25 / 27 and

then plot ppg_high-test against %diff we get:

So if the price of high-test is below about $3.35 the gas guzzler is more economical fuel-wise, and versa vice. But what is this  curve? A cubic polynomial trend line fits it almost perfectly. So is it a polynomial? Zooming out gives us a clue.

It is a rectangular hyperbola (first studied by Menaechmus, a student of Plato, about 350 BC) flipped on the X axis and asymptotic to X = 0 and Y = 0.08 = (1 / m) -1. You can easily see this by rewriting the equation for %diff as

%diff = A / ppg_high-test + B where

A = -d / m and

B = (1 / m) – 1

So this leaves the question of why a cubic polynomial fits the data so well. And here is where our Scottish math professor, Colin MacLaurin, comes in. In 1742 he wrote A Treatise on Fluxions (pdf), the first systematic application  of Newton’s calculus, in which he shows, among other trigonometric marvels, how the equation for a hyperbola could be closely approximated by truncating an infinite polynomial series.