Project Euler 248

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

package {
	import flash.display.Sprite;
	import flash.text.TextField;
	import flash.utils.getTimer;
	// @see http://projecteuler.net/index.php?section=problems&id=248
	public class Euler248 extends Sprite {
		private var _tf : TextField;
  
		public function Euler248() {
			_tf = new TextField();
			_tf.width = 465;
			_tf.height = 465;
			addChild(_tf);
			
			var s : int = getTimer();
			tr(solve());
			/*
			for each(var a : Array in enumE2()){
				for each(var o : Object in a){
					tr(o.num, o.factors);
				}
			}
			*/
			var g : int = getTimer();
			tr((g - s) + " ms");
		}

		// φ(p^n)=p^(n-1)*(p-1)をひたすら利用して解く。
		// φ(p^n)の値が13!の約数となるようなp^nをすべて求めて、
		// それらを組み合わせて13!になるようにすればよい。
		// 13!の約数は1582通りしかないので、WFSでいける。
		// enumE1()はn=1となるpをすべて求める。13以上の13!の約数に1を足して素数だったら採用。
		// enumE2()は、n>1となる(p,n)をすべて求める。これはφの値の中にpが残るので、p<=13となる。
		private function solve() : Number
		{
			var ee : Array = enumE1().concat(enumE2());
			var a : Array;
			var s : Object;
			var seed : Object = {};
			seed[0] = Vector.<Number>([1]); 
//			ee = ee.slice(0, 100);
			
			var lim : Array = [10, 5, 2, 1, 1, 1];
			for each(a in ee){
				var next : Object = {};
				var key : String;
				for(key in seed){
					next[key] = seed[key];
				}
				
				for each(s in a){
					var pluscode : uint = 0;
					for(var q : int = 5;q >= 0;q--){
						pluscode = pluscode * 11 + s.factors[q];
					}
					 
					for(key in seed){
						var f : Boolean = true;
						for(var i : uint = uint(key), p : uint = 0;i > 0;i /= 11, p++){
							if((i % 11) + s.factors[p] > lim[p]){
								f = false;
								break;
							}
						}
						if(!f)continue;
						
						var pp : Vector.<Number> = new Vector.<Number>();
						for each(var v : Number in seed[key]){
							pp.push(v * s.num);
						}
						
						var nkey : uint = uint(key) + pluscode;
						if(!next[nkey]){
							next[nkey] = pp;
						}else{
							next[nkey] = next[nkey].concat(pp);
						}
					}
				}
				seed = next;
			}
			
			for(var k : String in seed){
				tr(uint(k).toString(11), seed[k].length);
			}
			
			var such : Vector.<Number> = seed[((((1*11+1)*11+1)*11+2)*11+5)*11+10];
			tr(such.length);
			such.sort(Array.NUMERIC);
			tr(such[0]); // first of such number = 6227180929
			return such[149999];
		}
		
		private function enumE2() : Array
		{
			var lim : Array = [10, 5, 2, 1, 1, 1];
			var ps : Array = [2, 3, 5, 7, 11, 13];
			var ret : Array = [];
			
			var i : uint, j : uint;
			for(j = 0;j < ps.length;j++){
				var p : uint = ps[j];
				var pm1 : uint = p - 1;
				var l : Array = [0, 0, 0, 0, 0, 0];
				for(i = 0;i < ps.length;i++){
					while(pm1 % ps[i] == 0){
						pm1 /= ps[i];
						l[i]++;
					}
					if(l[i] > lim[i])break;
				}
				if(i < ps.length)continue;
				
				var mul : Number = p;
				var seg : Array = []; 
				for(i = 0;i <= lim[j];i++){
					l[j] = i;
					seg.push({num:mul, factors:l.concat()});
					mul *= p;
				} 
				ret.push(seg);
			}
			return ret;
		}
			
		private function enumE1() : Array
		{ 
			var lim : Array = [10, 5, 2, 1, 1, 1];
			var ps : Array = [2, 3, 5, 7, 11, 13];
			
			var seed : Array = [{num:1, factors:[0, 0, 0, 0, 0, 0]}];
			for(var i : uint = 0;i < 6;i++){
				var l : uint = seed.length;
				for(var j : uint = 0;j < l;j++){
					var num : Number = seed[j].num;
					var factors : Array = seed[j].factors;
					for(var k : uint = 1;k <= lim[i];k++){
						num *= ps[i];
						var cf : Array = factors.concat();
						cf[i] = k;
						seed.push({num:num, factors:cf});
					}
				}
			}
//			tr(seed.length);
//			tr(seed);
			
			var ct : uint = 0;
			var ret : Array = [];
			for each(var s : Object in seed){
				if(isPrime(s.num+1)){
//					tr(s.num, s.factors);
					s.num++;
					if(s.num <= 13)continue;
					ret.push([s]);
					ct++;
				}
			} 
			return ret;
		}

        private function isPrime(n : Number) : Boolean
        {
            if(n <= 1)return false;
            if(n % 2 == 0)return n == 2;
            
            var sq : int = Math.sqrt(n);
            for(var i : int = 3;i <= sq;i+=2){
                if(n % i == 0){
                    return false;
                }
            }
            return true;
        }
        
        	private function tr(...o : Array) : void
		{
			_tf.appendText(o + "\n");
			_tf.scrollV = _tf.maxScrollV;
		}
	}
}