Project Euler 221

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.events.*;
    import flash.utils.getTimer;
    import com.bit101.components.*;
    // @see http://projecteuler.net/index.php?section=problems&id=221
    public class Euler221 extends Sprite {
        private var _tf : TextField;
  
        public function Euler221() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var pb : PushButton = new PushButton(this, 350, 10);
            pb.label = "stop";
            pb.width = 100;
            pb.addEventListener(MouseEvent.CLICK, function(e : MouseEvent) : void
            {
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
            });
            
            var s : int = getTimer();
            solve();
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private const N : int = 150000;
        private var set : Object = {};
        private var vv : Number;
        private var p : Number;
        private var ct : int = 0;

        private function solve() : void
        {
            // p > 0, q < 0, r < 0
            // |p| < |q| < |r|
            // |q| <= 2|p|
            // pq+qr+rp=1
            // r=(-pq+1)/(p+q)
            
            // r=(pq+1)/(q-p)
            // pqr = pq(pq+1)/(q-p) <= p(p+1)(p(p+1)+1)
            for(p = 1;p <= 30000;p++){
//                for(var q : int = p + 1;q <= 2 * p;q++){
//                    if((p * q + 1) % (q - p) == 0){
//                        var r : int = (p * q + 1) / (q - p);
//                        tr(p, q, r, p * q * r);
//                        vs.push(p * q * r);
//                    }
//                } 
                var p21 : Number = p * p + 1;
                for(var k : int = 1;k <= p;k++){
                    if(p21 % k == 0){
                        var v : Number = p * (p + k) * (p + p21 / k);
                        if(!set[v])ct++;
                        set[v] = v;
                    }
                }
                
                if(ct >= N){
                    vv = select(objToArray(set), N - 1);
                    tr(p, vv);
                    break;
                }
            }
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }
        
        private function objToArray(set : Object) : Array
        {
            var a : Array = [];
            for each(var v : Number in set)a.push(v);
            return a;
        }
        
        private function onEnterFrame(e : Event) : void
        {
            var N100 : int = N / 90;
            var sup : int = p + N100;
            for(;p < sup;p++){
                var p21 : Number = p * p + 1; 
                var dd : Number = ((vv / p) - (2 * p * p + 1)) / p;
                if(dd * dd - 4 * p21 < 0){
                    tr("solved!");
                    tr(p, select(objToArray(set), N - 1));
                    removeEventListener(Event.ENTER_FRAME, onEnterFrame);
                    return;
                } 
                var infk : Number = (dd - Math.sqrt(dd * dd - 4 * p21)) / 2;
                for(var k : int = Math.ceil(infk);k <= p;k++){
                    if(p21 % k == 0){
                        var v : Number = p * (p + k) * (p + p21 / k);
                        set[v] = v;
                    }
                }
            }
            vv = select(objToArray(set), N - 1);
            tr(p, infk, vv);
        }

        private function select(a : Array, k : int, left : int = 0, right : int = -1) : *
        {
            if(right == -1)right = a.length;
            while(true){
                var pnind : int = partition(a, left, right, Math.random() * (right - left) + left);
                if(k == pnind)return a[k];
                if(k < pnind){
                    right = pnind;
                }else{
                    left = pnind + 1;
                }
            }
            return null;
        }
        
        private function partition(a : Array, left : int, right : int, pind : int) : int
        {
            var n : int = a.length;
            var pv : * = a[pind];
            a[pind] = a[right - 1];
            a[right - 1] = pv;
            
            var sind : int = left;
            for(var i : int = left;i < right - 1;i++){
                if(a[i] <= pv){ 
                    var d : * = a[sind];
                    a[sind] = a[i];
                    a[i] = d;
                    sind++;
                }
            }
            a[right - 1] = a[sind];
            a[sind] = pv;
            return sind;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
        }
    }
}