Project Euler 283(unsolved)

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

forked:0
favorite:0
lines:155
license : MIT License
modified : 2010-03-22 14:37:55

Embed: Tweet

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=283
    public class Euler283 extends Sprite {
        private var _tf : TextField;
  
        public function Euler283() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            var A : uint = 25;
            tr(solve(4*A*A));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private function solve(K : uint) : Number
        {
        		var alim : uint = K+1;
			var sn : uint = 0;
			var sd : uint = 1;
			var en : uint = 1;
			var ed : uint = 1;
			var seg : Vector.<uint> = new Vector.<uint>(999999);
        		var ret : Number = 0;
        		var p : uint = 0;
        		var ct : uint = 0;
        		// m = nd, n = nn (m > n) 
        		while(true){
        			var nn : uint = sn + en;
        			var nd : uint = sd + ed;
           		if(nn + nd <= alim){
            			if((nd^nn)&1){
            				var m : uint = nd;
            				var n : uint = nn;
//	        				var kmax : uint = alim*alim / ((m+n)*(m+n));
//	        				for(var k : uint = 1;k * k <= kmax;k++){
	        				for(var k : uint = 1;;k++){
	        					if(K * (n + 2* m)- k*k*m*m*n < 0)break;
	        					if(k*k*m*n-K<=0)continue;
	        					if((k*K*(m+n)) % (k*k*m*n-K) == 0){
			          			ct++;
	        						var u : uint = (k*K*(m+n)) / (k*k*m*n-K);
	        						var x : uint = k*m; // (a+k*(m-n))/2;
		        					var a : uint = k * (m + n);
	        						var b : uint = a-x+u;
	        						var c : uint = 2*(b+x)-a-b;
	        						var t : uint = b+x;
	        						// 2(a+u);
//	        						var S : Number = Math.sqrt(t*(t-a)*(t-b)*(t-c));
//	        						var P : Number = a + b + c;
//			          			tr(m + n);
//		        					tr(u, x, k,m,n,"",a, b, c, S, P, S/P);
		        					tr(a, b, c);
	        					}
	        				}
	            		} 
	            		
					seg[p] = en;
					seg[p + 1] = ed;
					p += 2;
					en = nn; ed = nd;
        			}else{
        				if(p == 0)break;
        				sn = en;
        				sd = ed;
        				en = seg[p - 2];
        				ed = seg[p - 1];
        				p -= 2;
        			} 
        		}
        		tr(ct);
        		
        		return ret;
        }
        
        /*
        private function solve(K : uint) : Number
        { 
        		var alim : uint = 4*(K+1)*(K+1);
        		for(var m : uint = 1;m+1<=alim;m+=2){
        			for(var n : uint = 2;m+n<=alim;n+=2){
        				if(GCD(m,n) > 1)continue;
        			//	var kmin : uint = K / (m * n);
        				var kmax : uint = alim*alim / ((m+n)*(m+n));
        				for(var k : uint = 1;k * k <= kmax;k++){
        					var a : uint = k * (m + n);
        					if(K - k * Math.max(m, n) < 0)break;
        					if(k*k*m*n-K<=0)continue;
        					if((k*K*(m+n)) % (k*k*m*n-K) == 0){
        						var u : uint = (k*K*(m+n)) / (k*k*m*n-K);
        						var x : uint = (a+k*Math.abs(m-n))/2;
        						var b : uint = a-x+u;
        						var c : uint = 2*(b+x)-a-b;
        						var t : uint = b+x;
        						var S : Number = Math.sqrt(t*(t-a)*(t-b)*(t-c));
        						var P : Number = a + b + c;
	        					tr(u, x, k,m,n,"",a, b, c, S, P, S/P);
        					}
        				}
//        				tr(kmin, kmax);
        			}
        		}
        		return 0;
        }
        */
        
        /*
        private function solve(N : uint) : Number
        {
        		var primes : Array = sieveEratosthenes(3 * N);
        		var p : uint = 0;
        	
        		var ct : uint = 0;
        		var ret : Number = 0;
    			for(var t : uint = 1;t <= 3 * N;t++){
    				if(primes[p] == t){
    					p++; 
    					continue;
    				}
				for(var a : uint = 1;a <= t*2/3;a++){
					for(var b : uint = Math.max(a, t-a+1);b <= t-a/2;b++){
//						if(a+b<=t)continue;
						if((a * b * (a + b)) % t != 0)continue;
						var sqval : Number = Math.sqrt((t-a)*(t-b)*(a+b-t)/(4*t));
						if(sqval == int(sqval) && sqval <= N){
							ret += 2 * t;
//						if(sqval == int(sqval)){
							tr(a,b,t);
							ct++;
						}
//						tr(a,b,t);
					}
				}
        		}
        		tr(ct);
        		return ret;
        }
        */
        
        private function sieveEratosthenes(n : int) : Array
        {
            var nn : uint = ((n / 2 - 1) >>> 5) + 1;
            var ar : Vector.<uint> = new Vector.<uint>(nn);
            var i : uint, j : uint;
            for(i = 0;i < nn - 1;i++)ar[i] = 0xffffffff;
            ar[nn - 1] = (1 << ((n / 2 - 1) & 31)) - 1;
            
            var sq : uint = (Math.sqrt(n) - 3) >>> 1;
            for(var p : uint = 0;p <= sq;p++){
                if(ar[p >>> 5] & (1 << (p & 31))){
                    var m : uint = (p << 1) + 3;
                    var m2 : uint = m << 1;
                    for(var mm : uint = m * m;mm <= n;mm += m2){
                        var ind : uint = (mm - 3) >>> 1;
                        ar[ind >>> 5] &= ~(1 << (ind & 31));
                    }
                }
            }
            
            var ret : Array = [2];
            for(i = 0;i < nn;i++){
                for(j = 0;j <= 31;j++){
                    if(ar[i] & (1 << j))ret.push((((i << 5) | j) << 1) + 3);
                }
            }
            return ret;
        }
        
        private function mergeCount(a : Object, b : Object) : Object
        {
        		for(var key : String in b){
        			if(a[key]){
        				a[key] += b[key];
        			}else{
        				a[key] = b[key];
        			}
        		}
        		return a;
        }
        
        private function enumDividers(f : Object) : Array
        {
        		var seed : Array = [1];
        		for(var key : String in f){
        			var p : uint = uint(key);
        			var ct : uint = f[key];
        			
        			for(var i : int = seed.length - 1;i >= 0;i--){
        				var val : uint = seed[i];
        				for(var j : uint = 1;j <= ct;j++){
        					val *= p;
        					seed.push(val);
        				}
        			}
        		}
        		return seed;
        }

private function factor(n : int) : Object
        {
            var ret : Object = {};
            var sq : int = Math.sqrt(n);
            for(var i : int = 2;i <= sq;i++){
                var ct : int = 0;
                while(n % i == 0){
                    n /= i;
                    ct++;
                }
                if(ct > 0){
                    ret[i] = ct;
                    sq = Math.sqrt(n);
                }
            }
            if(n != 1){
                ret[n] = 1;
            }
            return ret;
        }
        
        /*
        private function solve(N : uint) : Number
        {
			var sn : uint = 0;
			var sd : uint = 1;
			var en : uint = 1;
			var ed : uint = 1;
			var seg : Vector.<uint> = new Vector.<uint>(99999);
        		var ret : Number = 0;
        		var p : uint = 0;
        		var o : Object = {};
        		var val : Number;
        		var k : uint;
        		var ct : uint = 0;
        		// m = nd, n = nn (m > n)
        		while(true){
        			var nn : uint = sn + en;
        			var nd : uint = sd + ed;
        			var pro : uint = nn * (nd - nn);
           		if(pro <= N * 2){
            			if((nd^nn)&1){
            				var oret : Number = ret;
            				var klim : Number;
            				if(pro & 1){
            					klim = Math.floor(N / pro);
            					ret += 2 * nd * (nd + nn) * klim * (klim + 1);
            					for(k = 1;k <= klim;k++){
            						val = 4 * k * nd * (nd + nn);
            						o[val] = val;
            					}
            				}else{
            					klim = Math.floor(N / (pro / 2));
            					ret += nd * (nd + nn) * klim * (klim + 1);
            					for(k = 1;k <= klim;k++){
//            						tr(k, nd, nn);
            						val = 2 * k * nd * (nd + nn);
            						o[val] = val;
            					}
            				}
            				ct += klim;
//            				tr(nd, nn, pro, ret - oret);
	            		}
	            		
					seg[p] = en;
					seg[p + 1] = ed;
					p += 2;
					en = nn; ed = nd;
        			}else{
        				if(p == 0)break;
        				sn = en;
        				sd = ed;
        				en = seg[p - 2];
        				ed = seg[p - 1];
        				p -= 2;
        			} 
        		}
        		tr(ct);
        		
        		var sum : Number = 0;
        		for each(val in o){
        			sum += val;
        		}
        		tr(sum);
        		return ret;
        }
        */
        
        
        private function GCD(a : Number, b : Number) : Number
        {
        		while(b > 0){
        			var c : Number = a;
        			a = b;
        			b = c % b;
        		}
        		return a;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}

Code Fullscreen

Preview Fullscreen