Project Euler 140

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=140
    public class Euler140 extends Sprite {
        private var _tf : TextField;
  
        // @see http://izumi-math.jp/F_Nakamura/friend/friend3.htm
        // A_G(x)=(x+3x^2)/(1-x-x^2)から、xの2次方程式とみると、
        // xが有理数になるためには、解の公式の根号内 5A^2+14A+1が平方数であればよい。
        // だが、20個目でAが2億になるため、30個は、Flashの総当たりでは不可能。
        // 4次元ピタゴラス数を生成する。
        // 5A^2+14A+1=(3A+5)^2-(2A+4)^2-2^2-2^2より、
        // Aは2自然数s,tにより
        // s^2((A+2)^2+1^2+1^2)+t^2=st(3A+5)と書ける。
        // r=t/sとして、Aについて解くと、
        // A=((3r-4)+√(5r^2-4r-8))/2
        // s=1と仮定すると、次は5r^2-4r-8が平方数になればよい。
        // 5r^2-4r-8=(3r+2)^2-(2r+2)^2-2^2-2^2より、
        // 先と同じようにすると、次は5q^2+4q-8が平方数になればよい。
        // その次は5p^2-4p-8・・・このへんで、もしかしたら解は漸化式で求まるのではないかと考えて
        // シミュレーションしたらそれっぽかったので、
        // 2,3を種としてr,qを求めるための解の公式にあてはめて漸化式とする。
        // 
        // 結果よければすべて良しでした。
        // s=1も厳密に証明はしていないけれども、2st:s^2((A+2)^2+1^2+1^2)+t^2=1:st(3A+5)より、
        // 証明できそう。s<1000かつt<1000までは大丈夫だった。
        // あと解の公式のマイナスの方も全然検証してないね・・よろしくない。
        public function Euler140() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            t(solve());
            var g : int = getTimer();
            t((g - s) + " ms");
        }

        private function solve() : Number
        {
            var sum : Number = 0;
            var sa : Number = 2;
            var sb : Number = 3;
            for(var i : int = 1;i <= 15;i++){
                var fsa : Number = f(sa);
                var fsb : Number = f(sb);
                t(fsa);
                t(fsb);
                sum += fsa + fsb;
                sa = g(sa);
                sb = g(sb);
            }
            return sum;
        }

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

        private static function f(x : Number) : Number
        {
            return (3 * x - 4 + Math.sqrt(5 * x * x - 4 * x - 8)) / 2;
        }
        
        private static function g(x : Number) : Number
        {
            x = ((3 * x - 2) + Math.sqrt(5 * x * x - 4 * x - 8)) / 2
            x = ((3 * x + 2) + Math.sqrt(5 * x * x + 4 * x - 8)) / 2
            return x;
        }
    }
}