Project Euler 44

@see http://projecteuler.net/index.php?section=problems&id=44

by uwi 22 Sep 2009

Embed

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

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

        // X-A=B, A-B=C(すべて五角数)となるような4数を見つけてくればよい。
        // Cを昇順にしていって探す。求める値はCの最小値なので、これにより最小性が保証される。
        // A-B=(a-b)(3(a+b)-1)/2=c(3c-1)/2 より
        // cに含まれる素因数3はすべてa-bに吸収される。
        // その上で、c(3c-1)をa-bと3(a+b)-1にわけ、a,bを求める。
        // その後A+Bが五角数になるかテストして(X)、五角数なら成立。
        private function solve(M : int) : int
        {
            for(var c : int = 1;c <= M;c++){
                var p : int = c * (3 * c - 1);
                for(var q : int = c, r : int = 3;q % 3 == 0;q /= 3, r *= 3);
                for(var d : int = (q % 3) * (r / 3);d < c;d+=r){
                    if(d == 0)continue;
                    if(p % d == 0){
                       var sum : int = (p / d + 1) / 3;
                       if((d & 1) == (sum & 1)){
                           var a : int = (sum + d) >> 1;
                           var b : int = (sum - d) >> 1;
                           
                           var n : Number = a * (3 * a - 1) + b * (3 * b - 1);
                           var sq : Number = (1 + Math.sqrt(1 + 12 * n)) / 6;
                           if(Math.floor(sq) == sq){
                               t(a + "\t" + b + "\t" + c + "\t" + sq);
                               return a * (3 * a - 1) / 2 - b * (3 * b - 1) / 2;
                           }
                       }
                    }
                }
            }
            return 0;
        }

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