GolfScript, 24 characters
~:&1.{.2$+&%.2$(|}do](-,
Next iteration of a GolfScript implementation. The second version now also handles 1 correctly. It became quite long but maybe someone can find a way to shorten this version. You can try above version online.
