Project Euler 282

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=282
    public class Euler282 extends Sprite {
        private var _tf : TextField;
  
        public function Euler282() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
//            tr(solve());
//            tr(Math.pow(14, 8));
            tr(solve()%Math.pow(14, 8));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        // A(m,n)=A(m-1,A(m,n-1))の値は、A(m-1,*)の列とA(m,n-1)があれば決まり、
        // A(m,n-1)の剰余の値からA(m,n)が一意に定まるので、
        // A(m,n)の剰余は、mを固定するとnに関して周期を持つ。
        // 
        // m=3のとき、A(m,n)=2^(n+3)-3
        // 14^8を法として、A(3,n)の周期は3*7^7. ただし最初の5項は除外。
        // P(4,0)=A(4,0)%14^8, Q(4,0)=A(4,0)%(3*7^7)を出発点として、
        // Q(4,i)から、A(3,Q(4,i))の14^8を法とした値と3*7^7を法とした値を求めて、
        // P(4,i+1),Q(4,i+1)とする。
        // 同じ値にあったら、そこまでを周期とみなしその列は終了する。
        // できた周期を、上記の3*7^7のところと置き換えてA(5,*)を求めていく。
        // 以下略
        // 
        // P.S. 2^(n+3)-3の剰余を求めるところは端折れるので、テーブル引きにしなくてもいける。
		private function solve() : Number
        {
        		var t3 : Array = new Array(4941258/2+5);
        		var i : uint;
        		for(i = 0;i < 5;i++)t3[i] = (1 << (i + 3)) - 3;
        		var b : uint = 1;
        		for(i = 5;i < 4941258/2+5;i++){ // 6*7^7
        			t3[i] = 256 * b - 3;
        			b = (b * 2) % 5764801; // 7^8
        		}
        		
        		var t3ind : Array = [];
        		b = 1;
        		for(i = 0;;i++){
        			t3ind.push(8 * b - 3);
        			b = (b * 2) % 2470629; // 3*7^7
        			if(b == 1)break;
        		} 
        		
        		var ret4 : Array = next(t3, t3ind, 4941258/2);
        		var ret5 : Array = next(ret4[0], ret4[1], ret4[2]);
        		var ret6 : Array = next(ret5[0], ret5[1], ret5[2]);
        		tr("r4 : " + ret4[0][3]); 
        		return 1 + 3 + 7 + 61 +
        			select(4, ret4[0], ret4[2]) +
        			select(5, ret5[0], ret5[2]) +
        			select(6, ret6[0], ret6[2]);
        }
        
        private function select(ind : int, src : Array, cycle : int) : Number
        {
        		var pr : uint = src.length - cycle;
        		return src[ind < pr ? ind : (ind - pr) % cycle + pr];
        }
        
        private function next(src : Array, inds : Array, cycle : int) : Array
        {
        		var ret : Array = [];
        		var retind : Array = [];
        		ret.push(src[1]);
        		retind.push(inds[1]);
        		var pr : Number = src.length - cycle;
//        		tr(pr, cycle);
        		var i : uint;
        		var o : Object = {};
        		o[src[1] + " " + inds[1]] = 0;
        		for(i = 1;;i++){
        			var v : Number = src[retind[i-1] < pr ? retind[i-1] : (retind[i-1] - pr) % cycle + pr];
        			var vind : Number = inds[retind[i-1] % inds.length];
//        			tr(v);
				var code : String = v + " " + vind;
        			if(o[code] != null){
        				tr(i, v, o[code]);
        				return [ret, retind, i - o[code]];
        			}
        			o[code] = i;
        			ret.push(v);
        			retind.push(vind);
        		}
        		return null;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}