Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

2010-04-27

Project Euler #73

| 01:37 | Project Euler #73 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #73 - nitoyon.dispatchEvent(null)

nとdを正の整数として, 分数 n/d を考えよう. n<dかつHCF(n,d)=1のとき, 真既約分数と呼ぶ.</ppp>

d ≤ 8について既約分数を大きさ順に並べると, 以下を得る:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

1/3と1/2の間には3つの分数が存在することが分かる.

では, d ≤ 12,000 について真既約分数をソートした集合では, 1/3 と 1/2 の間に何個の分数があるか?

Problem 73 - PukiWiki

先日解いた #71 とほぼ同じロジック。真既約かどうかは調べなきゃ分からないので、d を固定した上で 1/2 から 1/3 の範囲の真既約分数を列挙していく。

ちょっと計算時間はかかるが、しばらくすれば正しい答えが出てくる。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem73 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const D:int = 12000;

    public function Problem73(){
        var n:int = 1, d:int = 3;
        var count:Number = 0;
        setTimeout(function():void {
            for (var i:int = 0; i < 100; i++) {
                if (d > D) {
                    t.text = count + "";
                    return;
                }

                n = d / 3;
                while (true) {
                    if (n / d > 1 / 3) {
	                    if (n / d >= 0.5) break;
	                    if (gcm(n, d) == 1) count++;
					}
                    n++;
                }

                d++;
            }

            t.text = "checking " + n + "/" + d;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function gcm(a:int, b:int):int {
        if (a < b) return gcm(b, a);
        if (a % b == 0) return b;
        return b > a - b ? gcm(b, a - b) : gcm(a - b, b);
    }
}
}

2010-04-26

Project Euler #71

| 01:18 | Project Euler #71 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #71 - nitoyon.dispatchEvent(null)

nとdを正の整数として, 分数 n/d を考えよう. n<dかつHCF(n,d)=1のとき, 真既約分数と呼ぶ.</ppp>

d ≤ 8について既約分数を大きさ順に並べると, 以下を得る:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

3/7のすぐ左の分数は2/5である.

d ≤ 1,000,000について真既約分数を大きさ順に並べたとき, 3/7のすぐ左の分数の分子を求めよ.

Problem 71 - PukiWiki

何も考えずに全通り調べると、100万^2 通り調べなきゃいけないので現実的ではない。d を固定して 3/7 の左近傍となる n を求めることはできるので、これを 0<d<=1000000 について調べればいい。</ppp>

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem71 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const D:int = 1000000;

    public function Problem71(){
        var n:int = 1, d:int = 2;
        var nearestN:int = 0, nearest:Number = 0;
        setTimeout(function():void {
            for (var i:int = 0; i < 1000; i++) {
                if (d > D) {
                    t.text = nearestN + "";
                    return;
                }

                n = d * 3 / 7;
                while (true) {
                    if (n / d <= nearest) break;
                    if (gcm(n, d) == 1 && n / d < 1) {
                        if (n / d < 3 / 7 && n / d > nearest) {
                            nearestN = n;
                            nearest = n / d;
                        }
                        break;
                    }
                    n--;
                }

                d++;
            }

            t.text = "checking " + n + "/" + d;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function gcm(a:int, b:int):int {
        if (a < b) return gcm(b, a);
        if (a % b == 0) return b;
        return b > a - b ? gcm(b, a - b) : gcm(a - b, b);
    }
}
}

2010-04-25

Project Euler #69

| 16:38 | Project Euler #69 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #69 - nitoyon.dispatchEvent(null)

オイラーのトーティエント関数、φ(n)[時々ファイ関数とも呼ばれる]は、nと互いに素なn未満の数の数を定める。たとえば、1、2、4、5、7、そして8はみな9未満で9と互いに素であり、φ(9)=6.

n互いに素な数φ(n)n/φ(n)
2112
31,221.5
41,322
51,2,3,441.25
61,523
71,2,3,4,5,661.1666...
81,3,5,742
91,2,4,5,7,861.5
101,3,7,942.5

n ≤ 10ではn/φ(n)の最大値はn=6であることがわかる。

n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ。

Problem 69 - PukiWiki

トーティエント関数を求める処理が複雑そうで敬遠していたが、オイラーのφ関数 - Wikipedia によると、φ=n*(1-1/p_1)*(1-1/p_2)...*(1-1/p_k) で求められるとのことなので、n/φ を求めるのも簡単。

あとは素因数分解すればよいだけ。100万までの数を順番に素因数分解する処理がだいぶ重かったが、少し我慢すれば求められた。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem69 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const N:int = 1000000;
    private var primes:Array;
    private var _isPrime:Object;

    public function Problem69(){
        enumPrime();
    }

    private function doit():void {
        var maxValue:Number = 0;
        var max:int = 0;
        var n:int = 1;
        setTimeout(function():void {
            for (var i:int = 0; i < 1000; i++) {
                var m:int = n;
                var v:Number = 1;
                for each (var p:int in primes) {
                    if (m % p == 0) {
                        v *= (1 - 1.0 / p);
                        while (m % p == 0) {
                            m /= p;
                        }
                    }
                    if (m == 1) break;
                }
                v = 1 / v;

                if (maxValue < v) {
                    maxValue = v;
                    max = n;
                }

                if (n >= 1000000) {
                    t.text = max + "\n" + maxValue;
                    return;
                }

                n++;
            }

            t.text = "calc " + n + " min: " + max;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function enumPrime():void {
        var n:int = 5;
        var isNotPrime:Array = [];
        primes = [2, 3];
        _isPrime = {2: true, 3: true};
        setTimeout(function():void {
            var c:int = 0;
            for (var j:int = 0; j < 2000; j++) {
                if (n % 2 != 0 && n % 3 != 0 && !isNotPrime[n]) {
                    primes.push(n);
                    _isPrime[n] = true;
                    for (var i:int = n * 2; i < N; i += n) {
                        isNotPrime[i] = true;
                        c++;
                    }
                }
                n += 2;
                if (c > 10000 || n >= N) break;
            }

            if (n < N) {
                t.text = "check prime " + n + "...";
                setTimeout(arguments.callee, 10);
            } else {
                doit();
            }
        }, 10);
    }
}
}

2010-04-21

Project Euler #99

| 00:27 | Project Euler #99 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #99 - nitoyon.dispatchEvent(null)

指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 < 3^7 = 2187 であることが確かめられる.

しかし, 632382^518061 > 519432^525806 を確認することは非常に難しい (両者ともに300万桁以上になる).

各行に1組が書かれている1000個の組を含んだ22Kのテキストファイルbase_exp.txtから, 最大の数が書かれている行の番号を求めよ.

Problem 99 - PukiWiki

まじめに計算するなら気が遠くなるが、log を取れば激しく簡単な問題になる。それだけ。

package{
import flash.display.Sprite;
import flash.text.TextField;

public class Problem99 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem99(){
		var max:int = -1;
		var max_num:Number = 0;

		var list:Array = data.split(/\r?\n/);
		for (var i:int = 0; i < list.length; i++) {
			var v:Array = list[i].split(",");
			var n:Number = parseFloat(v[1]) * Math.log(parseFloat(v[0]));
			if (n > max_num) {
				max_num = n;
				max = i + 1;
			}
		}

		t.text = max.toString();
    }

	private var data:String = <>519432,525806
632382,518061
78864,613712
466580,530130
780495,510032
525895,525320
  :
13846,725685</>.toString();
}
}

Project Euler #81

| 01:01 | Project Euler #81 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #81 - nitoyon.dispatchEvent(null)

下記の5次の正方行列で、左上のセルから開始し右下のセルで終わる道を探索する。ただし下方向と右方向にのみ移動できるものとする。一番小さなパスは下で太字で示されたものである。このときの合計は2427になる。

131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331

今、31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 左上のセルから開始し右下のセルで終わりかつ右方向と下方向にのみ移動するときの最小の道の和を求めよ.

Problem 81 - PukiWiki

80×80だけど、DP の標準的な適用例なのでそのまま解く。

package{
import flash.display.Sprite;
import flash.text.TextField;

public class Problem81 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem81(){
        var list:Array = data.split(/\r?\n/);
        var a:Array = [0];

        for each (var line:String in list) {
            var s:Array = line.split(/,/);
            for (var i:int = 0; i < s.length; i++) {
                a[i] = (a[i] == undefined ? Infinity : a[i]);
                a[i] = Math.min(a[i], i == 0 ? Infinity : a[i - 1]) + parseInt(s[i]);
            }
        }

        t.text = a[a.length - 1];
    }

    private var data:String = <>4445,2697,5115,718,2209,2212,654,4348,3079,6821,7668,3276,8874,4190,3785,2752,9473,7817,9137,496,7338,3434,7152,4355,4552,7917,7827,2460,2350,691,3514,5880,3145,7633,7199,3783,5066,7487,3285,1084,8985,760,872,8609,8051,1134,9536,5750,9716,9371,7619,5617,275,9721,2997,2698,1887,8825,6372,3014,2113,7122,7050,6775,5948,2758,1219,3539,348,7989,2735,9862,1263,8089,6401,9462,3168,2758,3748,5870
    :
5304,5499,564,2801,679,2653,1783,3608,7359,7797,3284,796,3222,437,7185,6135,8571,2778,7488,5746,678,6140,861,7750,803,9859,9918,2425,3734,2698,9005,4864,9818,6743,2475,132,9486,3825,5472,919,292,4411,7213,7699,6435,9019,6769,1388,802,2124,1345,8493,9487,8558,7061,8777,8833,2427,2238,5409,4957,8503,3171,7622,5779,6145,2417,5873,5563,5693,9574,9491,1937,7384,4563,6842,5432,2751,3406,7981</>.toString();
}
}

2010-04-19

Project Euler #63

| 00:10 | Project Euler #63 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #63 - nitoyon.dispatchEvent(null)

5桁の数 16807 = 7^5は自然数を5乗した数である. 同様に9桁の数 134217728 = 8^9も自然数を9乗した数である.

自然数をn乗して得られるn桁の正整数は何個あるか?

Problem 63 - PukiWiki

特に工夫もなく 1乗から100乗ぐらいまで求めてみた。101乗以上にはないことは、10^n は n 桁を越えるし、9^n が n 桁より小さくなる閾値を越えたら、それ以上は見つからないはずなので証明できるだろう。結局、最大の n は 21 だった。

package{
import flash.display.Sprite;
import flash.text.TextField;

public class Problem63 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem63(){
        var n:int = 1;
        var result:Array = [];

        for (var i:int = 0; i < 100; i++) {
            var m:int = 1;
            while (true) {
                var num:Num = new Num(1);
                for (var j:int = 0; j < n; j++) { num.mul(m); }
                if (num.toString().length == n) {
                    result.push(m + "^" + n);
                } else if (num.toString().length > n) {
                    break;
                }
                m++;
            }
            n++;
        }

        t.text = result.length + "";
    }
}
}

class Num{
    private var digits:Array = [];
    private static const N:int = 5;
    
    public function Num(a:int){
        digits[0] = a;
        carry();
    }

    public function mul(a:int):Num{
        for(var i:int = 0; i < digits.length; i++){
            digits[i] *= a;
        }
        carry();
        return this;
    }

    private function carry():void{
        for(var i:int = 0; i < digits.length; i++){
            if(digits[i] >= Math.pow(10, N)){
                if(digits.length <= i + 1) digits[i + 1] = 0;
                digits[i + 1] += Math.floor(digits[i] / Math.pow(10, N));
                digits[i] %= Math.pow(10, N);
            }
        }
    }

    public function toString():String {
        var ret:String = "";
        for (var i:int = 0; i < digits.length - 1; i++) {
            var tmp:String = digits[i];
            while (tmp.length < N) tmp = "0" + tmp;
            ret = tmp + ret;
        }
        ret = digits[digits.length - 1].toString() + ret;
        return ret;
    }
}

Project Euler #92

| 23:06 | Project Euler #92 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #92 - nitoyon.dispatchEvent(null)

各桁の数を2乗して足し合わせて新たな数を作ることによって、作られる数字の列を考える。

例えば

  • 44 → 32 → 13 → 10 → 1 → 1
  • 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

のような列である。結果として1か89で無限ループに陥っている。

ここで、ある数から始めた列は1か89に到達することが分かっている。

では、10,000,000より小さい数で89に到達する数はいくつあるか。

Problem 92 - PukiWiki

何も考えずに1000万回ループするだけ。いちおうメモ化してみてけど、しなくてもあまり速度には影響でないと思う。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem92 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem92(){
        var n:int = 1;
        var result:int = 0;
        var cache:Object = {
            89: 1,
            1: -1
        };
        var a:Array = [];

        setTimeout(function():void {
            for (var i:int = 0; i < 5000; i++) {
                if (n >= 10000000) {
                    t.text = result.toString();
                    return;
                }

                var m:int = n;
                do {
                    if (cache[m] > 0) { result++; }
                    if (cache[m] != null) {
                        cache[n] = cache[m];
                        break;
                    }

                    m = getNext(m);
                } while (true);
                n++;
            }

            t.text = result + "/" + n;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function getNext(i:int):int {
        var ret:int = 0;
        while (i > 0) {
            ret += Math.pow(i % 10, 2);
            i /= 10;
        }
        return ret;
    }
}
}