Project Euler 137

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/v2ah
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=137
    public class Euler137 extends Sprite {
        private var _tf : TextField;
  
        public function Euler137() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            t(solve(15));
            var g : int = getTimer();
            t((g - s) + " ms");
        }

        // フィボナッチ数の公式
        // F_i=1/√5(((1+√5)/2)^i-((1-√5)/2)^i)を使う。
        // x^iF_i=1/√5(((1+√5)x/2)^i-((1-√5)x/2)^i)
        // 問題文の例から類推して、xは1未満で、1項目と2項目のそれぞれの無限和は収束するだろうと勝手に仮定
        // そうすると、A_F(x)=x/(-x^2-x+1)となる。
        // y=A_F(x)と置いて、xの2次方程式とみると
        // x={-(1+y)+√((1+y)^2+(2y)^2)}/2y
        // 例によってピタゴラス数の生成。(2y, y+1)=1なので
        // 2y=2mn, y+1=m^2-n^2 (m>n>=1, (m,n)=1)とおいてよい。
        // yを消去してm^2-n^2=mn+1
        // m={n+√(5n^2+4)}/2
        // よって、nをインクリメントしていって5n^2+4が平方数になるようなのを見つけたら
        // m, y(=mn)を求めていけばよい。
        private function solve(L : int) : Number
        {
            var ct : int = 0;
            for(var n : Number = 1;ct < L;n++){
                var sq : Number = Math.sqrt(5 * n * n + 4);
                if(sq != int(sq))continue;
                var m : Number = (n + sq) >> 1;
                if(GCD(m, n) != 1)continue;
                var y : Number = m * n;
                
                // おまけ
                var di : Number = -(1 + y) + (m * m + n * n);
                var de : Number = 2 * y;
                var g : int = GCD(di, de);
                di /= g;
                de /= g;
                t(y + " -> " + di + "/" + de);
                ct++;
            }
            return y;
        }
        
        private function GCD(a : Number, b: Number) : Number
        {
            return b == 0 ? a : GCD(b, a % b);
        }

	private function t(o : *) : void
	{
            _tf.appendText("" + o + "\n");
	}
    }
}